Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Java Tip Jan 22, 2011 - Primality Tests

  1. #1
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Java Tip Jan 22, 2011 - Primality Tests

    Introduction

    Determining if a number is prime is very important for many applications. While the main application is in cryptography, there are other applications which require prime numbers.

    Probabilistic tests are most useful for large prime numbers. Small prime numbers can be tested quickly enough using a naive primality test. The Miller-Rabin primality test is one of the most popular probabilistic tests to determine if a number is composite or probably prime.

    In this tip, code for a naive primality test as well as a Miller-Rabin primality test are provided.

    The Naive Primality Test

    The naive primality test works by testing if that number is divisible by any other number. There are 2 main optimizations which are used to speed up the primality tests:

    1. Every even integer greater than 2 is not prime.
    2. The maximum number you have to test goes up to sqrt(number).

    	/**
    	 * Uses a naive primality test
    	 * 
    	 * @param number
    	 * @return true if prime, false otherwise
    	 */
    	public static boolean naivePrime(int number)
    	{
    		if (number <= 1 || (number & 1) == 0)
    		{
    			if (number == 2)
    			{
    				return true;
    			}
    			return false;
    		}
    		int limit = (int) (Math.sqrt(number) + 1);
    		for (int i = 3; i < limit; i += 2)
    		{
    			if (number % i == 0)
    			{
    				return false;
    			}
    		}
    		return true;
    	}

    Miller-Rabin Primality Test

    The Miller-Rabin primality test works using some properties of advanced number theory which goes above a lot of other people's head (definitely above mine). If you want to learn how it works, see Wikipedia: Miller-Rabin Primality Test

    Here's the code:

    	/**
    	 * Determines if a number is probably prime using the Miller-Rabin primality
    	 * test.
    	 * 
    	 * @param number
    	 * @param iterations
    	 *            How accurate the test needs to be. Accuracy ~= 1 -
    	 *            O(4^-iterations)
    	 * @return false if definitely composite. true if probably prime.
    	 */
    	public static boolean millerRabinPrime(int number, int iterations)
    	{
    		if (number <= 1 || (number & 1) == 0)
    		{
    			if (number == 2)
    			{
    				return true;
    			}
    			// numbers less than or equal to 1 are not prime
    			// even numbers are not prime
    			return false;
    		}
    		else if (number == 3)
    		{
    			// 3 is prime
    			return true;
    		}
    		// write number - 1 as 2^s * d, with d odd by factoring powers of 2 from
    		// n-1
    		long s = 1;
    		while ((number - 1 & 1 << s) == 0)
    		{
    			++s;
    		}
    		long d = (number - 1) / (1 << s);
    		// System.out.println("2^" + s + " * " + d);
    		Random generator = new Random();
    		// if (iterations > number - 4)
    		// {
    		// iterations = number - 3;
    		// }
    		for (int i = 1; i <= iterations; ++i)
    		{
    			// pick a random integer a in the range [2, n-2]
    			long a = generator.nextInt(number - 3) + 2;
    			// test alternative: use an even a distribution
    			// long a = (number - 3) * i / iterations;
    			// compute x=a^d % number, check to see if x==1 or x==number-1
    			long x = safe_pow(a, d, number);
    			if (x == 1 || x == number - 1)
    			{
    				continue;
    			}
    			boolean gotoLoop = false;
    			for (int r = 1; r < s && !gotoLoop; ++r)
    			{
    				// x = x^2 % n
    				x = x * x % number;
    				if (x == 1)
    				{
    					return false;
    				}
    				else if (x == number - 1)
    				{
    					gotoLoop = true;
    					break;
    				}
    			}
    			if (!gotoLoop)
    			{
    				// definately composite
    				return false;
    			}
    		}
    		// probably prime
    		return true;
    	}
     
    	/**
    	 * Computes base^power % mod. Protects against over-flow
    	 * 
    	 * @param base
    	 * @param power
    	 * @param mod
    	 * @return
    	 */
    	public static long safe_pow(long base, long power, long mod)
    	{
    		if (power == 0)
    		{
    			return 1;
    		}
    		else if (power == 1)
    		{
    			return base;
    		}
    		else if ((power & 1) == 0)
    		{
    			// even power
    			// base^power % mod = ((base * base % mod) ^ (power/2)) % mod
    			return safe_pow((base * base % mod), power / 2, mod) % mod;
    		}
    		else
    		{
    			// odd
    			// base^power % mod = ((base * base % mod) ^ (power/2) * base) % mod
    			return safe_pow((base * base % mod), power / 2, mod) * base % mod;
    		}
    	}

    Performance (accuracy/speed)

    Here's a simple test rig for testing the accuracy and speed of the Miller-Rabin test vs. the naive test.

    	public static void main(String[] args)
    	{
    		long start = System.currentTimeMillis();
    		int startP = 0x0;
    		int endP = 0x1FFFFF;
    		for (int i = startP; i < endP; ++i)
    		{
    			naiveTest(i);
    		}
    		long end = System.currentTimeMillis();
    		System.out.println("Low-range Naive: " + (end - start));
    		System.out.println("Low-range Naive average: " + ((double) end - start) / (endP - startP));
    		start = System.currentTimeMillis();
    		for (int i = startP; i < endP; ++i)
    		{
    			millerRabinTest(i, 0x5);
    		}
    		end = System.currentTimeMillis();
    		System.out.println("Low-range miller-rabin: " + (end - start));
    		System.out.println("Low-range miller-rabin average: " + ((double) end - start) / (endP - startP));
    		for (int i = startP; i < endP; ++i)
    		{
    			boolean naive = naiveTest(i);
    			boolean miller = millerRabinTest(i, 0x5);
    			if (naive != miller)
    			{
    				System.out.println("inaccurate for " + i + " naive: " + naive + " miller: " + miller);
    			}
    		}
     
    		start = System.currentTimeMillis();
    		startP = 0x7FF0FFFF;
    		endP = 0x7FF2FFFF;
    		for (int i = startP; i < endP; ++i)
    		{
    			naiveTest(i);
    		}
    		end = System.currentTimeMillis();
    		System.out.println("High-range Naive: " + (end - start));
    		System.out.println("High-range Naive average: " + ((double) end - start) / (endP - startP));
    		start = System.currentTimeMillis();
    		for (int i = startP; i < endP; ++i)
    		{
    			millerRabinTest(i, 0x5);
    		}
    		end = System.currentTimeMillis();
    		System.out.println("High-range miller-rabin: " + (end - start));
    		System.out.println("High-range miller-rabin average: " + ((double) end - start) / (endP - startP));
    		for (int i = startP; i < endP; ++i)
    		{
    			boolean naive = naiveTest(i);
    			boolean miller = millerRabinTest(i, 0x5);
    			if (naive != miller)
    			{
    				System.out.println("inaccurate for " + i + " naive: " + naive + " miller: " + miller);
    			}
    		}
    	}

    This tests numbers in the low range (0-2097151) and numbers in the high range (2146500607-2146631679)
    Running the test, I got the following results (your results may vary, times are in milliseconds):

    Low-range Naive: 573
    Low-range Naive average: 2.732278219355688E-4
    Low-range miller-rabin: 1487
    Low-range miller-rabin average: 7.090571923528635E-4
    High-range Naive: 1015
    High-range Naive average: 0.00774383544921875
    High-range miller-rabin: 142
    High-range miller-rabin average: 0.0010833740234375

    A summary of these results:

    For small numbers, using the Naive test is faster (~3 times faster). Even so, the Miller-Rabin test was able to test small numbers quickly and efficiently. The interesting results are those for large numbers. The Miller-Rabin test was ~7 times faster for moderately large numbers. To put this into perspective:
    Generally for cryptography, most algorithms use ~256 bits or more. Here do the limitations of how I implemented the algorithm, we only have 32 bits (technically 31 because Java doesn't let you have unsigned values). These performance gains will grow exponentially with with larger and larger numbers. Just for fun, I ran the Miller-Rabin test for the full range of all integers (0 to 2^31-1) and it took 34.44 minutes. I didn't want to run the same range using the Naive test, but using the above results I think it's reasonable to conclude that it would have taken ~4 hours to complete that test.

    So how does the Miller-Rabin test fair on accuracy?
    1. If the test marks a number composite, it is composite (no questions asked).
    2. The theoretical chance that it will incorrectly guess that a number is prime is 4^(-k), where k is the number of iterations. It's difficult to derive a direct k-value from my code because I used a random number generator and didn't check for duplicates. However, for large numbers being tested, it's reasonable to conclude that the k-value is ~5 for the parameters I used. This results in a theoretical chance of incorrectly labeling something as prime at 0.09765625%. In practice, this chance is actually a lot smaller. I have been able to run this code over billions, perhaps even trillions of numbers and have yet to encounter the algorithm labeling the number as prime incorrectly.

    Conclusion

    In conclusion, I hope this code will be useful to someone (likely just as a reference). The major pit-fall of this code is that it doesn't support big integers. There is also one major speed improvement that can be made, and that's replacing the current integer power code with a FFT (Fast-Fourier Transform) algorithm. This last suggestion can speed up the algorithm by an order of magnitude.

    The default Java BigInteger class also supports a probabilistic primality test (likely implemented using the Solovay-Strassen primality test). This test has the problem of having an accuracy of 2^-k. While still quite good, it's not nearly as good as the the Miller-Rabin test. Also, the Miller-Rabin test will never incorrectly label composite numbers while the Solovay-Strassen test has a chance of incorrectly labeling prime or composite numbers. I believe both tests have the same running time if comparing to my implementation. I'm not sure if the Solovay-Strassen could also use a FFT to improve it's performance, though I wouldn't doubt it.

    Happy coding
    Last edited by helloworld922; February 7th, 2011 at 09:46 PM.

  2. The Following User Says Thank You to helloworld922 For This Useful Post:

    ChristopherLowe (January 3rd, 2012)


  3. #2
    Junior Member
    Join Date
    Apr 2011
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Java Tip Jan 22, 2011 - Primality Tests

    Please let me know if you get a chance to check algorithm of FFT Prime test. Thanks

  4. #3
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Java Tip Jan 22, 2011 - Primality Tests

    In this case, there's no point because I'm able to compute the exponentiation in O(log(n)), and from what I understand about FFT's, we're both using similar methods (divide & conquer). Also, for other math operations, the hardware is always going to be faster than anything I can write in software.

    However, in http://www.javaprogrammingforums.com...primality.html, I implemented the same algorithm using Java's BigInteger class. I can't remember exactly what algorithm they use internally for multiplication/division/exponentiation, but I believe they do it naively, which is O(n^2), where-as a FFT is O(n log(n)), which is considerably faster (for longer numbers, at least).

Similar Threads

  1. ROBOTIX 2011:Robotics competition in India
    By roobokgp in forum The Cafe
    Replies: 2
    Last Post: November 21st, 2013, 05:21 AM