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.
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-users@openssl.org
Automated List Manager majord...@openssl.org
