информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Рекордное число уязвимостей в 2021 
 Блокировка российских аккаунтов... 
 Отзыв сертификатов ЦБ РФ, ПСБ,... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Re: Там же приводится ссылка на ява-апплет с сорцами. Вот эта: 22.02.06 12:19  Число просмотров: 4178
Автор: gene_green Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Дело в том, что я не силён в 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).
Может, кто-нибудь разъяснит, почему она тормозит процесс и/или как оптимизировать приведенный выше код...
<theory> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2022 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach