Rastgele asal sayılar ve Rabin Karp alt dize araması

Aug 17 2020

Sedgewick'ten Rabin-Karb algoritmasını okuyorum. Kitap şöyle diyor:

Taşmayı önlerken mümkün olduğunca büyük bir değer alan rastgele bir asal Q kullanıyoruz

İlk okumada rastgele olmanın önemini fark etmedim ve kodda a'nın longkullanıldığını gördüğümde ilk düşüncelerim şunlardı:
a) a long
veya
b'ye uyan büyük bir asal bulmak için Eratosthene'in eleğini kullanın ) listeden yukarı bakın. yeterince büyük olan herhangi bir asal sayıyı hazırlar intve onu sabit olarak kullanır.

Ancak açıklamanın geri kalanı şöyle diyor:

Bir çarpışmanın daha az olması olasılığını yapmaktan longdaha büyük bir değer kullanacağız.10^2010^-20

Bu kısım kafamı karıştırdı çünkü bir daha büyük bir değer, bir longsığamaz 10^20. Daha sonra, prime için hesaplamayı kontrol ettiğimde, kitap sadece aşağıdaki ipucu içeren bir alıştırmayı erteliyor:

Rastgele bir n basamaklı sayı, 1 / n ile orantılı olasılıkla asaldır

Bu ne anlama geliyor?

Yani temelde anlamadığım şey şu:
a) rastgele bir asal kullanmanın anlamı nedir? Neden onu önceden hesaplayıp sabit olarak kullanamıyoruz?
b) 10^20menzil dışında olduğu için neden bahsediliyor long?
c) Bu ipucu nasıl yardımcı olur? Tam olarak ne anlama geliyor?

Yanıtlar

3 DavidEisenstat Aug 17 2020 at 14:09

Sedgewick bir kez daha bir algoritmayı basitleştirmeye çalıştı ve ayrıntıları biraz yanlış anladı. İlk olarak, gözlemlediğiniz gibi, 10 20 , 64 bitte temsil edilemez. 2 63 - 1'e yakın bir üssü alsanız bile , sonraki modulo'nun doğru olması için muhtemelen normal yolu çarpmadan çoğaltmak için biraz alan isteyeceksiniz. Yanıt, bunu kolaylaştıran ancak yalnızca 10-9 aralığında çarpışma olasılıkları sunan 31 bitlik bir asal kullanır .

Orijinal versiyon Rabin parmak izlerini ve cebirsel sayı teorisinin perspektifinden tamsayılar üzerinde rastgele bir asal gibi davranan 𝔽 2 [x] üzerinde rastgele indirgenemez bir polinom kullanır . Polinomu 32 veya 64 derece olarak seçersek, parmak izleri uygun uzunlukta bir bilgisayar kelimesine mükemmel bir şekilde uyar ve polinom toplama ve çıkarma her ikisi de bitsel XOR için çalışır, dolayısıyla taşma olmaz.

Şimdi, Sedgewick muhtemelen polinom halkalarının nasıl çalıştığını açıklamak istemedi. İnce. Ben pratikte bu yaklaşımı uygulamak olsaydı, maksimum bir asal p yakın seçerdim ucuz talimatlara göre mod için kolay oldu (ı kısmi değilim 2 31 - 2 27 + 1 ; DÜZENLEME aslında 2 31 - 1 daha da iyi çalışır çünkü burada düzgün bir asaya ihtiyacımız yoktur) ve sonra da polinomları değerlendirmek için [1, p − 1] 'de rastgele bir sayı seçin (Wikipedia bunu böyle açıklıyor). Biraz rastgeleliğe ihtiyaç duymamızın nedeni, aksi takdirde habersiz düşmanın, çok sayıda hash çarpışmasına sahip olacağı garanti edilecek ve bu da çalışma süresini ciddi şekilde düşürecek bir girdi seçebilmesidir.

Sedgewick, orijinali bundan biraz daha yakından takip etmek istedi, ancak özünde polinomları sabit bir x değerinde değerlendirir (polinom halkaları kullanan orijinal versiyonda kelimenin tam anlamıyla x). Farkında olmayan düşmanın çarpışmalara yol açmaması için rastgele bir asal sayıya ihtiyacı var. Yeterince büyük sayıları elemek oldukça verimsizdir, bu yüzden Asal Sayı Teoremine (ipucunun arkasındaki matematiktir, ancak teorik olarak büyük bir karışıklık yaratan sadece asimptotik olarak tutar) ve hızlı bir ilkellik testine (olasılıklı olabilir; Başarısız olduğu durumlar, algoritmanın doğruluğunu etkilemeyecektir ve beklenen çalışma süresini etkilemeyecek kadar nadirdir).

Çarpışma olasılığına ilişkin resmi bir sınırı nasıl kanıtladığını bilmiyorum. Benim kaba fikrim temelde, ilgi penceresinde yeterli asal sayı olduğunu gösterin, Çin Kalan Teoremini kullanarak aynı anda çok fazla asal çarpışma olmasının imkansız olduğunu gösterin, çarpışma olasılığının aşağıdakilerle sınırlı olduğu sonucuna varın: düşük olan kötü bir asal seçme olasılığı. Ancak Asal Sayı Teoremi yalnızca asimptotik olarak geçerlidir, bu nedenle makine kelime aralıklarındaki asalların yoğunluğu ile ilgili bilgisayar deneylerine güvenmek zorundayız. Harika değil.