how to test a prime number 1000 digits long?

Question

I am trying to find whether number is prime or not for 1000 digit long. Algorithm i am thinking to use is 6k+/-1

problem i am facing is how can i store such a long number in java, it is taken string as input.

or

for doing divisibility should is consider only the last few digits of the number.

please advise

Answer 1

You can use some ideas toghether.

• The algorith 6k +/-1
• Checking until divisor is less than sqrt(prime)
• Checking dividing only by primes

Combining those methods you can speed up a lot your validation.

This link can help you: http://www.osix.net/modules/article/?id=791

And of course use BigInteger.

Answer 2

6k +/- 1 is not a primality test! If you already know the number Q is prime (and greater than 7), knowing that it's of the form 6k +/- 1 tells you whether it's "safe" -- that Q+1 and Q-1 will both have large factors, making Q more difficult to factor (thus "safe" for cryptographic purposes). But most numbers of the form 6k +/- 1 will be composite.

"Safe Prime" page from Wikipedia

If want to write your own routine for testing 1000 digit numbers for primality, you'll want to use the BigInteger class as the other answers have suggested. You could use the Fermat test first, which will tell you if the number is "definitely composite" or "probably prime". You could then use a more computationally intensive test like Miller-Rabin or Solovay-Strassen on the "probably prime" numbers for the final definitive test.

Primality testing algorithms from Wikipedia

Answer 3

BigInteger