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

Почему факториал используется в алгоритме Полларда $p - 1$?

флаг et
user93353

Почему именно мы используем факториал для нахождения $L$ который делится на $р - 1$?

Алгоритм Полларда касается B-гладких чисел, а не B-гладких чисел. Итак, где именно появляется факториал? Факториалы ничего не делают, это просто умножение чисел без возведения в степень.

Я имею в виду Полларда. $р - 1$ алгоритм, описанный в книге Сильвермана «Математическая криптография», где они проверяют $a^{j!} - 1$ в цикле (с увеличением j), пока они не найдут правильный $gcd(a^{j!} - 1)$ что приводит к фактору.

Я понимаю ту часть, где Малая теорема Ферма используется, чтобы показать, что L таково, что $p-1$ делит $a^L - 1$ & $q-1$ не разделяет $a^L - 1$ - мой вопрос не об этом. Мой вопрос: почему/как попытка ${j!}$ (т. е. попытка факториала) работает для нахождения подходящего $L$?

137
1 + 0
Рейтинг:3
SSA avatar Crypto
флаг ng
SSA

Теорема Ферма лежит в основе этой второй схемы факторизации, известной как метод Полларда p-1.

  • предположим, что нечетное составное целое число n, которое нужно разложить на множители, имеет простой делитель n со свойством, что p-1 является произведением относительно небольших простых чисел. Пусть q будет любым целым числом таким, что (p-1)|q. Например, q может быть либо k! или наименьшее общее кратное первых k положительных целых чисел, где k берется достаточно большим. выберите 1<a<p-1
  • $${m\equiv a^q \equiv a^{(p-1)j}\equiv 1^j \equiv1(modp)}$$ подразумевает р | (м-1), это силы ${НОД(m-1,n)>1}$
  • Но здесь важно отметить, если ${НОД(м-1,n)=1}$, то следует вернуться и выбрать другое значение a.
  • Метод может потерпеть неудачу, если q (k!) считать недостаточно большим; то есть, если p-1 содержит большой простой множитель или маленькое простое число, встречающееся в большой степени, следовательно, лучше выбрать k!, а не угадывать любое новое большое число каждый раз, когда мы получаем ${НОД(м-1,n)=1}$, поэтому факториал является лучшим выбором и может увеличить вероятность обнаружения, является ли фактор большим простым фактором.
0 + 10
флаг et
user93353
Я уже понимаю, что вы объяснили выше - об использовании Ферма для доказательства того, что L таков, что $p-1$ делит $a^L - 1$ и $q-1$ не делит $a^L - 1$ - мой вопрос не связано с этим. Мой вопрос в том, почему/как ${k!}$ -т.е. пытаетесь использовать факториалы для поиска подходящего $L$?
0
Ответить
флаг et
user93353
Почему факториал лучше подходит для нахождения $L$? Или, если честно, я даже не понимаю, почему это вообще выбор?
0
Ответить
SSA avatar
флаг ng
SSA
когда вы хотите попробовать разные числа, которые могут переходить к большим значениям на каждом шаге, факториал помогает в двух случаях: [1] если у вас большой простой множитель или [2] маленькое простое число с большой степенью. так в 10! , у вас есть степень 2 равна 8, для 3 равна 2 и т.д..также я упомянул, что этот метод хорошо работает, когда p-1 является произведением относительно малого простого числа. Как вы думаете, есть ли лучший вариант?
0
Ответить
флаг et
user93353
Я вообще не могу придумать ни одного варианта :-) Я нуб.
0
Ответить
флаг et
user93353
«У вас есть степень 2, равная 8, поскольку 3 равна 2 и т. д.» - что вы имеете в виду, когда 3 равно 2?
0
Ответить
флаг et
user93353
Итак, 10! содержит (2, 2 ^ 2, 2 ^ 3), (3, 3 ^ 2) и, подобно этому, любой факториал состоит из простых степеней - и, следовательно, это хороший способ найти L - это то, что вы говорите, верно?
0
Ответить
SSA avatar
флаг ng
SSA
да, это маленькие нечетные простые числа, p-1 и q-1 - гладкие целые числа. исправление в 10!, 3 имеет степень 4.
0
Ответить
флаг pe
Samuel Neves
По большей части факториал не используется для $p-1$. Или, по крайней мере, не должно быть. Смотрите мой ответ [здесь] (https://crypto.stackexchange.com/a/72884/592).
0
Ответить
флаг et
user93353
@SamuelNeves - большинство книг, которые я просматривал, похоже, используют Factorial, а не LCM. Они даже не говорят о LCM. Например,Математическая криптография Сильвермана, книга Смарта «Радость факторинга». Метод LCM упоминается лишь в небольшой части книг. Любая идея, почему это так?
0
Ответить
флаг et
user93353
@SamuelNeves - еще одна особенность книги Сильвермана заключается в том, что он, кажется, смотрит на B-smooth (p-1), а не на B-powersmooth (p-1). И, по-видимому, подразумевает, что если p-1 является B-гладким, то вам нужно подняться до B!, тогда как методы LCM, кажется, говорят, что если p-1 является B-гладким, то вам нужно перейти до LCM (от 1 до B) . Это также вопрос путаницы.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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