🚀 go-pugleaf

In article <9208101729.AA24006@gandalf.ssw.com> rjl@GANDALF.SSW.COM (Robert J Leone) writes:
:In an encyclopedia reference on RSA, it mentioned using values around 10**75
:for p and q. One question (and please excuse my possible mathematical
:naivete):
:  Does anyone here have a feel for how sparse primes are in the range
:10**75 to 10**76? In other words, is it computationally feasible to
:compile a table of primes


You last sentence was left incomplete. If you are asking whether one
could compile all the 75 digit primes, the answer is: not in the
lifetime of this universe.

Near 75 digits approximately 1 in every 172.7 integers is prime, so there
are approximately 5.79 x 10^72  75-digit primes.

If you want to compile a table of *some* 75 digit primes, then the answer
to your question is yes. Finding and proving 75-digit primes is trivial.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"

rjl@GANDALF.SSW.COM (Robert J Leone) writes:

>In an encyclopedia reference on RSA, it mentioned using values around 10**75
>for p and q. One question (and please excuse my possible mathematical
>naivete):
>  Does anyone here have a feel for how sparse primes are in the range
>10**75 to 10**76? In other words, is it computationally feasible to
>compile a table of primes

In my humble excursions into this arena, I've noticed that primes are roughly
11% of the numbers of x digits in length.  Is it feasible to compile a table
of primes? Sure.  But it's gonna be one heck of a list.  The number of primes
is not infinite (I'm probably going to get flamed on that remark).

In article <9208101729.AA24006@gandalf.ssw.com> rjl@GANDALF.SSW.COM (Robert J  
Leone) writes:
> In an encyclopedia reference on RSA, it mentioned using values around 10**75
> for p and q. One question (and please excuse my possible mathematical
> naivete):
>   Does anyone here have a feel for how sparse primes are in the range
> 10**75 to 10**76? In other words, is it computationally feasible to
> compile a table of primes

The prime number theorem tells us that there are approximately N/log(N) primes
less then N. So in the range from 10**75 to 10**76 there are approximately
         (10**76)/log(10**76) - (10**75)/log(10**75) = 5*(10**73) 
primes. If you arrange one prime in a line and 50 lines on a
page, the table is a book of 10**72 pages. I think these is more pages then the
number of atoms in the universe.
--
Prof. Dr. Klaus Pommerening                                                     
Institut fuer Medizinische Statistik und Dokumentation                          
der Johannes-Gutenberg-Universitaet                                             
Obere Zahlbacher Strasse 69, W-6500 Mainz                                                                    

>
>In my humble excursions into this arena, I've noticed that primes are roughly
>11% of the numbers of x digits in length.  Is it feasible to compile a table
>of primes? Sure.  But it's gonna be one heck of a list.  The number of primes
>is not infinite (I'm probably going to get flamed on that remark).

A reasonably accurate and easy to remember approximation for the fraction
of numbers that are prime for a given size is 1/n where n is the number
of bits in the number.  So for example for numbers around 10 bits long
11% is not a bad approximation but for numbers 100 bits long it is
terrible.

I am going to give you a change to back out gracefully here:  When
you said the number of primes was not infinite did you mean the total
number of primes or the number of primes in a given range.  (Hint:
answer the latter and you can more or less save face :-).

Jimmy
jru@Comtech.com
n

In article <1557@anagld.analytics.com> sammy@anagld.analytics.com (Sam Blackburn) writes:
>rjl@GANDALF.SSW.COM (Robert J Leone) writes:
>
>>In an encyclopedia reference on RSA, it mentioned using values around 10**75
>>for p and q. One question (and please excuse my possible mathematical
>>naivete):
>>  Does anyone here have a feel for how sparse primes are in the range
>>10**75 to 10**76? In other words, is it computationally feasible to
>>compile a table of primes
>
>In my humble excursions into this arena, I've noticed that primes are roughly
>11% of the numbers of x digits in length.  Is it feasible to compile a table
>of primes? Sure.  But it's gonna be one heck of a list.  The number of primes
>is not infinite (I'm probably going to get flamed on that remark).


No personal flame intended but you should study your subject before shooting
your mouth off. At the very least you should read the first few chapters of
ANY number theory book.

(1) Primes are NOT 11% of the numbers of x digits. They have asymptotic
density ZERO. For primes near 10^75, their density is about .58%

(2) It is NOT feasible to compile such a list.

(3) Where in ****** did you get the crazy idea that the number of primes
is finite? 
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"

In article <1557@anagld.analytics.com> sammy@anagld.analytics.com (Sam Blackburn) writes:

>In my humble excursions into this arena, I've noticed that primes are roughly
>11% of the numbers of x digits in length.  Is it feasible to compile a table
>of primes? Sure.  But it's gonna be one heck of a list.  The number of primes
>is not infinite (I'm probably going to get flamed on that remark).

Flamed? FLAMED? Why, what was the last time anyone on the net was
flamed for being ignorant? :-)

OK, so that this is not just a flame, he're your quick proof (is this
by Euclid?)

Proof that for any number N, there exists a prime larger than N:

Consider N!+1. Now, N!+1 does not have any divisors less than or equal
to N. Therefore, either N!+1 is itself prime, or it has a (prime)
divisor that's larger than N. In either case, there does exist a prime
larger than N, for all N, and therefore the number of primes is infinite. QED.

/ji

PS: Someone else give the proof on the density of primes... my number
theory is rusty at best, and it's too early in the morning anyway.

In-Real-Life: John "Heldenprogrammer" Ioannidis
E-Mail-To: ji@cs.columbia.edu
V-Mail-To: +1 212 854 8120
P-Mail-To: 450 Computer Science \n Columbia University \n New York, NY 10027

sammy@anagld.analytics.com (Sam Blackburn) writes:
>                                               The number of primes
>is not infinite (I'm probably going to get flamed on that remark).

Our Internet link went down shortly after this article arrived, so
I'm probably not the first to remind you of Euclid's proof that there
is no largest prime number, and therefore the number of primes IS
indeed infinite.                -- George Mitchell (george@tessi.com)

ji@cs.columbia.edu (John Ioannidis) writes:

>Flamed? FLAMED? Why, what was the last time anyone on the net was
>flamed for being ignorant? :-)

Ignorance is curable, stupidity is not. :-)

In article <Bstqr2.Lxq@cs.columbia.edu> ji@cs.columbia.edu (John Ioannidis) writes:
>In article <1557@anagld.analytics.com> sammy@anagld.analytics.com (Sam Blackburn) writes:
>
>>In my humble excursions into this arena, I've noticed that primes are roughly
>>11% of the numbers of x digits in length.  Is it feasible to compile a table
>>of primes? Sure.  But it's gonna be one heck of a list.  The number of primes
>>is not infinite (I'm probably going to get flamed on that remark).
>
>Flamed? FLAMED? Why, what was the last time anyone on the net was
>flamed for being ignorant? :-)
>

Several people have jumped on "The number of primes is not infinite" statment,
which clearly is flammable by itself.

In the context of the original message though, I believe the poster meant
"The number of primes of exactly 10**75 digits (or perhaps of
10**(75+/-3) digits) is not infinite."  This number may be more than the
number of atoms in the universe, but it *is* finite.


