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

A 1000 digit number uses less than 350 bytes of memory with BigDecimal. You should find you can handle numbers much larger than this.

The problem you will find is that you need to check alot of numbers, about 10^31 which will take a long time, about 10^18 years.

Answer 2

You should use a Lucas pseudoprime test and a Rabin-Miller strong pseudoprime test in bases 2 and 3. If all three give a result of probably prime, then for all practical reasons you should consider it so. There are no known counterexamples to this test. If you have to generate a certificate of primality, then you could use an elliptic curve primality prover, but it will be tremendously slower.

Answer 3

You should use BigInteger if you need to deal with ints outside the 32/64-bit space. Don't know whether there's practical limits on that that you'll need to worry about.

Answer 4

In case you don't like the probabilistic methods, there is a deterministic polynomial algorithm available as well.

But unless a deity is playing with the odds and pulling your leg or something, you should probably just use the probabilistic methods, which are faster.

Answer 5

If it is sufficient to determine whether or not a number is PROBABLY prime, you can use the built in isProbablePrime function

• if the call returns true, the probability that the number is prime exceeds (1 - 1/(2^certainty)).
• If the call returns false, the number is definately not prime.

Answer 6

if your not looking for a programmable method you should maybe just ask wolframalpha

f.x: "is 1754179634151752538176965974334085811645204614256364837827967 a prime"

returns: "1754179634151752538176965974334085811645204614256364837827967 is a prime!"