/*
 * Copyright (C) 1995, 1996 Systemics Ltd (http://www.systemics.com/)
 * All rights reserved.
 */

package cryptix.math;

import java.io.PrintStream;

/**
 *
 * This function tests the primality of a BigIntegers.
 *
 * <p>Copyright (C) 1995, 1996 Systemics Ltd (http://www.systemics.com/)
 * All rights reserved.
 */
public class TestPrime
{
	public static final boolean
	hasSmallFactor( BigInteger n )
	{
		return hasSmallFactor( n, null );
	}

	public static final boolean
	hasSmallFactor( BigInteger n, TestPrimeObserver obsrv )
	{
		BigInteger r = new BigInteger();
		BigInteger f = new BigInteger();
		for( int i = 0, len = primes.length; i < len; i++ )
		{
			f.assign( primes[i] );
			if (r.mod(n, f).cmp(BigInteger.zero) == 0)
			{
				signalObserver( obsrv, TestPrimeObserver.HAS_SMALL_FACTORS );
				return true;
			}
		}
		signalObserver( obsrv, TestPrimeObserver.NO_SMALL_FACTORS );
		return false;
	}
	
	public static boolean
	isPrime( BigInteger p )
	{
		return isPrime( p, null );
	}

	public static boolean
	isPrime( BigInteger p, TestPrimeObserver obsrv )
	{
		if ( hasSmallFactor( p, obsrv ) )
			return false;
		BigInteger p1 = new BigInteger().sub( p, BigInteger.one );
		BigInteger r = new BigInteger();
		BigInteger x = new BigInteger();

		for ( int i =0; i < 4; i++ )
		{
			// if ((x ^ (p-1)) % p) != 1 then p isn't prime
			x.assign( primes[i] );
			BigNum.modExp( r, x, p1, p );
			if ( r.cmp( BigInteger.one ) != 0 )
			{
				signalObserver( obsrv, TestPrimeObserver.NOT_PRIME );
				return false;
			}
		}
		signalObserver( obsrv, TestPrimeObserver.IS_PRIME );
		return true;
	}

	private static final void
	signalObserver( TestPrimeObserver obsrv, int signalValue )
	{
		if ( obsrv != null )
			obsrv.handleEvent( signalValue );
	}
	
