информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяСтрашный баг в Windows
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Линуксовый ботнет, распространяющийся... 
 Конец поддержки Internet Explorer 
 Рекордное число уязвимостей в 2021 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Re: Там же приводится ссылка на ява-апплет с сорцами. Вот эта: 22.02.06 12:19  Число просмотров: 4193
Автор: 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>
Факторизация Ленстры эллиптическими кривыми. 01.02.06 01:46  
Автор: gene_green Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Та самая, о которой говорится здесь: http://en.wikipedia.org/wiki/Lenstra_Elliptic_Curve_Factorization

Подскажите, пожалуйста, более детальный (с точки зрения программирования, скажем, на Maple (но не ifactor(n,lenstra)!) ) алгоритм реализации этой факторизации, и где можно найти уже реализованный алгоритм?
Там же приводится ссылка на ява-апплет с сорцами. Вот эта: 22.02.06 11:56  
Автор: RElf <M> Статус: Member
Отредактировано 22.02.06 11:57  Количество правок: 1
<"чистая" ссылка>


Factorization using the Elliptic Curve Method (ECM)
Re: Там же приводится ссылка на ява-апплет с сорцами. Вот эта: 22.02.06 12:19  
Автор: 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).
Может, кто-нибудь разъяснит, почему она тормозит процесс и/или как оптимизировать приведенный выше код...
b = (y^2 - x^3 - ax) mod n 14.08.06 20:47  
Автор: Led Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Дело в том, что я не силён в Java. Загнал исходник в
> NetBeans и разобраться, как его перегнать в Maple или хотя
> бы тот язык, в котором можно dll сделать, не получается, да
> и не относящегося к чистому ECM там много.

Там есть еще и SIQS, а не только голый ECM.

Я многое там поправил, например убрал увеличение количества проходов по кривым с ростом их номеров. Врубил также возможность перехода сразу на квадртатичное решето, что здорово экономит время. Ну и перевел с апплета на Java приложение, чтобы можно было запускать нормально, а не с сайта (Mozilla с локальной страницы апплеты не грузит). Осталось еще воткнуть сохранене уже готовых результатов при закрытии приложения, т.е. контрольную точку и вполне ничего получается.

>
> Приведу код на 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
^^^^^^^^^^

Для начала b cледует вычислять по формуле, которая в заголовке данного сообщения

А после этого лучше переходить на проективные координаты, как в усовершенствованном методе Ленстры. Там нет ни одного обратного значения по модулю и код намного короче получается. Обратный алгоритм Евклида гороздо дороже по вычислительным ресурсам нежели gcd. Он сам по себе усложненный gcd

Ну, a на десерт, не помешает добавить вторую стадию. Она более быстрая, по сравнению с первой и в некоторых случаях весьма результативная.

Пока только с первой стадией мне удавалось за несколько секунд факторизовать числа порядка 64 бит. А со второй за примерно такое же время ломаются и 128 битки.
И все таки я *решительно* не понимаю, почему не подходит ifactor/lenstra 23.02.06 20:22  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
Может я плохо объяснил с первого раза, но может это поможет:

> interface( verboseproc = 2 );
> eval(`ifactor/lenstra`);

                                  1


  proc(n)
local
i, s, prime, f, A, X, Z, rgen, sp, a, r, curves, B1, kg, kgg;
option `Copyright (c) 1990 by the University of Waterloo. A\
ll rights reserved.`;
    if nargs < 1 or 3 < nargs then
        error "wrong number of arguments."
    end if;
    if nargs < 3 then B1 := 1000000 else B1 := args[3] end if
    ;
    if nargs < 2 then curves := 30
    else curves := args[2]
    end if;
    if modp(n, 2) = 0 then return 2 end if;
    if modp(n, 3) = 0 then return 3 end if;
    s := evalf(1/2*sqrt(5) - 1/2, 30);
    A := array(1 .. curves);
    X := array(1 .. curves);
    Z := array(1 .. curves, [1 $ curves]);
    rgen := rand(1 .. n - 1);
    for i to curves do
        a := 0;
        while modp(a*(a^2 - 1)*(9*a^2 - 1), n) = 0 do
            r := rgen();
            kg := r^2 + 6;
            kgg := igcd(kg, n);
            if kgg <> 1 then return kgg end if;
            a := modp(6*r/kg, n)
        end do;
        A[i] := modp(1/16*(-3*a^4 - 6*a^2 + 1)/a^3 + 1/2, n);
        X[i] := modp(3/4*a, n)
    end do;
    prime := 2;
    while prime <= B1 do
        sp := round(s*prime);
        `ifactor/lenstra/mulpp`(1, n, A, sp, prime, B1, X, Z)
            ;
        f := Z[1];
        for i from 2 to curves do
            `ifactor/lenstra/mulpp`(i, n, A, sp, prime, B1, X,
                Z);
            f := modp(f*Z[i], n)
        end do;
        f := igcd(f, n);
        if f <> 1 then return f end if;
        prime := nextprime(prime)
    end do;
    FAIL
