Java Reference
In-Depth Information
1
/**
2
* Private method that implements the basic primality test.
3
* If witness does not return 1, n is definitely composite.
4
* Do this by computing a^i (mod n) and looking for
5
* nontrivial square roots of 1 along the way.
6
*/
7
private static long witness( long a, long i, long n )
8
{
9
if( i == 0 )
10
return 1;
11
12
long x = witness( a, i / 2, n );
13
if( x == 0 ) // If n is recursively composite, stop
14
return 0;
15
16
// n is not prime if we find a nontrivial square root of 1
17
long y = ( x * x ) % n;
18
if( y == 1 && x != 1 && x != n - 1 )
19
return 0;
20
21
if( i % 2 != 0 )
22
y = ( a * y ) % n;
23
24
return y;
25
}
26
27
/**
28
* The number of witnesses queried in randomized primality test.
29
*/
30
public static final int TRIALS = 5;
31
32
/**
33
* Randomized primality test.
34
* Adjust TRIALS to increase confidence level.
35
* @param n the number to test.
36
* @return if false, n is definitely not prime.
37
* If true, n is probably prime.
38
*/
39
public static boolean isPrime( long n )
40
{
41
Random r = new Random( );
42
43
for( int counter = 0; counter < TRIALS; counter++ )
44
if( witness( r.nextInt( (int) n - 3 ) + 2, n - 1, n ) != 1 )
45
return false;
46
47
return true;
48
}
figure 9.9
A randomized test for primality
Search WWH ::
Custom Search