2009/6/6 Michael S. Zick <open...@morethan.org>: > 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). That is , n = q*p , we can choose the prime has given bits, but we can not know all that prime in that range.if we want to know the range , we should test it every odd number in that range, or should find a function that can do the job efficiently . 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 ?
> > Mike > > > > > ______________________________________________________________________ > 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