end proc

> eval(`ifactor/lenstra/mulpp`);

  proc(i, n, A, mm, nn, B1, X, Z)
local pow, ax, az;
option `Copyright (c) 1990 by the University of Waterloo. A\
ll rights reserved.`;
    ax := X[i];
    az := Z[i];
    pow := nn;
    while pow <= B1 do
        `ifactor/lenstra/ellmul`(n, A[i], mm, nn, ax, az,
            'ax', 'az');
        pow := pow*nn
    end do;
    X[i] := ax;
    Z[i] := az
end proc

> eval(`ifactor/lenstra/ellmul`);

  proc(n, A, mm, nn, px, pz, aax, aaz)
local ax, az, bx, bz, cx, cz, tmpx, tmpz, d, e, t1, t2;
option `Copyright (c) 1990 by the University of Waterloo. A\
ll rights reserved.`;
    cx := px;
    cz := pz;
    e := mm;
    d := nn - mm;
    if e < d then
        `ifactor/lenstra/elldoub`(n, A, px, pz, 'bx', 'bz');
        ax := px;
        az := pz;
        d := d - e
    else
        `ifactor/lenstra/elldoub`(n, A, px, pz, 'ax', 'az');
        bx := px;
        bz := pz;
        e := e - d
    end if;
    while e <> 0 do
        if e < d then
            tmpx := bx;
            tmpz := bz;
            t1 := modp((ax - az)*(bx + bz), n);
            t2 := modp((ax + az)*(bx - bz), n);
            bx := modp(cz*modp((t1 + t2)^2, n), n);
            bz := modp(cx*modp((t1 - t2)^2, n), n);
            d := d - e
        else
            tmpx := ax;
            tmpz := az;
            t1 := modp((ax - az)*(bx + bz), n);
            t2 := modp((ax + az)*(bx - bz), n);
            ax := modp(cz*modp((t1 + t2)^2, n), n);
            az := modp(cx*modp((t1 - t2)^2, n), n);
            e := e - d
        end if;
        cx := tmpx;
        cz := tmpz
    end do;
    aax := ax;
    aaz := az
end proc

> eval(`ifactor/lenstra/elldoub`);

  proc(n, A, ax, az, cx, cz)
local t1, t2;
option `Copyright (c) 1990 by the University of Waterloo. A\
ll rights reserved.`;
    t1 := modp((ax + az)^2, n);
    t2 := modp((ax - az)^2, n);
    cx := modp(t1*t2, n);
    cz := modp((t1 - t2modp(At1 - t2) + t2, n), n)
end proc

> 


---
Да, действительно. Это должно уже помочь. :) Спасибо. Хотя я... 23.02.06 21:50  
Автор: gene_green Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Может я плохо объяснил с первого раза, но может это
> поможет:


Да, действительно. Это должно уже помочь. :) Спасибо. Хотя я не уверен, что это то, что нужно. Работает-то оно куда медленнее, чем http://www.alpertron.com.ar/ECM.HTM :(
А почему ifactor/lenstra не подходит? [upd] 01.02.06 11:02  
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 01.02.06 11:09  Количество правок: 1
<"чистая" ссылка>
> Та самая, о которой говорится здесь:
> http://en.wikipedia.org/wiki/Lenstra_Elliptic_Curve_Factori
> zation

> Подскажите, пожалуйста, более детальный (с точки зрения
> программирования, скажем, на Maple (но не
> ifactor(n,lenstra)!) ) алгоритм реализации этой
> факторизации, и где можно найти уже реализованный алгоритм?

Скорее всего, она не встроенная, а посему можно посмотреть ее код
http://thproxy.jinr.ru/Documents/MapleV/qa/section3_4.html

Вместо комментариев можно использовать высокий printlevel - просто для того, чтобы посмотреть ход вычисления.
---------------

Вот то же самое, но из первых рук
http://www.maplesoft.com/support/faqs/mathematics/5.aspx
1




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


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