4

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

harshit
  • 7,925
  • 23
  • 70
  • 97
  • Do you have the CPU power to do that? It is not an easy task. – backslash17 Aug 15 '09 at 16:42
  • 3
    You might want to consider using software that already exists to perform this computation. There is no sense reinventing the wheel if you can avoid it, and chances are that the preexisting software will out perform something of your own concoction. – Nixuz Aug 15 '09 at 17:03
  • 1
    6k +/- 1 will tell you if it is NOT prime quickly, or if it MIGHT be prime. Example: k=6, 35 is not prime. However 723 == 3 (mod 6) is quickly determined not to be prime. You still need a prime test if n == +-1 (mod 6) – maxwellb Aug 15 '09 at 17:13

9 Answers9

13

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.
Chi
  • 22,624
  • 6
  • 36
  • 37
  • 1
    Hmmm. Am I the only one who finds it extremely disturbing that the javadoc for the probable-prime methods of BigInteger does not include documentation on which algorithm is used? – Jason S Aug 17 '09 at 13:27
  • 3
    @Jason - why does that disturb you? The purpose of javadoc is to help users of the API know how to use it, not to expose internal implementation details. The details are quite clearly spelled out in the source code. – CPerkins Sep 17 '09 at 14:36
  • The function works wonderfully and fast, I used it along with gcd() to constantly factor a rational class that stored two BigInts to make a rational number with infinite precision. It was always fast enough to execute some pretty big calculations--even when it was operations on two small matrices composed of Imaginary numbers each composed of two BigRational numbers--most operations were still nearly instantaneous from the users point of view. – Bill K Mar 08 '12 at 17:46
  • [Here is the OpenJDK implementation for BigInteger#isProbablePrime(int certainty)](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/math/BigInteger.java#BigInteger.isProbablePrime%28int%29). It calls the package-private method `primeToCertainty(int certainty, Random random)`, which then uses `passesMillerRabin(rounds, random)` and `passesLucasLehmer();`. That should give you some clues :) – Håvard Geithus Jul 31 '12 at 18:46
11

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.

Sam Harwell
  • 97,721
  • 20
  • 209
  • 280
  • 3
    Note that Java's isProbablePrime(int) uses Miller/Rabin- and Lucas/Lehmer algorithms. – Bart Kiers Aug 15 '09 at 21:04
  • 1
    @Bart: where is that documented? – Jason S Aug 17 '09 at 13:28
  • @JasonS - Its mentioned in the comments just above the source code of the function :) – xkcd Feb 15 '16 at 18:10
  • @xkcd -- that's not documentation. (and really, you just responded to a six-and-a-half-year-old comment?) You have to look into the implementation-dependent source code to see it. (e.g. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/math/BigInteger.java#840 and the private `passesMillerRabin` and `passesLucasLehmer` methods. – Jason S Feb 15 '16 at 18:45
7

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.

AlBlue
  • 23,254
  • 14
  • 71
  • 91
3

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

Jim Lewis
  • 43,505
  • 7
  • 82
  • 96
  • 1
    All primes greater than three are of the form 6k +/- 1. You are correct in that it is not a test for primality, but it is a valid, and reasonably fast test against primality. if (p-1) % 6 ! 0 and (p+1) % 6 != 0 then the number is not prime. Yes, it generates a lot of false positives, but it doesn't generate any false negatives. – Chris Cudmore Nov 22 '11 at 15:05
2

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.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
1

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.

yairchu
  • 23,680
  • 7
  • 69
  • 109
0

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.

backslash17
  • 5,300
  • 4
  • 31
  • 46
0

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!"

Þorvaldur Rúnarsson
  • 879
  • 7
  • 15
0

I think you can use BigInteger for really large numbers.

However, one thing you should note that all numbers that are in the format 6k+1 are primes. For example 

when k=341,
6k +1 = 6(341) +1 = 2046 + 1= 2047

Now 2047 can be divided by 23 like so

2047/23 = 89

Thus it might not be great to use when generating prime numbers

Chidiebere
  • 1,051
  • 1
  • 13
  • 14