Мы хотим найти $D=-n/s^2$ за $s^2$ самый большой квадрат, разделяющий известный $n=4p-t^2>0$ (куда $t$ это след и $n$ - порядок эллиптической кривой с уравнением в $\mathbb F_p$), по той же причине SafeCurves делает: констатирует $-D\ge B$ для некоторых $В$ (SafeCurves имеет $2^{-100}=B$ ). Я никогда не пытался и не исследовал это. Этот ответ является предварительным диким предположением.
Неизвестен метод с эвристическим полиномом времени по размеру $n$ который тянет квадратные множители $n$ с уверенностью (или даже с высокой степенью уверенности, AFAIK), по желанию; и я понятия не имею, чтобы кто-то работал на такого рода $n$ обдуманный.
Лучшее, что я могу предложить, это пытающийся учитывать $n$ используя методы, используемые для общих целых чисел, в частности ЕСМ Ленстры, в отличие от тех (ППМПКС или же GNFS), который будет использоваться для модулей RSA рассматриваемого размера (в порядке $р$ в худшем случае); и выполнить досрочное прерывание в относительно редком случае, когда трудно получить полную факторизацию.
(Пересмотренный) метод, который я предлагаю, заключается в следующем:
Вытяните как можно больше факторов $n$ насколько это возможно, используя пробное деление на маленькие простые числа и, возможно, немного Ро Полларда.
В этот момент мы выразили $n$ как $n=u\prod{p_i}^{k_i}$ с отчетливым $p_i$, и каждый $k_i\ge1$. Улучшите это (например, пробным разделением $u$ каждым $p_i$) так что нет $p_i$ делит $u$.
Если $u$ является простым или $1$, тогда $D=-u\prod{p_i}^{k_i\bmod 2}$, мы можем протестировать $-D\ge B$, останавливаться.
Если $u$ является квадратом (что легко проверить), то $D=-\prod p_i^{k_i\bmod 2}$, мы можем протестировать $-D\ge B$, останавливаться.
[необязательно] Попробуйте извлечь больше факторов из $u$ используя ограниченное количество Полларда р-1, и Р+1 Уильямса (например, в GMP-ECM); и если это удастся, улучшите факторизацию и продолжите с (2.)
На данный момент мы знаем, что выполняется одно из следующих двух утверждений:
- $u$ является произведением двух различных простых чисел, ни одно из которых не является одним из наших $p_i$;
- $u$ является произведением трех или более простых множителей (то есть, если $u=\prod{p_j}^{k_j}$ с $p_j$ премьер тогда $\сумма k_j\ge3$ ), следовательно $u$ делится не более чем на простое число $\sqrt[3]u$.
Теперь мы используем ЕСМ Ленстры как напр. в GMP-ECM с надеждой найти множитель меньше $\sqrt[3]u$, или меньше границы $В$. Если это удастся, улучшите факторизацию и продолжите с (2.)
Если шаг (6.) не раскрыл фактор, у нас есть варианты:
- Откажитесь от наших усилий по этой кривой и попробуйте новую в надежде, что проверка будет проще;
- Фактор $u$ с ППМПКС или же GNFS;
- Вывод $D=-u\prod{p_i}^{k_i\bmod 2}$ который имеет лишь небольшую вероятность быть неверным, ограниченную вычислимой вероятностью того, что количество ECM Ленстры, которое мы сделали, не могло бы извлечь коэффициент меньше, чем $\sqrt[3]u$
- Подтвердить $-D\ge B$ который имеет лишь небольшую вероятность быть неверным, ограниченную вычислимой вероятностью того, что количество ECM Ленстры, которое мы сделали, не могло бы извлечь коэффициент меньше, чем $В$