Комментарии 3
Все можно свести к поиску нетривиального решения 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)
Из x² ≡ y²(mod N) следует (y-1x)² ≡ 1(mod N).
Если мы знаем разложение на множители N = pq то с помощью алгоритма Евклида можем найти
mp-nq = 1 и тогда (mp+nq)²- 4mnpq = (mp-nq)² что как раз и означает (mp+nq)² ≡ 1(mod pq)
"И вот так всегда, на самом интересном месте..." (с) попугай Кеша
GNFS в статью бы точно влез. Будем ждать второй части.
Интересно, кстати, было читать статью по рекорду дискретного логарифмирования в том смысле, что много идей GNFS туда перетекло. Мне после неё стали понятнее идеи и приёмы GNFS.
А вообще тема годная и торт.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Факторизация чисел и методы решета. Часть I