	private static final int primes[] =
	{
		   2,   3,   5,   7,  11,  13,  17,  19,
		  23,  29,  31,  37,  41,  43,  47,  53,
		  59,  61,  67,  71,  73,  79,  83,  89,
		  97, 101, 103, 107, 109, 113, 127, 131,
		 137, 139, 149, 151, 157, 163, 167, 173,
		 179, 181, 191, 193, 197, 199, 211, 223,
		 227, 229, 233, 239, 241, 251, 257, 263,
		 269, 271, 277, 281, 283, 293, 307, 311,
		 313, 317, 331, 337, 347, 349, 353, 359,
		 367, 373, 379, 383, 389, 397, 401, 409,
		 419, 421, 431, 433, 439, 443, 449, 457,
		 461, 463, 467, 479, 487, 491, 499, 503,
		 509, 521, 523, 541, 547, 557, 563, 569,
		 571, 577, 587, 593, 599, 601, 607, 613,
		 617, 619, 631, 641, 643, 647, 653, 659,
		 661, 673, 677, 683, 691, 701, 709, 719,
		 727, 733, 739, 743, 751, 757, 761, 769,
		 773, 787, 797, 809, 811, 821, 823, 827,
		 829, 839, 853, 857, 859, 863, 877, 881,
		 883, 887, 907, 911, 919, 929, 937, 941,
		 947, 953, 967, 971, 977, 983, 991, 997,
		1009,1013,1019,1021,1031,1033,1039,1049,
		1051,1061,1063,1069,1087,1091,1093,1097,
		1103,1109,1117,1123,1129,1151,1153,1163,
		1171,1181,1187,1193,1201,1213,1217,1223,
		1229,1231,1237,1249,1259,1277,1279,1283,
		1289,1291,1297,1301,1303,1307,1319,1321,
		1327,1361,1367,1373,1381,1399,1409,1423,
		1427,1429,1433,1439,1447,1451,1453,1459,
		1471,1481,1483,1487,1489,1493,1499,1511,
		1523,1531,1543,1549,1553,1559,1567,1571,
		1579,1583,1597,1601,1607,1609,1613,1619,
		1621,1627,1637,1657,1663,1667,1669,1693,
		1697,1699,1709,1721,1723,1733,1741,1747,
		1753,1759,1777,1783,1787,1789,1801,1811,
		1823,1831,1847,1861,1867,1871,1873,1877,
		1879,1889,1901,1907,1913,1931,1933,1949,
		1951,1973,1979,1987,1993,1997,1999,2003,
		2011,2017,2027,2029,2039,2053,2063,2069,
		2081,2083,2087,2089,2099,2111,2113,2129,
		2131,2137,2141,2143,2153,2161,2179,2203,
		2207,2213,2221,2237,2239,2243,2251,2267,
		2269,2273,2281,2287,2293,2297,2309,2311,
		2333,2339,2341,2347,2351,2357,2371,2377,
		2381,2383,2389,2393,2399,2411,2417,2423,
		2437,2441,2447,2459,2467,2473,2477,2503,
		2521,2531,2539,2543,2549,2551,2557,2579,
		2591,2593,2609,2617,2621,2633,2647,2657,
		2659,2663,2671,2677,2683,2687,2689,2693,
		2699,2707,2711,2713,2719,2729,2731,2741,
		2749,2753,2767,2777,2789,2791,2797,2801,
		2803,2819,2833,2837,2843,2851,2857,2861,
		2879,2887,2897,2903,2909,2917,2927,2939,
		2953,2957,2963,2969,2971,2999,3001,3011,
		3019,3023,3037,3041,3049,3061,3067,3079,
		3083,3089,3109,3119,3121,3137,3163,3167,
		3169,3181,3187,3191,3203,3209,3217,3221,
		3229,3251,3253,3257,3259,3271,3299,3301,
		3307,3313,3319,3323,3329,3331,3343,3347,
		3359,3361,3371,3373,3389,3391,3407,3413,
		3433,3449,3457,3461,3463,3467,3469,3491,
		3499,3511,3517,3527,3529,3533,3539,3541,
		3547,3557,3559,3571,3581,3583,3593,3607,
		3613,3617,3623,3631,3637,3643,3659,3671,
		3673,3677,3691,3697,3701,3709,3719,3727,
		3733,3739,3761,3767,3769,3779,3793,3797,
		3803,3821,3823,3833,3847,3851,3853,3863,
		3877,3881,3889,3907,3911,3917,3919,3923,
		3929,3931,3943,3947,3967,3989,4001,4003,
		4007,4013,4019,4021,4027,4049,4051,4057,
		4073,4079,4091,4093,4099,4111,4127,4129,
		4133,4139,4153,4157,4159,4177,4201,4211,
		4217,4219,4229,4231,4241,4243,4253,4259,
		4261,4271,4273,4283,4289,4297,4327,4337,
		4339,4349,4357,4363,4373,4391,4397,4409,
		4421,4423,4441,4447,4451,4457,4463,4481,
		4483,4493,4507,4513,4517,4519,4523,4547,
		4549,4561,4567,4583,4591,4597,4603,4621,
		4637,4639,4643,4649,4651,4657,4663,4673,
		4679,4691,4703,4721,4723,4729,4733,4751,
		4759,4783,4787,4789,4793,4799,4801,4813,
		4817,4831,4861,4871,4877,4889,4903,4909,
		4919,4931,4933,4937,4943,4951,4957,4967,
		4969,4973,4987,4993,4999,5003,5009,5011,
		5021,5023,5039,5051,5059,5077,5081,5087,
		5099,5101,5107,5113,5119,5147,5153,5167,
		5171,5179,5189,5197,5209,5227,5231,5233,
		5237,5261,5273,5279,5281,5297,5303,5309,
		5323,5333,5347,5351,5381,5387,5393,5399,
		5407,5413,5417,5419,5431,5437,5441,5443,
		5449,5471,5477,5479,5483,5501,5503,5507,
		5519,5521,5527,5531,5557,5563,5569,5573,
		5581,5591,5623,5639,5641,5647,5651,5653,
		5657,5659,5669,5683,5689,5693,5701,5711,
		5717,5737,5741,5743,5749,5779,5783,5791,
		5801,5807,5813,5821,5827,5839,5843,5849,
		5851,5857,5861,5867,5869,5879,5881,5897,
		5903,5923,5927,5939,5953,5981,5987,6007,
		6011,6029,6037,6043,6047,6053,6067,6073,
		6079,6089,6091,6101,6113,6121,6131,6133,
		6143,6151,6163,6173,6197,6199,6203,6211,
		6217,6221,6229,6247,6257,6263,6269,6271,
		6277,6287,6299,6301,6311,6317,6323,6329,
		6337,6343,6353,6359,6361,6367,6373,6379,
		6389,6397,6421,6427,6449,6451,6469,6473,
		6481,6491,6521,6529,6547,6551,6553,6563,
		6569,6571,6577,6581,6599,6607,6619,6637,
		6653,6659,6661,6673,6679,6689,6691,6701,
		6703,6709,6719,6733,6737,6761,6763,6779,
		6781,6791,6793,6803,6823,6827,6829,6833,
		6841,6857,6863,6869,6871,6883,6899,6907,
		6911,6917,6947,6949,6959,6961,6967,6971,
		6977,6983,6991,6997,7001,7013,7019,7027,
		7039,7043,7057,7069,7079,7103,7109,7121,
		7127,7129,7151,7159,7177,7187,7193,7207,
		7211,7213,7219,7229,7237,7243,7247,7253,
		7283,7297,7307,7309,7321,7331,7333,7349,
		7351,7369,7393,7411,7417,7433,7451,7457,
		7459,7477,7481,7487,7489,7499,7507,7517,
		7523,7529,7537,7541,7547,7549,7559,7561,
		7573,7577,7583,7589,7591,7603,7607,7621,
		7639,7643,7649,7669,7673,7681,7687,7691,
		7699,7703,7717,7723,7727,7741,7753,7757,
		7759,7789,7793,7817,7823,7829,7841,7853,
		7867,7873,7877,7879,7883,7901,7907,7919,
		7927,7933,7937,7949,7951,7963,7993,8009,
		8011,8017,8039,8053,8059,8069,8081,8087,
		8089,8093,8101,8111,8117,8123,8147,8161
	};


