Факторизация чисел и методы решета. Часть I

[paluke]

Все можно свести к поиску нетривиального решения x² ≡ 1(mod N) где x ≠ ±1
Из x² ≡ y²(mod N) следует (y^-1x)² ≡ 1(mod N).
Если мы знаем разложение на множители N = pq то с помощью алгоритма Евклида можем найти
mp-nq = 1 и тогда (mp+nq)²- 4mnpq = (mp-nq)² что как раз и означает (mp+nq)² ≡ 1(mod pq)

[domix32]

А это разве для всех N работает?

[speshuric]

"И вот так всегда, на самом интересном месте..." (с) попугай Кеша
GNFS в статью бы точно влез. Будем ждать второй части.

Интересно, кстати, было читать статью по рекорду дискретного логарифмирования в том смысле, что много идей GNFS туда перетекло. Мне после неё стали понятнее идеи и приёмы GNFS.

А вообще тема годная и торт.