mersenneforum.org > Math testing big numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2002-10-06, 19:17 #1 sagan_fan   Oct 2002 23 Posts 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?
 2002-10-06, 19:25 #2 Kevin     Aug 2002 Ann Arbor, MI 1101100012 Posts 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.
 2002-10-06, 19:25 #3 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 24·17·29 Posts 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.
2002-10-06, 19:26   #4
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

24·17·29 Posts

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.

 2002-10-06, 20:13 #5 Kevin     Aug 2002 Ann Arbor, MI 1B116 Posts 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.
 2002-10-07, 08:11 #6 sagan_fan   Oct 2002 23 Posts 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.
 2002-10-07, 13:02 #7 cperciva   Oct 2002 43 Posts 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.
 2002-10-07, 19:18 #8 sagan_fan   Oct 2002 23 Posts 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.
2002-10-09, 21:20   #9
ewmayer
2ω=0

Sep 2002
República de California

32×1,303 Posts
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 &lt; 2^32 in less than hour, even
without knowing if the factors of the number have any special form.

 Similar Threads Thread Thread Starter Forum Replies Last Post sd235 Information & Answers 12 2018-12-06 17:56 Vicodin Information & Answers 21 2017-05-02 05:11 Angular GPU Computing 13 2016-08-02 12:03 eepiccolo Math 6 2006-03-28 20:53 NeoGen Software 8 2006-03-20 01:22

All times are UTC. The time now is 21:40.

Tue May 24 21:40:23 UTC 2022 up 40 days, 19:41, 0 users, load averages: 2.00, 2.18, 2.06