Как вычислить дискриминанты КМ без факторинга?

В ECC есть параметр, известный как дискриминанты CM. Предположим, что след кривой есть $t$ в $Z_p$. Количество $s^2$ это самый большой квадрат, делящий $т^2-4п$ тогда $\frac{t^2-4p}{s^2}$ является свободным от квадратов отрицательным целым числом. Дискриминант СМ $\frac{t^2-4p}{s^2}$ если $\frac{t^2-4p}{s^2} \mod 4 = 1$, иначе как $4(\frac{t^2-4p}{s^2})$. Как вычислить этот параметр без факторинга? Есть ли какой-то алгоритм для этого? Кто-нибудь может написать программу в Sage для вычисления D?

Мы хотим найти $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 рассматриваемого размера (в порядке $р$ в худшем случае); и выполнить досрочное прерывание в относительно редком случае, когда трудно получить полную факторизацию.

(Пересмотренный) метод, который я предлагаю, заключается в следующем:

1. Вытяните как можно больше факторов $n$ насколько это возможно, используя пробное деление на маленькие простые числа и, возможно, немного Ро Полларда.

2. В этот момент мы выразили $n$ как $n=u\prod{p_i}^{k_i}$ с отчетливым $p_i$, и каждый $k_i\ge1$. Улучшите это (например, пробным разделением $u$ каждым $p_i$) так что нет $p_i$ делит $u$.

3. Если $u$ является простым или $1$, тогда $D=-u\prod{p_i}^{k_i\bmod 2}$, мы можем протестировать $-D\ge B$, останавливаться.

4. Если $u$ является квадратом (что легко проверить), то $D=-\prod p_i^{k_i\bmod 2}$, мы можем протестировать $-D\ge B$, останавливаться.

5. [необязательно] Попробуйте извлечь больше факторов из $u$ используя ограниченное количество Полларда р-1, и Р+1 Уильямса (например, в GMP-ECM); и если это удастся, улучшите факторизацию и продолжите с (2.)

6. На данный момент мы знаем, что выполняется одно из следующих двух утверждений:

   • $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.)

7. Если шаг (6.) не раскрыл фактор, у нас есть варианты:

   • Откажитесь от наших усилий по этой кривой и попробуйте новую в надежде, что проверка будет проще;
   • Фактор $u$ с ППМПКС или же GNFS;
   • Вывод $D=-u\prod{p_i}^{k_i\bmod 2}$ который имеет лишь небольшую вероятность быть неверным, ограниченную вычислимой вероятностью того, что количество ECM Ленстры, которое мы сделали, не могло бы извлечь коэффициент меньше, чем $\sqrt[3]u$
   • Подтвердить $-D\ge B$ который имеет лишь небольшую вероятность быть неверным, ограниченную вычислимой вероятностью того, что количество ECM Ленстры, которое мы сделали, не могло бы извлечь коэффициент меньше, чем $В$