Регистрация Войти
Рейтинг:0
killertoge avatar Crypto

Сложность теста на простоту Рабина-Миллера

флаг lk
killertoge

Я думал о сложности теста на простоту Рабина-Миллера. В википедии я нахожу O(k log3n), но объяснения нет. Моя идея была слишком простой. Чтобы увидеть, является ли n простым, у нас есть k попыток, и с каждой попыткой мы проверяем, равен ли первый элемент b 1, иначе мы ищем -1 в b-последовательности. Здесь b = a^u mod n и n-1 = 2^l * u, u нечетно, причем (b,b^2^1,b^2^2,b^2^3,...,b^ 2^(1-1)). Итак, я предполагаю худший сценарий, мы вычисляем все вплоть до последней степени, прямо перед тем, как мы достигнем фактического fermats-primetest. Итак, если мы можем представить n-1 = 2 ^ lu с нечетным u, то нам потребуется всего k * (n-1)/(2u) шагов.

60
0 + 0
Рейтинг:1
kodlu avatar Crypto
флаг sa
kodlu

введите описание изображения здесь

Используя двоичное расширение экспоненты $t$ и повторный квадрат, который вы можете вычислить $х^т$ по модулю $n$ с $O(\log п)$ по модулю $n$ операции умножения.

И каждый модуль $n$ умножение и деление займет $O(\log^2n)$ целочисленные операции. Так что это делает $O(\log^3n)$ целочисленные операции.

Как только у вас есть $х^т$ по модулю $n,$ тогда $х^{2т},х^{4т},х^{2^ст}$ по модулю $n$ можно получить по $s\leq\log_2 n$ итерации повторного возведения в квадрат по модулю $n$.

Все остальные операции имеют меньшую сложность.

Если вы повторите $к$ раз уменьшить вероятность ошибки, вы получаете $O(k \log^3 n).$

0 + 0
killertoge avatar
флаг lk
killertoge
Я понимаю, что при двоичном расширении мне потребуется O (log n) операций, чтобы получить x ^ n. Так как мы по модулю n, каждое умножение стоит O(log^2n), хорошо!. Делаем k попыток O(k log^3 n), хорошо!. Но не делайте этого до конца a^(n-2), так как последнее возведение в квадрат будет простым тестом Ферма. Так это O (k log ^ 2 n log (n-2))?
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.