Факторизация. p-1 метод Полларда.

[julyk]

$p-1$ метод Полларда - один из методов факторизации целых чисел. Пусть $n=pq$. Метод выдаст результат в том случае, когда база разложения будет содержать такие числа, что $(p-1)$ будет B-гладким, а $(q-1)$ - нет (или наоборот).
Мне нужно разложить число 19750241176032508049. WolframAlpha позволяет узнать, что $n = 4444120783\cdot4444127903.$ Заметим, что

$$4444120782 = 2\cdot3\cdot3\cdot3\cdot2837\cdot29009;$$

$$4444127902 = 2\cdot2222063951.$$

Зная эти сомножители, выберем базу разложения. Пусть она состоит из 4 элементов $B=\{2,3,2837,29009\}$. Случайное число возьмем равным 2. Разложение найти не удается. Аналогично, если выбираем базу $B={2,2222063951}.$ Но! При добавлении в базу числа 2222063951, то есть при выборе базы $B=\{2,3,2837,29009, 2222063951\}$, алгоритм верно находит $p.$

$$p=4444120782.$$

Мне нужно понять, почему так происходит. Подскажите пожалуйста.

[Sonic86]

Так, я плохо знаю $p-1$-метод Полларда, но попробую ответить. Поскольку пока мне кажется, что Вы в своем посте что-то не договариваете и считаете людей, способных Вам помочь, телепатами, то я напишу, как мне кажется, те вычисления, которые Вы делали и попробую их объяснить. Если я не угадаю, то поправьте меня и тогда напишите подробно, что Вы делали.

Вы берете данное $n$, $a=2$ и для заданного $B$ находите $R=a^{\prod\limits_{b\in B}b}-1\bmod n$ и $d=\gcd(R,n)$, причем у Вас для $B=\{2,3,2837,29009\}$ получается $d=1$, для $B=\{2,2222063951\}$ тоже $d=1$, а для $B=\{2,3,2837,29009, 2222063951\}$ получается $d=p$, да? И Вы спрашиваете, почему так.
Последнее довольно просто: если $a$ взаимно просто с $m$, то по теореме Эйлера $a^{\varphi(m)}\equiv 1\pmod m$, где $\varphi(m)$ - функция Эйлера, и даже $a^{\lambda(m)}\equiv 1\pmod m$, где $\lambda(m)$ - функция Кармайкла. Для $m=n=pq, \varphi(m)=(p-1)(q-1)$, причем чаще всего эти значения достигаются для произвольного $a$. Теперь смотрите, у Вас:
$p-1=4444120782 = 2\cdot 3^3\cdot 2837\cdot 29009;$
$q-1=4444127902 = 2\cdot2222063951.$
Когда Вы берете в $B$ не $3^3$, а $3$, то у Вас будет $d=p$ только если случайно окажется, что $2$ - это девятая степень по модулю $p$, т.е. если существует $g:2\equiv g^9\pmod p$, что скорее всего неверно (лень проверять). Если Вы возьмете все же $3^3$ вместо $3$ в $B$, то у Вас стабильно для любого $a$ будет $p\mid d$. В последнем случае понятно: Вы взяли все множители $q-1$, потому он у Вас и находит $q$ (хотя Вы пишите, что он нашел $p$, я Вам не верю должно быть $q$).

[julyk]

Извините, что написала неподробно. Просто чаще всего здесь пишут люди намного умнее меня, которые кажется знают все, ну или по крайней мере очень много). Вы правильно меня поняли, но я все-таки напишу еще раз.
Вход:число $n$.
Выход:нетривиальный делитель $p$ числа $n$.
Метод.
1. Выбрать базу разложения $D$.
2. Выбрать случайное целое $a,$ $2\le a \le n-1$ и вычислить $b=НОД(a,n).$ Если $b\ge 2,$ то делитель $p$ найден.
3. Для всех чисел $z \in D$ выполнить следующие действия:
3.1. Вычислить $l=[\ln(n)/\ln(z)].$
3.2. Положить $a=a^{z^l}(\mod n).$
4. Положить $b=НОД(a-1,n).$
5. Если $b=n$, то нет ответа, иначе $p=b$ и $p-$ результат.

У меня, к моему огромному удивлению, все заработало и с базой из всех множителей $p$ (и c 3, и c 27). Но объяснять почему не работало, мне все равно надо. Можете, пожалуйста, еще раз объяснить . Я честно пыталась вчитаться(.

[Sonic86]

julyk в сообщении #809463 писал(а):

1. Выбрать базу разложения $D$.

Видимо, $D=B$.

julyk в сообщении #809463 писал(а):

У меня, к моему огромному удивлению, все заработало и с базой из всех множителей $p$ (и c 3, и c 27).

У Вас есть пункт:

julyk в сообщении #809463 писал(а):

3. Для всех чисел $z \in D$ выполнить следующие действия:
3.1. Вычислить $l=[\ln(n)/\ln(z)].$
3.2. Положить $a=a^{z^l}(\mod n).$

при наличии этого пункта уже неважно, брали изначально $3$ или $3^3$ - можно было брать $3$.

julyk в сообщении #809463 писал(а):

У меня, к моему огромному удивлению, все заработало и с базой из всех множителей $p$ (и c 3, и c 27).

Ага, вот так и должно быть.

julyk в сообщении #809463 писал(а):

Но объяснять почему не работало, мне все равно надо.

Раз не работало, значит была другая программа или другие входные данные. М.б. Вы при вводе $B$ сделали опечатку, м.б. еще что-то. Если была другая программа, то тогда, есс-но, нужно смотреть эту другую программу.
Я у Вас вижу пока только одно отличие:

julyk в сообщении #809463 писал(а):

2. Выбрать случайное целое $a,$ $2\le a \le n-1$

julyk в сообщении #808710 писал(а):

Случайное число возьмем равным 2.

Но при выбранной $B$ выше это даже не должно играть роли.
$p,q$ симметричны. Если Вы в $B$ вложили все делители $p-1$ или $q-1$, то программа должна Вам выдавать в качестве $b$ из пункта 4 число, кратное $p$ или $q$ соответственно. Или Вам программа для $a=2$ вернула $b=n$? Можете посмотреть?

[julyk]

Спасибо
Если я в базу складываю все делители обоих чисел и принимаю $a=2$, то программа в $b$ возвращает $p$, 4444120783. По идее, он кратен самому себе, значит все работает верно.