-- 
   Dave Kemp   dpkemp@afterlife.ncsc.mil 
-----------------------------------------------------------------------------
"The use of history as therapy means the corruption of history as history."
    -- Arthur Schlesinger          (quote stolen from Chet Ramey, CWRU)

In article <Bstqr2.Lxq@cs.columbia.edu>, ji@cs.columbia.edu (John Ioannidis) writes:
.
. stuff deleted
.
> OK, so that this is not just a flame, he're your quick proof (is this
> by Euclid?)
.
. proof deleted
.
You must notice, that there exists a small community (even with
mathematicians among them) which does not believe in inductive
proofs. I think, they have a lot of problems with commonly
accepted theorems.

(I do _not_ belong to this group!!!)

Uli


-- 
Ulrich Graef        |  analog (phone) :  +49 6155 62493           
Lichtenbergweg 11   |  digital (Email): graef@hrz.th-darmstadt.de 
D-W-6103 Griesheim  +--------------------------------------------
Germany             |  Nothing is real, look into your mirror!

graef@rs5.hrz.th-darmstadt.de (Ulrich Graef) writes:

>You must notice, that there exists a small community (even with
>mathematicians among them) which does not believe in inductive
>proofs. I think, they have a lot of problems with commonly
>accepted theorems.

Whoa!  Euclid's proof does not involve induction!  It is a
reductio ad absurdum proof, which shows that the premise:

   Assume that there is a largest prime n.

leads to a contradiction, and therefore the premise cannot be true.

You are correct that some people worry about inductive proofs, but
their worries fortunately do not apply here.

George Mitchell (george@tessi.com)

In article <1992Aug12.171656.8755@tessi.com>, george@tessi.com (George Mitchell) writes:
> graef@rs5.hrz.th-darmstadt.de (Ulrich Graef) writes:
> 
> >You must notice, that there exists a small community (even with
> >mathematicians among them) which does not believe in inductive
> >proofs. I think, they have a lot of problems with commonly
> >accepted theorems.
> 
> Whoa!  Euclid's proof does not involve induction!  It is a
> reductio ad absurdum proof, ...

You are right, but I only use the wrong words (english is not
my native language). There is also a group, which worries
about `reductio ad absurdum' proofs.

A friend of mine worry about both!!!

Uli


-- 
Ulrich Graef        |  analog (phone) :  +49 6155 62493           
Lichtenbergweg 11   |  digital (Email): graef@hrz.th-darmstadt.de 
D-W-6103 Griesheim  +--------------------------------------------
Germany             |  Nothing is real, look into your mirror!

graef@rs5.hrz.th-darmstadt.de (Ulrich Graef) writes:
>[ . . . ] There is also a group, which worries
>about `reductio ad absurdum' proofs.

I would recommend that anyone worried about the rigor of reductio
ad absurdum enter a field of study other than mathematics.
-- George Mitchell (george@tessi.com)