А за сколько второй ECM найдёт второй делитель? Может быстрее 45мс?
Нет, медленнее. Он же работает детерминировано, время работы зависит от B1 (ну и от rounds конечно но там как повезёт).
В этом недостаток ECM с точки зрения управления ожиданиями, и одновременно преимущество.
Вот сколько ищется первый множитель:
Код:
? n=24148925432634573196763136754090576178896835988651533646083;
? c=0;for(i=1,100,if(my_ecm(n,2,random(100),15000),c++));print(c)
100
time = 1min, 38,063 ms.
?
Видим, что нашёлся 100 раз из 100, за 938мс в среднем.
Посмотрим за сколько найдёт оба:
Код:
? n=24148925432634573196763136754090576178896835988651533646083;
? {c1=0;c2=0;
for(i=1,100,
nr=my_ecm(n,2,random(100),15000);
if(nr,
nr2=my_ecm(n/nr,2,random(100),15000);
c1++
,
next()
);
if(nr2,c2++));
print(" Один:",c1," Оба:",c2);}
Один:100 Оба:17
time = 3min, 10,893 ms.
?
Видим что второй множитель с теми же параметрами находит только в 17% случаев, а времени тратит (на второй) столько же сколько и на первый, в сумме в два раза дольше.
То есть, в этом конкретном случае, не надо второй раз запускать ECM.
Запускаем теперь второй раз mpqs:
Код:
? n=24148925432634573196763136754090576178896835988651533646083;
? {c1=0;c2=0;
for(i=1,100,
nr=my_ecm(n,2,random(100),15000);
if(nr,
nr2=my_mpqs(n/nr);
c1++
,
next()
);
if(nr2,c2++));
print(" Один:",c1," Оба:",c2);}
Один:100 Оба:100
time = 1min, 35,184 ms.
?
Итого, полная факторизация за 935мс в среднем (то есть время mpqs на грани погрешности, мгновенно если первый множитель уже найден), против более 2 секунд встроенной факторизации.
Но это - на конкретном числе, совсем не факт что на других будет обгонять.
Даже скорее не будет...
-- добавлено через 16 минут --А это по моему без разницы - они из эллиптических кривых, т.е. самого алгоритма ECM, независимо от конкретной реализации.
Ну смотрите, вот для
n=24148925432634573196763136754090576178896835988651533646083Для параметров ECM в pari-шной реализации,
rounds=2, B1=15000 и
seed случайный от 0 до 99, множитель находится в 100 случаях из 100 (но не факт что в 1000 случаях из 1000) . То есть вероятность, похоже, больше 98%
А что было бы у вас, какие оптимальные B1 и rounds?
Сдаётся мне что B1 это не что-то универсально принятое.
P.S. На всякий случай, как у меня определены встроенные ECM и MPQS:
Код:
install(Z_ECM,GLLU);
install(mpqs,G);
isnl(x=[])=x;
my_ecm(n,rounds,seed,b1)=isnl(Z_ECM(n,rounds,seed,b1));
my_mpqs(n:int)=my(divisor=component(mpqs(n),1));return([divisor,n/divisor]);
В my_mpqs я возвращаю вектор потому, что не уверен что там возвращается простое, так что на всякий случай возвращаю два множителя, и потом проверяю их оба на простоту.
посчитали вероятности того что число величиной 66 десятичных цифр состоит из omega=2,3.. множителей при условии, что множителей меньших 2^20 точно нет и число точно составное
