2009/6/7 Victor Duchovni <victor.ducho...@morganstanley.com>:
> On Sun, Jun 07, 2009 at 09:51:14AM +0800, jaze lee wrote:
>
>> The problem is we can not find the function yet ? or some other ways
>> to judge a big integer whether it's a prime. Is it so-called
>> mathematics problem that many cipher based on it ?
>
> No answer to your questions beyond "it's magic, trust me" will be any
> more illuminating or convincing, unless you are willing to spend the
> time and learn at least some of the mathematics involved or at least try
> to write code so you can gauge the effectiveness of naive (not based on
> advanced mathematics) approaches.
i know , thank you
>
> A reasonably effective algorithm (for medium size composites such as
> the one I posted) is described on Wikipedia:
>
> http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
>
> This has run-time O(n^(1/4)) rather than naive division, which runs in
> O(n^(1/2)). So for a 68-bit number, naive division takes O(2^34) steps
> (with each step burning multiple CPU cycles to do bignum divisions),
> while "Pollard's rho" takes O(2^17) steps, which is entirely practical.
>
> Of course even for 512-bit RSA, Pollard's rho takes O(2^128) steps,
> which is entirely impractical, while GNFS breaks 512-bit RSA on realistic
> compute farms...
>
> Naive division is "exponential" running time O(2^(n/2)) for n-bit moduli.
>
> Pollard's rho is still "exponential" running time O(2^(n/4)) for n-bit moduli.
>
> Lenstra's ECM:
> http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization
> is sub-exponential, and fastest known for numbers with at least one "small"
> prime factor. It will handle my and significantly larger problems much
> faster than Pollard's rho. Not easy to explain to non-experts, implementations
> are not too difficult, even if you don't understand the theory.
>
> GNFS is "sub-exponential" with run-time O(2^(C*n^(1/3)*log(n)^(2/3))),
> which is exponential, not in "n", but the cube-root of "n". Sadly,
> GNFS is not easy to explain, and not very easy to implement. Factoring
> is still (via this best known algorithm for numbers with large factors)
> a difficult problem.
>
> No proof is known that better algorithms won't come along, but for now
> state of the-art number theory gives us GNFS.
>
> --
> Viktor.
> ______________________________________________________________________
> OpenSSL Project http://www.openssl.org
> User Support Mailing List openssl-us...@openssl.org
> Automated List Manager majord...@openssl.org
>
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager majord...@openssl.org
