# Largest Prime Number in the sequence **URL:** \ **Category:** Factual Questions\ **Created:** [June 29, 2002, 2:16am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503 "2002-06-29T02:16:11Z")\ **Posts on this page:** 15\ **Page:** 4
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 4, 2002, 3:25am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/61 "2002-07-04T03:25:43Z")
Of course, it’s not like a computer program would show that it diverged–after all, it could converge to a number just slightly higher than the one you’re at now, and very slowly at that. But hey, glad to help out. ---
**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\ **Post date:** [July 4, 2002, 5:10am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/62 "2002-07-04T05:10:40Z")
The naive way of factoring, dividing a given number by all numbers less than that number, is the wrong way to do it: It’s amazingly slow as numbers get bigger, and when you’re working with cryptographically-large numbers, well, you’d be better able to wait around for the universe to decide for itself whether it’s going to collapse in on itself or die a heat death. Currently, the fastest algorithm for factoring arbitrary numbers (even really large ones, such as are used in cryptography) is known as the general number field sieve. [Here is an implementation of the sieve, which provides your best bet at factoring big numbers within your lifetime.](http://citeseer.nj.nec.com/buchmann93implementation.html) Note that while being able to factor arbitrary huge numbers (that is, huge numbers not of a special form) in a trivial amount of time would blow the lid off modern cryptography completely and provide a step towards showing that P=NP, a more effective attack on encryption lies in searching for weaknesses in the protocol using the algorithm. An insecure key-distribution method or a social-engineering weak spot (“Yes, I am with Security. Please read off your login name and password so we can determine whether or not your account has been compromised.”), for example, would provide a much more promising foothold than an attempt to rewrite complexity theory. (My source? _Applied Cryptography, Second Edition_ by Bruce Schneier, pub. John Wiley and Sons, Inc., copyright 1996 by Bruce Schneier, ISBN 0-471-11709-9, a great book to take on a transatlantic flight. 🙂 Really, it gives the C sources for nine strong encryption algorithims (including DES and RC5), plus enough information to implement any other encryption, hash, or key-generation algorithm of interest to the modern cryptographer with a knowledge of one good language. (_koff_Perl_koff_) And it has a bibliography good enough to use as a buying list for a world-class cryptography/cryptanalysis reference library. It’s good enough it’ll never be sold in North Korea or Afghanistan.) ---
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [July 4, 2002, 7:58am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/63 "2002-07-04T07:58:46Z")
> [@](#): > > \*Originally posted by ScarletSteve \* > \*\* > > A bit out of my depth here, but what I don’t understand is that surely it is relativly simple to assemble a table of all the products of (large) primes. This could then quickly give you the original primes for any encrypted message and its published product. Unless large primes are kept secret (and I assume they aren’t, but they might always be filed next to those plans for cars that run on water 🙂 > > I’m not challenging what you say, Jabba, as I have seen this explanation before in seemingly authoritative texts, but just need it explaining further. \*\* No, it’s not that easy at all. In fact, if you think it is and wanna make a few dollars at it (from $10,000 to $200,000) there’s the [RSA Cryptography Challenge](http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html) You can start with 576-bit numbers (weighing in at 174 decimal digits) and then work your way up to 2048-bit numbers (weighing in at 617 digits.) The product pq is given. Just find p and q. Currently, the highest number factored on the RSA Challenge is a 512-bit number (155 digits.) Just the sieving took them 3.7 months, using two different sieving programs. The equivalent CPU time was 35.7 years. 292 computers in all were used. Total factoring time was 5.2 months. A 140-digit number took 9 weeks to solve. This is very much an exponential slope. Adding several digits compounds the computing time astronomically. ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [July 4, 2002, 9:26am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/64 "2002-07-04T09:26:55Z")
**Chronos** & **ultrafilter** : The series of prime reciprocals diverges extremely slowly so it would take a long time even to be able to guess the limiting behaviour from a computer analysis. It can be shown that the series is asymptotically ln ln x: to get a sum greater than 5 you would need to take the primes less than 2.85_10[sup]64[/sup]; to get the sum greater than 6 you would need to go up to 1.6_10[sup]175[/sup]. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [July 4, 2002, 9:51am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/65 "2002-07-04T09:51:19Z")
I love how much information is in this thread, without even a single WAG to answer the OP. 😉 ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [July 4, 2002, 12:09pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/66 "2002-07-04T12:09:45Z")
I know, it’s becoming embarrassing, isn’t it? The best I’ve got so far is 1,999,999,973. All primes below 2\*10[sup]9[/sup] are known and this is largest such. And don’t you love the SDMB? I bet you don’t get discussions like this on AOL Chat. ---
**Author:** ![jcgmoi](https://avatars.discourse-cdn.com/v4/letter/j/a9adbd/32.png) [@jcgmoi](https://boards.straightdope.com/u/jcgmoi)\ **Post date:** [July 4, 2002, 4:02pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/67 "2002-07-04T16:02:48Z")
> [@](#): > > Originally posted by ScarletSteve > > A bit out of my depth here, but what I don’t understand is that surely it is relativly simple to assemble a table of all the products of (large) primes. This could then quickly give you the original primes for any encrypted message and its published product. Nothing wrong with this idea in theory but as a practical matter it founders on the fact that there are so damn many large primes. We can get a pretty good estimate of the number of primes \<= X using the approximation p(X) = (X/(logX - 1). I make it that there are approximately 3.88 \* 10[sup]98[/sup] 100-digit primes, so your table of products will contain about 7.5 \* 10[sup]196[/sup] entries. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [July 5, 2002, 6:19am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/68 "2002-07-05T06:19:06Z")
> [@](#): > > \*Originally posted by Joe\_Cool \* > \*\*Anyway, I see prior art: > 0 is a natural number. > Every natual number has one succsesor, which is also a natural number. \*\* So if I write this regular expression: [\s\S]\* then I have prior art on pretty much anything that will ever be written? 😉 ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [July 5, 2002, 11:34pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/69 "2002-07-05T23:34:13Z")
> [@](#): > > It can be shown that the series is asymptotically ln ln x Holy Flurking Schmidt! That’s a log _of a log_? I guess my little QBASIC program was a monumental exercise in futility. On the other hand, I _was_ only 15, so some naivety can perhaps be excused. As for the patent question, by the way: Those who have a difficult time with the idea of intellectual property rights on a number might like to consider how one could get IP rights on anything _other_ than a number. Suppose I write a novel… I can copyright that, right? But in this day and age, I’m most likely to submit that novel to a publisher in some electronic form, which means that my copyrighted work consists of a list of ones and zeros. That list of digits can, in turn, be considered a number. If it’s the size of the number that makes a difference, I suspect that there are copyrighted poems and other short works shorter than the above-mentioned patented primes. Of course, a patent is not the same thing as a copyright, but I would imagine that similar ideas would apply. ---
**Author:** ![Joe\_Cool](https://avatars.discourse-cdn.com/v4/letter/j/ecb155/32.png) [@Joe\_Cool](https://boards.straightdope.com/u/Joe_Cool)\ **Post date:** [July 6, 2002, 7:26pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/70 "2002-07-06T19:26:09Z")
> [@](#): > > \*Originally posted by Achernar \* > \*\*So if I write this regular expression: > > [\s\S]\* > > then I have prior art on pretty much anything that will ever be written? 😉 \*\* Point taken, but I still don’t buy the idea of a number being patented. “War and Peace” was created - it’s not like that work was floating around in the ether, just waiting to be discovered. Numbers exist. The large primes exist : they are found, not created or invented. Personally, I’m a math purist, in the sense that I believe numbers and their relationships ARE, whether we’re here to find them or not. Regardless of what base you express it in, [symbol]p[/symbol] is always the same quantity. Same for 1, e, and [symbol]Ö[/symbol]2. And whether we discover them or not, large primes exist. That’s like patenting a cat or a tree, just because you found it. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 6, 2002, 7:50pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/71 "2002-07-06T19:50:52Z")
> [@](#): > > \*Originally posted by Joe\_Cool \* > **Point taken, but I still don’t buy the idea of a number being patented. “War and Peace” was created - it’s not like that work was floating around in the ether, just waiting to be discovered. Numbers exist. The large primes exist : they are found, not created or invented.** Not to start a debate, but there is a (large) number which is the ASCII representation of “War and Peace”. By your reasoning, that number existed before the book was written. Also, if numbers exist independent of the human mind, then why not strings of characters? They can be defined in the same terms as numbers (FWIW, in modern math, the only things that are taken to exist are sets, and everything else is done in terms of them). Again, I don’t really want to start a debate, just to make you think a little. Do a search in GD on “patent number” and you should find something relevant. ---
**Author:** ![Joe\_Cool](https://avatars.discourse-cdn.com/v4/letter/j/ecb155/32.png) [@Joe\_Cool](https://boards.straightdope.com/u/Joe_Cool)\ **Post date:** [July 6, 2002, 8:35pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/72 "2002-07-06T20:35:16Z")
Again, I see the point you’re making, but I don’t agree. Sure, the number existed, but its mapping into language didn’t. That is, until somebody first wrote the book, then somebody else decided that numbers can represent text, then created a system to map language into numerical representation. I mean, sure, there’s also a number representing Romeo and Juliet, where everybody dies _except_ the title characters. There’s also a numerical representation of War and Peace, but with every instance of ‘the’ replaced with ‘lesbian’. That doesn’t mean that nobody has to write it to find the mapping. I guess you could call it splitting hairs, but oh well. Like I said, I get what you’re saying, I just don’t agree. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 6, 2002, 8:42pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/73 "2002-07-06T20:42:04Z")
> [@](#): > > \*Originally posted by Joe\_Cool \* > **Sure, the number existed, but its mapping into language didn’t.** Just FYI, a lot of people would disagree with this. Personally, I don’t believe that either existed independently of the human mind, but others would believe that both have always existed. Again, there’s a bunch of stuff in GD on this. ---
**Author:** ![Joe\_Cool](https://avatars.discourse-cdn.com/v4/letter/j/ecb155/32.png) [@Joe\_Cool](https://boards.straightdope.com/u/Joe_Cool)\ **Post date:** [July 7, 2002, 4:00am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/74 "2002-07-07T04:00:15Z")
Again, disagree. 🙂 I believe, as I said on the other threads, that the numbers just ARE, whether we discover them or not. Circular and linear (or very nearly so) objects exist, and regardless of whether there’s anybody in the forest to hear it fall, there is a set of points equidistant from any given point. Our method of defining, notating, and handling numbers is arbitrary and invented (as can be attested by all the different number systems that have been in use in the past), but the quantities and relationships exist in and of themselves. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [July 7, 2002, 8:23pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/75 "2002-07-07T20:23:58Z")
> [@](#): > > I mean, sure, there’s also a number representing Romeo and Juliet, where everybody dies except the title characters. There’s also a numerical representation of War and Peace, but with every instance of ‘the’ replaced with ‘lesbian’. That doesn’t mean that nobody has to write it to find the mapping. Well, yes, the numbers corresponding to those strings of text do exist, but at some point someone decided that the particular string wherein the lovers die had some value. Similarly, there are many numbers, or even prime numbers, but at some point, someone decided that that particular number had value. [Previous page](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503.md?page=3)