Случайные простые числа и поиск подстроки Рабина Карпа
Я читаю алгоритм Рабина-Карба из Седжвика. В книге говорится:
Мы используем случайное простое число Q, принимая как можно большее значение, избегая переполнения.
При первом чтении я не заметил , значение случайного , и когда я увидел , что в коде long
используются мои первые мысли были:
а) сито Используйте Эратосфен, чтобы найти большое простое число , что приспосабливает long
или
б) смотреть вверх из списка штрихует любое достаточно большое простое число, большее чем, int
и использует его как константу.
Но остальная часть объяснения гласит:
Мы будем использовать
long
значение больше, чем10^20
вероятность того, что столкновение произойдет, меньше, чем10^-20
Эта часть меня сбила с толку, так как long
не может соответствовать, не 10^20
говоря уже о значении, превышающем это. Затем, когда я проверил расчет простого числа, книга перешла к упражнению, в котором есть только следующий намек:
Случайное n-значное число является простым с вероятностью, пропорциональной 1 / n
Что это значит?
Итак, в основном я не понимаю:
а) в чем смысл использования случайного простого числа? Почему мы не можем просто предварительно рассчитать его и использовать как константу?
б) почему 10^20
упомянуто, если оно выходит за пределы допустимого диапазона long
?
в) Чем полезен этот совет? Что именно это означает?
Ответы
И снова Седжвик попытался упростить алгоритм и немного ошибся в деталях. Во-первых, как вы заметили, 10 20 не могут быть представлены в 64 битах. Однако даже взяв простое число, близкое к 2 63 - 1, вам, вероятно, понадобится немного места для умножения обычным способом без переполнения, чтобы последующий модуль был правильным. В ответе используется 31-битное простое число, что упрощает задачу, но дает вероятность столкновения только в диапазоне 10 −9 .
В исходной версии используются отпечатки Рабина и случайный неприводимый многочлен над 𝔽 2 [x], который с точки зрения теории алгебраических чисел ведет себя во многом как случайное простое число над целыми числами. Если мы выберем для полинома степень 32 или 64, то отпечатки пальцев идеально впишутся в компьютерное слово соответствующей длины, а сложение и вычитание полиномов работают с побитовым XOR, поэтому переполнения нет.
Очевидно, Седжвик не хотел объяснять, как работают кольца полиномов. Хорошо. Если бы я должен был реализовать этот подход на практике, я бы выбрал простой р , близкий к максимальной , что было легко модником по дешевой инструкции (я неравнодушен к
2
31 - 2
27 + 1
; EDIT фактически- 31 - 1 работает даже лучше, так как здесь нам не нужно гладкое простое число), а затем выберите случайное число в [1, p − 1] для вычисления полиномов в (так это объясняет Википедия). Причина, по которой нам нужна некоторая случайность, заключается в том, что в противном случае невнимательный противник мог бы выбрать ввод, который гарантированно будет иметь много хеш-коллизий, что серьезно ухудшит время выполнения.
Однако Седжвик хотел следовать оригиналу немного более внимательно, чем тот, который, по сути, оценивает многочлены при фиксированном значении x (буквально x в исходной версии, которая использует кольца многочленов). Ему нужно случайное простое число, чтобы невнимательный противник не мог спланировать столкновения. Рассеивание достаточно больших чисел довольно неэффективно, поэтому он обращается к теореме о простых числах (которая является математикой, стоящей за его подсказкой, но она выполняется только асимптотически, что теоретически создает большой беспорядок) и быстрому тесту на простоту (который может быть вероятностным; случаи, когда это не удается, не повлияют на правильность алгоритма, и они достаточно редки, чтобы не повлиять на ожидаемое время работы).
Я не уверен, как он доказывает формальное ограничение вероятности столкновения. Моя приблизительная идея в основном заключается в том, чтобы показать, что в интересующем окне достаточно простых чисел, использовать китайскую теорему об остатках, чтобы показать, что невозможно столкновение слишком многих простых чисел одновременно, сделать вывод, что вероятность столкновения ограничена вероятность выбрать плохое простое число - низкая. Но теорема о простых числах верна только асимптотически, поэтому мы должны полагаться на компьютерные эксперименты относительно плотности простых чисел в диапазонах машинных слов. Не хорошо.