mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Billion Digits

Reply
 
Thread Tools
Old 2008-09-14, 19:15   #1
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52·17 Posts
Default Billion digit prime?

Actually factoring might find a billion digit prime! It is highly improbable but if a mersenne number has just two factors and we find the small one, its relatively easy to figure out if the big one is prime.

Well by relatively easy, perhaps I am mistaken. Even a Rabin-Miller probable prime test is slower than a LL test for mersennes. Not sure how much slower it is tho.

Ok. it is a long shot and maybe not worth even thinking about. First to get a billion digit prime this way we would need to start with billion plus 100 digit mersenne numbers so that the large factor would still be a billion digits long.

Last fiddled with by lfm on 2008-09-14 at 19:29
lfm is offline   Reply With Quote
Old 2008-09-14, 19:25   #2
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

12EB16 Posts
Default

Quote:
Originally Posted by lfm View Post
Actually factoring might find a billion digit prime! It is highly improbable but if a mersenne number has just two factors and we find the small one, its relativly easy to figure out if the big one is prime.

Ok. it is a long shot and maybe not worth even thinking about. First to get a billion digit prime this way we should start with billion plus 100 digit mersenne numbers so that the large factor would still be a billion digits long.
Don't even think about it
Checking primality of such number by trial-division would take forever, even a Lucas-Lehmer test would take more than 850 years (without finding factors).

And primality checking of a number with no particular notation (as would be the bigger factor) is actually limited to 15.000 digits by actual software (multicore Primo), while we had at least a 500.000.000 digits number.

Luigi

Last fiddled with by ET_ on 2008-09-14 at 19:27
ET_ is offline   Reply With Quote
Old 2008-09-14, 19:44   #3
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52×17 Posts
Default

"multicore primo" I can't find what this is. Could you tell me more about it? Or where to find more about it?

Its ok, I found it. It seems it no longer holds the record. See:
http://www.ellipsa.net/public/primo/...Multiprocessor

the "distributed ecpp" has a 20k digit prime proved. Still no help to us of course.

Another consideration is the odds that the two factors would be so lop sided. The vast majority of two factor composites will have two large factors. It would be like the odds of finding a 77 digit or smaller number out of random 500 million digit numbers.

Last fiddled with by lfm on 2008-09-14 at 20:03
lfm is offline   Reply With Quote
Old 2008-09-14, 20:30   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2·3·23·31 Posts
Default

Regardless of the exact method used on numbers of no specific form (e.g. the larger of the two in what you're referring to), factoring LL numbers (with an efficient algorithm) is faster. Fully factoring an LL number with the algorithm in Prime95, for instance, with >1B digits would take an impossibly long amount of time (as in, an enormous supercomputer that pushes the limits of theoretical possible speed would take billions of years to factor it).

Last fiddled with by Mini-Geek on 2008-09-14 at 20:31
Mini-Geek is online now   Reply With Quote
Old 2009-01-05, 14:37   #5
joblack
 
joblack's Avatar
 
Oct 2008
n00bville

2×367 Posts
Default

Quote:
Originally Posted by ET_ View Post
Don't even think about it
Checking primality of such number by trial-division would take forever, even a Lucas-Lehmer test would take more than 850 years (without finding factors).
Could you elaborate the 850 years? With a Quad Q6600 (4 x 3 GhZ) a 560M number would need estimated 11 years (checked with Prime95).
joblack is offline   Reply With Quote
Old 2009-01-05, 14:50   #6
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

29×167 Posts
Default

Quote:
Originally Posted by joblack View Post
Could you elaborate the 850 years? With a Quad Q6600 (4 x 3 GhZ) a 560M number would need estimated 11 years (checked with Prime95).
850 years of Pentium 4, maybe the site is outdated

Anyway billion digits numbers start at about 3321928097, twice a 560 Million digits number. I hope that you did not take 560M as the exponent (i.e. 2^560000000-1), because this way a billion digit number would be six time in size.

Add that doubling the exponent would require about 4*time to finish, and you're done: 11 years * 3.2 (4 threaded CPU ecfficiency) * 6 (= 3.3G/560M) * 4 (time factor), you get 844.8 years...

Luigi
ET_ is offline   Reply With Quote
Old 2009-01-07, 01:17   #7
joblack
 
joblack's Avatar
 
Oct 2008
n00bville

2×367 Posts
Default

Quote:
Originally Posted by ET_ View Post
850 years of Pentium 4, maybe the site is outdated

Anyway billion digits numbers start at about 3321928097, twice a 560 Million digits number. I hope that you did not take 560M as the exponent (i.e. 2^560000000-1), because this way a billion digit number would be six time in size.
Luigi
Damned you´re absolutely right ...
joblack is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really. CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55
The "one billion minus 999,994,000" digits prime number a1call Miscellaneous Math 179 2015-11-12 14:59
question range 1 billion to 2 billion? Unregistered Information & Answers 7 2010-08-12 06:25
Lucas test for billion bit prime MESCALINE1968 Lone Mersenne Hunters 2 2005-06-06 22:06
10 digit prime in e TTn 15k Search 15 2004-10-18 03:11

All times are UTC. The time now is 22:28.


Mon Sep 26 22:28:49 UTC 2022 up 39 days, 19:57, 0 users, load averages: 1.52, 1.40, 1.50

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