> 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, 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
Okay, let's look at 'n' for a second. Both 'p' and 'q' are roughly of the order of magnitude of the square root of 'n'. A typical 'n' might be 600 digits, so 'p' and 'q' are roughly 300 digits long each (express in base 10). Let's assume you could test, say, a hundred billion 'p'/'p' values in a second. Well, you do the math and you get over 10^100 billion years expected time to find the answer. This is a simple and naive analysis, and doubtless there are faster algorithms than trying every value. But even if you assume some brilliant algorithm makes the process 100 billion billion times faster, it's still over 10^100 billion years. This is hardly anything remotely resembling a formal proof, of course. But it should give you the basic idea -- it's a difficult problem because the numbers are big. DS ______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List openssl-users@openssl.org Automated List Manager majord...@openssl.org
