testing big numbers

[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?

[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.

[Prime95]

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]

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.

[Kevin]

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.

[sagan_fan]

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.

[cperciva]

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.

[sagan_fan]

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.

[ewmayer]

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.