Дело в том, что я не силён в Java. Загнал исходник в NetBeans и разобраться, как его перегнать в Maple или хотя бы тот язык, в котором можно dll сделать, не получается, да и не относящегося к чистому ECM там много.
Приведу код на Maple, о котором говорил выше (он работает, но недостаточно быстро):
Генерация случайной кривой и точки (0,y) на ней.
> generate_curve := proc(n, p::name, bound) local a,b,y,g,random;
> if nargs = 3 then random := rand(bound):
> else random := rand(50); fi;
>
> a := 0; y := 0; g := n;
> while ( a = 0 or y = 0 or g >= n ) do
> a := random() mod n; y := random() mod n; b := y^2 mod n;
> g := igcd(4*a^3 + 27*b^2,n);
> od;
>
> if (g = 1) then
> if (nargs >= 2) then p := [0,y]; fi;
> [a,b,n];
> else g; fi;
> end:
Сложение двух точек на кривой (на входе - две точки, выводится - сумма).
> elliptic_add := proc(p1,p2,E) local g,inv,x1,x2,x3,y1,y2,y3,a,b,n;
> x1 := p1[1]; x2 := p2[1]; y1 := p1[2]; y2 := p2[2];
> a := E[1]; b := E[2]; n := E[3];
>
> if (x1=infinity and y1=infinity) then [x2,y2];
> elif (x2=infinity and y2=infinity) then [x1,y1];
> elif (x1=x2 and y1 <> y2) then [infinity,infinity];
>
> elif (x1=x2 and y1=y2) then
> g := igcdex(2*y1,n,inv);
> if g = 1 then
> x3 := ((3*x1^2+a)*inv)^2-2*x1 mod n;
> y3 := ((3*x1^2+ainv)x1-x3)-y1 mod n;
> [x3,y3];
> else g; fi;
>
> else
> g := igcdex(x2-x1,n,inv);
> if g = 1 then
> x3 := power(((y2-y1)*inv),2)-x1-x2 mod n;
> y3 := (y2-y1invx1-x3)-y1 mod n;
> [x3,y3];
> else g; fi;
> fi;
> end:
Произведение точки и числа:
> elliptic_mul := proc(p1,k,E) local pn,ps,d,r;
> pn := p1; r := irem(k,2);
> if r = 1 then ps := p1; else ps := [infinity,infinity]; fi;
> d := (k-r)/2;
>
> while (d > 0 and (not (type(ps,integer) or type(pn,integer)) and (pn <> [infinity,infinity]))) do
> r := irem(d,2);
> pn := elliptic_add(pn,pn,E);
> if r = 1 then ps := elliptic_add(ps,pn,E); fi;
>
> d := (d-r)/2;
> od;
>
> if type(pn,integer) then pn;
> else ps; fi;
> end:
И, собственно, сам ECM...
> ecf := proc(n,boundB,boundC) local B,C,E,p,k,d,i,q;
>
> if isprime(n) then RETURN(n); fi;
> if nargs = 2 then B := boundB; else B := 2*length(n); fi;
> if nargs = 3 then C := boundC; else C := ilog[2](n); fi;
>
> q := 2; k := 1;
> while q < B do
> k := k*q^ilog[q](C);
> q := nextprime(q); od;
>
> d := 1;
> while (d=1 or d=n) do
> E := generate_curve(n,'p');
> if type(E,integer) then d := E;
> else
> d := elliptic_mul(p,k,E);
> if not type(d,integer) then d := 1; fi;
> fi;
> od;
> d;
> end:
Проанализировав время выполнения кода, отвечающего за сам ECM, пришёл к выводу, что медленно работает из-за строчки d := elliptic_mul(p,k,E).
Может, кто-нибудь разъяснит, почему она тормозит процесс и/или как оптимизировать приведенный выше код...
|
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
