mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2002-10-06, 19:17   #1
sagan_fan
 
Oct 2002

108 Posts
Default testing big numbers

This may be the wrong place to ask, but is there some way to test a number with 10^9 digits for being prime? The number is on the form
a^(a^b) - a - 1, so its not a mersenne prime.
I realize i probably can't prove this is a prime, but maybe I can prove it being composite?
Does anybody know of any program that can test this big numbers?
sagan_fan is offline   Reply With Quote
Old 2002-10-06, 19:25   #2
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

Try the link to the Polynomial Time Algorithm of the mainpage at mersenne.org . It says that method should be able to work on numbers w/ millions of digts, though I am unaware of a program that uses it or how long it would take.
Kevin is offline   Reply With Quote
Old 2002-10-06, 19:25   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22·43·47 Posts
Default

Join the prime numbers email list at http://groups.yahoo.com/group/primenumbers/

There is no practical way to prove it prime, but they may be able to point you to some factoring programs that just might prove it composite.
Prime95 is offline   Reply With Quote
Old 2002-10-06, 19:26   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

176248 Posts
Default

Quote:
Originally Posted by Kevin
Try the link to the Polynomial Time Algorithm of the mainpage at mersenne.org . It says that method should be able to work on numbers w/ millions of digts, though I am unaware of a program that uses it or how long it would take.
That algorithm, if improved, will be able to test numbers of a few *thousand* digits.
Prime95 is offline   Reply With Quote
Old 2002-10-06, 20:13   #5
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

Oh yeah, it is thousands of digits. Sometimes I read things wrong, where I accidentally impose words from the line above the one I'm reading. So I saw the millions from what LL testing can do. Stupid, stupid me ops: . But it does seem like a type of number that should be able to be factored using special programs.
Kevin is offline   Reply With Quote
Old 2002-10-07, 08:11   #6
sagan_fan
 
Oct 2002

23 Posts
Default

Howlong time would it take to do a test using fermats little theorem with the base 2? That is calculate 2^(p-1) mod p and see if it is 1.
sagan_fan is offline   Reply With Quote
Old 2002-10-07, 13:02   #7
cperciva
 
Oct 2002

2B16 Posts
Default

A single Fermat test will take roughly the same time as the LL test. If you're not operating on Mersenne numbers, in fact, it will take somewhat longer, due to the modular arithmetic being slower.
cperciva is offline   Reply With Quote
Old 2002-10-07, 19:18   #8
sagan_fan
 
Oct 2002

23 Posts
Default

If I want to calculate 2^(p-1) mod p, i would have to do something like 10^(10^9) multiplications with 2 modulo p. Using a computer which can do 10^12 modulo multiplications per second, the operation would take:
10^(10^9) / 10^12 = 10^(10^9 - 12) = 10^999999988 s = 10^999999980,5 years.
right?
The time could be reduced a little by writing (p-1) as a binary number and squaring modulo p instead of multiplying by 2, but it would still take several millions years, so i guess i can just forget Fermat test.
sagan_fan is offline   Reply With Quote
Old 2002-10-09, 21:20   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×32×653 Posts
Default Re: testing big numbers

Quote:
Originally Posted by sagan_fan
This may be the wrong place to ask, but is there some way to test a number with 10^9 digits for being prime? The number is on the form
a^(a^b) - a - 1, so its not a mersenne prime.
I realize i probably can't prove this is a prime, but maybe I can prove it being composite?
Does anybody know of any program that can test this big numbers?
Why don't you try writing a simple sieve-based factoring program?
To test whether f divides a^x - c, we simply do a binary exponentiation
to get a^x mod f, and see if the result = c. This needs on the order of
log2(x) mod-f multiplies. If a and x fit into a computer word, on a decently
fast PC you can easily test all candidates < 2^32 in less than hour, even
without knowing if the factors of the number have any special form.
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why have ECM testing for known non-prime Mersenne numbers? sd235 Information & Answers 12 2018-12-06 17:56
Testing my numbers Vicodin Information & Answers 21 2017-05-02 05:11
Nvidia GPU for PRP testing proth numbers? Angular GPU Computing 13 2016-08-02 12:03
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53
newbie question - testing primality of very large numbers NeoGen Software 8 2006-03-20 01:22

All times are UTC. The time now is 01:56.


Sun Dec 4 01:56:51 UTC 2022 up 107 days, 23:25, 1 user, load averages: 0.62, 0.86, 0.89

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.

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