Số nguyên tố ngẫu nhiên và tìm kiếm chuỗi con Rabin Karp

Question

Tôi đang đọc thuật toán Rabin-Karb từ Sedgewick. Cuốn sách nói:

Chúng tôi sử dụng một số nguyên tố Q ngẫu nhiên nhận giá trị càng lớn càng tốt trong khi tránh tràn

Lúc đầu đọc, tôi không nhận thấy ý nghĩa của ngẫu nhiên và khi tôi thấy rằng trong mã a longđược sử dụng, suy nghĩ đầu tiên của tôi là:
a) Sử dụng sàng Eratosthene để tìm một số nguyên tố lớn phù hợp với a long
hoặc
b) tra cứu từ danh sách số nguyên tố bất kỳ số nguyên tố nào đủ lớn lớn hơn intvà sử dụng nó như một hằng số.

Nhưng sau đó phần còn lại của lời giải thích nói:

Chúng tôi sẽ sử dụng một longgiá trị lớn hơn 10^20để xác suất xảy ra va chạm thấp hơn10^-20

Phần này làm tôi bối rối vì một longkhông thể phù hợp với 10^20một giá trị lớn hơn thế. Sau đó, khi tôi kiểm tra phép tính cho số nguyên tố, cuốn sách đã chuyển sang một bài tập có gợi ý sau:

Một số ngẫu nhiên có n chữ số là số nguyên tố với xác suất tỷ lệ với 1 / n

Điều đó nghĩa là gì?

Vì vậy, về cơ bản những gì tôi không nhận được là:
a) ý nghĩa của việc sử dụng một số nguyên tố ngẫu nhiên là gì? Tại sao chúng ta không thể tính toán trước nó và sử dụng nó như một hằng số?
b) tại sao được 10^20đề cập vì nó nằm ngoài phạm vi cho long?
c) Gợi ý đó hữu ích như thế nào? điều đó có chính xác?

Answer 1

Một lần nữa , Sedgewick đã cố gắng đơn giản hóa một thuật toán và đã làm sai các chi tiết. Đầu tiên, như bạn quan sát, 10 ²⁰ không thể được biểu diễn bằng 64 bit. Tuy nhiên, ngay cả khi lấy số nguyên tố gần bằng 2 ⁶³ - 1, bạn có thể sẽ muốn có một chút khoảng trống để nhân theo cách bình thường mà không bị tràn để modulo tiếp theo là chính xác. Câu trả lời sử dụng số nguyên tố 31-bit, giúp điều này dễ dàng nhưng chỉ cung cấp xác suất va chạm trong phạm vi 10 ⁻⁹ .

Phiên bản gốc sử dụng dấu vân tay Rabin và một đa thức bất khả quy ngẫu nhiên trên 𝔽 ₂ [x], theo quan điểm của lý thuyết số đại số hoạt động giống như một số nguyên tố ngẫu nhiên trên các số nguyên. Nếu chúng ta chọn đa thức là bậc 32 hoặc 64, thì các dấu vân tay hoàn toàn phù hợp với một từ máy tính có độ dài thích hợp và phép cộng và trừ đa thức đều hoạt động theo bitwise XOR, do đó không bị tràn.

Bây giờ, Sedgewick có lẽ không muốn giải thích cách hoạt động của các vành đa thức. Khỏe. Nếu tôi phải thực hiện phương pháp này trong thực tế, tôi sẽ chọn một số nguyên tố p gần với giá trị tối đa để dễ sửa đổi với các hướng dẫn rẻ tiền (tôi là một phần của 2 ³¹ - 2 ²⁷ + 1 ; EDIT thực sự là 2 ³¹ - 1 hoạt động tốt hơn vì chúng ta không cần một số nguyên tố mịn ở đây) và sau đó chọn một số ngẫu nhiên trong [1, p-1] để đánh giá các đa thức tại (đây là cách Wikipedia giải thích). Lý do mà chúng ta cần một số ngẫu nhiên là nếu không, kẻ thù không biết gì có thể chọn một đầu vào được đảm bảo có nhiều va chạm băm, điều này sẽ làm giảm thời gian chạy.

Tuy nhiên, Sedgewick muốn theo sát bản gốc hơn một chút, về bản chất, đánh giá các đa thức ở một giá trị cố định của x (nghĩa đen là x trong phiên bản gốc sử dụng các vành đa thức). Anh ta cần một số nguyên tố ngẫu nhiên để kẻ thù không biết gì không thể tạo ra va chạm. Việc sàng lọc các số đủ lớn là khá kém hiệu quả, vì vậy anh ta chuyển sang Định lý Số Nguyên tố (là phép toán đằng sau gợi ý của anh ta, nhưng nó chỉ giữ về mặt tiệm cận, điều này tạo ra một mớ hỗn độn lớn về mặt lý thuyết) và một bài kiểm tra tính nguyên sơ nhanh (có thể là xác suất; các trường hợp mà nó không thành công sẽ không ảnh hưởng đến tính đúng đắn của thuật toán và chúng đủ hiếm để không ảnh hưởng đến thời gian chạy dự kiến).

Tôi không chắc làm thế nào anh ta chứng minh được ràng buộc chính thức về xác suất va chạm. Ý tưởng sơ bộ của tôi về cơ bản là, hãy chứng minh rằng có đủ số nguyên tố trong cửa sổ quan tâm, sử dụng Định lý Phần dư Trung Quốc để chỉ ra rằng không thể xảy ra va chạm cho quá nhiều số nguyên tố cùng một lúc, kết luận rằng xác suất va chạm bị giới hạn bởi xác suất chọn một số nguyên tố xấu, thấp. Nhưng Định lý Số nguyên tố chỉ có tiệm cận, vì vậy chúng ta phải dựa vào các thí nghiệm máy tính về mật độ của các số nguyên tố trong phạm vi từ máy. Không tốt.