On Sat, Jun 06, 2009 at 04:58:24AM -0500, Michael S. Zick wrote:
> DAQ1: How many integer numbers are there? (an uncountable value)
Not "uncountable", countably infinite.
> DAQ2: How many after we throw away all the even ones? (an uncountable value)
Ditto.
> 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)
Ditto, and in modern definitions of "prime", 1 is not a prime, it is a
"unit".
> 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).
This is far from obvious at first glance:
<http://en.wikipedia.org/wiki/Bertrand%27s_postulate>
> Modern, computerized, studies place the smallest number for which pc(x) >
> Li(x)
> is true at about 1.397*10^316.
This is a coincidence, we use 1024-bit RSA moduli because 512-bit
is within the range of GNFS, but 1024 has not been, although by now
applications with strong (beyond "commercial") security requirements
should be moving to 2048 bits. This is unrelated to prime counting.
The GNFS does not use any trial divisions, and so the number of primes
to try is not directly pertinent.
> 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.
Since primality testing is slower than division, in practice, with naive
trial division, one would divide by every number of the form 6n+/-1
if one wanted brute force, and would not bother to find out which are
prime. The extra factor of ln(sqrt(N)) in the number of divisions is
not significant relative to the cost of primality tests.
--
Viktor.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager majord...@openssl.org
