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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
А почему ifactor/lenstra не подходит? [upd] 01.02.06 11:02  Число просмотров: 4471
Автор: 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
<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-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach