20021006, 19:17  #1 
Oct 2002
2^{3} 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? 
20021006, 19:25  #2 
Aug 2002
Ann Arbor, MI
110110001_{2} 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.

20021006, 19:25  #3 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{4}·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. 
20021006, 19:26  #4  
P90 years forever!
Aug 2002
Yeehaw, FL
2^{4}·17·29 Posts 
Quote:


20021006, 20:13  #5 
Aug 2002
Ann Arbor, MI
1B1_{16} 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.

20021007, 08:11  #6 
Oct 2002
2^{3} Posts 
Howlong time would it take to do a test using fermats little theorem with the base 2? That is calculate 2^(p1) mod p and see if it is 1.

20021007, 13:02  #7 
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.

20021007, 19:18  #8 
Oct 2002
2^{3} Posts 
If I want to calculate 2^(p1) 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 (p1) 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. 
20021009, 21:20  #9  
∂^{2}ω=0
Sep 2002
República de California
3^{2}×1,303 Posts 
Re: testing big numbers
Quote:
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) modf 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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Why have ECM testing for known nonprime Mersenne numbers?  sd235  Information & Answers  12  20181206 17:56 
Testing my numbers  Vicodin  Information & Answers  21  20170502 05:11 
Nvidia GPU for PRP testing proth numbers?  Angular  GPU Computing  13  20160802 12:03 
Speed of P1 testing vs. Trial Factoring testing  eepiccolo  Math  6  20060328 20:53 
newbie question  testing primality of very large numbers  NeoGen  Software  8  20060320 01:22 