	//
	//	Test code
	//
	public static void
	main(String argv[])
	{
		try {
			self_test(System.out, argv);
		}
		catch(Throwable t)
		{
			t.printStackTrace();
		}
	}

	public static void
	self_test(PrintStream out, String argv[])
	throws Exception
	{
		BigInteger i;

		i = new BigInteger(34567);
		if (!hasSmallFactor(i)) { out.println("test 1 failed"); }

		i = new BigInteger(76543);
		if (hasSmallFactor(i)) { out.println("test 2 failed"); }

		i.fromString("D9BEAD898AAB1AEE84D7E1740C63D293D30689FE7F2CA169");
		if (isPrime(i)) { out.println("test 3 failed"); }
		i.inc(); i.inc();
		if (!isPrime(i)) { out.println("test 4 failed"); }
		i.inc(); i.inc();
		if (isPrime(i)) { out.println("test 5 failed"); }

		i.fromString("F3F075C82B5CEB105103ABDFF97545CEDAB935B47FA68FFF");
		if (isPrime(i)) { out.println("test 6 failed"); }
		i.inc(); i.inc();
		if (!isPrime(i)) { out.println("test 7 failed"); }
		i.inc(); i.inc();
		if (isPrime(i)) { out.println("test 8 failed"); }
	}
}