On Sat June 6 2009, jaze lee wrote: > > i still not understand the problem. although i don''t get the result. >
Q1: Why is this problem "hard" - as in: "computationally hard" ? A1: There are two many number trials (computations) required in a "cryptographically hard" number. True, for any brute force approach. My apologies in advance to any and all mathematicians reading this... ;) Q2: But is it all that hard for something other than "brute force"? Q3: Where did that "approximately 300 decimal digits" come from? Actually, 10^316 is the better approximation of "cryptographically hard" as will be seen shortly. Hyp1: We want to give up on any "try each number computationally" (brute force). Q4: If we don't try all numbers (in a range), how do we know when (if) we have found all of the prime numbers in that range? We can throw out the obvious and those that violate the definition of prime. Numbers divisible by 1 don't matter - that divisor is allowed by definition. Like, all even numbers (they are divisible by 2) - DAQ1: How many integer numbers are there? (an uncountable value) DAQ2: How many after we throw away all the even ones? (an uncountable value) Obviously, this isn't leading to a simplification of the problem; re-think... List the first few prime numbers, just so they are in front of us: 1, 2, 3, 5, 7, 11, 13 ... to (an uncountable value - see: DAQ1 & DAQ2) Q5: Is there some way to know how many prime numbers there are, less than x? Ans: Yes, several of them - within limitations. We know from above that there must be at least one prime number between 13 (the largest we know of) and twice that number (26). If we know that it is not practical to test each number, then whatever means we use, we have to know when to stop trying (because we found them all). Enter here, the: "Prime Number Theorem" (google it). and the "prime counting function" [I'll write: pc(x)]. The first approximation found for pc(x) was: x div (Ln(x) Carl Gauss found a 'better' approximation for pc(x) was: Li(x) So now our problem is: find all primes between 13..26, stop when we have found: pc(26) - pc(13) new primes. Use whatever search and trial method you like - with modern 32bit and 64bit integer machines common, you can have a lot of fun finding primes and learning ways to search for them. You know you could try a modified, binary search for one. Q6: But will this approach always work? A6: No. (I almost had you, didn't I?) Google: "Skewes' number" That is the smallest, natural, number for which: pc(x) is approximately: Li(x) is false. In fact, pc(x) > Li(x) is true (by definition of a Skewes Number). So if we can't pre-determine how many prime numbers there is in the range we are considering, how do we know when to stop looking? Modern, computerized, studies place the smallest number for which pc(x) > Li(x) is true at about 1.397*10^316. A1..5: One workable (layman's) definition of "cryptographically hard" (10^316). I.E: Any method you come up with for your prime-finding will fail, since you don't know how many primes there are in that range, you don't know when to stop "prime-finding", hence you have to test them all (brute force, again). And we are already agreed that brute force is not practical. Hope this helps (and that true mathematicians don't black-ball me from the ml). Mike ______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List openssl-users@openssl.org Automated List Manager majord...@openssl.org
