On Fri, Jun 05, 2009 at 03:52:07PM +0800, jaze lee wrote:
> hello,
> when i read some books about cryptography, it always go that the
> cryptography is based on the difficult math problem, for example big
> integer decomposition,
> i don't understand it, for if we know that n = p*q , p, q are prime ,
> why it's difficult to get p and q ? i think ,if we know the big
> integer and it is mul of two prime number. we can get prime number
> and test whether p*q == n,
The basis for thinking this is easy is ignorance of the details of how you
would go about it. So, to understand why it is not easy, take some time to
write a program to factor a 68-bit composite number, which is well within
reach of sophisticated factoring algorithms, but once you understand
how those work, you'll probably learn why 1024-bits is (still) not easy.
Your challenge is to write your own code to factor:
248911498900030209107
Good luck.
[ The "Wolfram Alpha" computational search engine, factors this in under
a second. Code that posts a query to a public "oracle" such this does
not count. ]
> why people say it 's a difficult problem?
> may be my understanding is not right? someone who knows please tell me,
> thank you very much
Too many candidate prime number factors to test directly, all known
"sieving methods" that reduce the cost by eliminating "impossible"
candidates have non-polynomial run-time in the bit size of the primes
and have very high memory costs to combine all the sieving information.
The first modern sieve appears in C.F. Gausses "Disquisitiones
arithmeticae", and makes use of quadratic reciprocity to constrain
the candidate prime factors modulo manageably small primes if
the composite number is not very large.
--
Viktor.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager majord...@openssl.org
