Bilangan prima acak dan pencarian substring Rabin Karp

Question

Saya membaca algoritma Rabin-Karb dari Sedgewick. Buku itu mengatakan:

Kami menggunakan prime Q acak yang mengambil nilai sebesar mungkin sambil menghindari overflow

Pada pembacaan pertama saya tidak memperhatikan pentingnya random dan ketika saya melihat bahwa dalam kode a longdigunakan, pikiran pertama saya adalah:
a) Gunakan saringan Eratosthene untuk menemukan bilangan prima besar yang sesuai dengan a long
atau
b) mencari dari daftar bilangan prima apapun yang cukup besar yang lebih besar dari intdan menggunakannya sebagai konstanta.

Tapi kemudian penjelasan selanjutnya mengatakan:

Kami akan menggunakan longnilai yang lebih besar daripada 10^20membuat probabilitas bahwa tabrakan terjadi kurang dari10^-20

Bagian ini membuat saya bingung karena longtidak bisa muat 10^20apalagi nilainya lebih besar dari itu. Kemudian, ketika saya memeriksa kalkulasi untuk prime, buku tersebut menolak latihan yang hanya memiliki petunjuk berikut:

Bilangan acak n-digit adalah bilangan prima dengan probabilitas sebanding dengan 1 / n

Apa artinya?

Jadi pada dasarnya yang tidak saya dapatkan adalah:
a) apa artinya menggunakan bilangan prima acak ? Mengapa kita tidak dapat menghitungnya terlebih dahulu dan menggunakannya sebagai konstanta?
b) mengapa 10^20disebutkan karena di luar jangkauan long?
c) Bagaimana petunjuk itu membantu? Apa sebenarnya artinya?

Answer 1

Sekali lagi , Sedgewick telah mencoba untuk menyederhanakan algoritme dan membuat detailnya sedikit salah. Pertama, seperti yang Anda amati, 10 ²⁰ tidak dapat direpresentasikan dalam 64 bit. Meskipun mengambil bilangan prima mendekati 2 ⁶³ - 1, bagaimanapun, Anda mungkin ingin sedikit ruang untuk mengalikan dengan cara normal tanpa meluap sehingga modulo berikutnya benar. Jawabannya menggunakan bilangan prima 31-bit, yang membuatnya mudah tetapi hanya menawarkan probabilitas tabrakan dalam kisaran 10 ⁻⁹ .

Versi aslinya menggunakan sidik jari Rabin dan polinomial acak tak tersederhanakan di atas over ₂ [x], yang dari perspektif teori bilangan aljabar berperilaku sangat mirip bilangan prima acak di atas bilangan bulat. Jika kita memilih polinomial menjadi derajat 32 atau 64, maka sidik jari sangat cocok dengan kata komputer dengan panjang yang sesuai, dan penjumlahan dan pengurangan polinomial keduanya bekerja dengan XOR bitwise, sehingga tidak ada luapan.

Sekarang, Sedgewick mungkin tidak ingin menjelaskan cara kerja cincin polinomial. Baik. Jika saya harus menerapkan pendekatan ini dalam praktek, saya akan memilih p dekat prima dengan max yang mudah untuk mod oleh instruksi yang murah (aku parsial untuk 2 ³¹ - 2 ²⁷ + 1 ; EDIT sebenarnya 2 ³¹ - 1 bekerja lebih baik lagi karena kita tidak membutuhkan bilangan prima halus di sini) dan kemudian memilih bilangan acak di [1, p − 1] untuk mengevaluasi polinomial di (begitulah Wikipedia menjelaskannya). Alasan mengapa kita memerlukan beberapa keacakan adalah karena jika tidak, musuh yang tidak sadar dapat memilih masukan yang dijamin akan mengalami banyak benturan hash, yang akan sangat menurunkan waktu berjalan.

Sedgewick ingin mengikuti yang asli sedikit lebih dekat dari itu, bagaimanapun, yang pada dasarnya mengevaluasi polinomial pada nilai tetap x (secara harfiah x dalam versi asli yang menggunakan cincin polinomial). Dia membutuhkan bilangan prima acak sehingga musuh yang tidak sadar tidak dapat merekayasa tabrakan. Mengayak angka yang cukup besar cukup tidak efisien, jadi dia beralih ke Teorema Bilangan Prima (yang merupakan matematika di balik petunjuknya, tetapi hanya berlaku secara asimtotik, yang membuat kekacauan besar secara teoritis) dan tes primalitas cepat (yang bisa jadi probabilistik; kasus yang gagal tidak akan memengaruhi kebenaran algoritme, dan kasus tersebut cukup langka sehingga tidak akan memengaruhi waktu berjalan yang diharapkan).

Saya tidak yakin bagaimana dia membuktikan ikatan formal pada kemungkinan tabrakan. Ide kasar saya pada dasarnya, tunjukkan bahwa ada cukup bilangan prima di jendela yang menarik, gunakan Teorema Sisa Cina untuk menunjukkan bahwa tidak mungkin ada tabrakan untuk terlalu banyak bilangan prima sekaligus, simpulkan bahwa probabilitas tabrakan dibatasi oleh kemungkinan memilih bilangan prima yang buruk, yang rendah. Tetapi Teorema Bilangan Prima hanya berlaku secara asimtotik, jadi kita harus mengandalkan eksperimen komputer mengenai kepadatan bilangan prima dalam rentang kata mesin. Tidak hebat.