Как стать автором
Обновить

Комментарии 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)

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

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


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


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

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Публикации

Истории