NTTL Function - IsPrime

Parameters

Name	Type	Description
X	T	The number being tested.
security	size_t	The number of trials of the probabilistic algorithm to be performed. Increasing this parameter decreases the chance of a composite being reported as prime, but also increases the running time of the algorithm. The default value of this parameter is 20.

Returns: ( bool ) If this function returns false, then the number X is composite with high probability. If it returns true, then X is prime with high probability. More precisely, high probability means at least (1 - (1/2)^security) . If you are testing random large numbers for primality, then the probability of error is actually much closer to 0. If you are testing a number of unknown procedence (e.g. given to you by some adversary in an e-commerce application), then you have to decide whether a probability of error of (1/2)^20 is acceptable. If not, simply increase the value of the security parameter. WARNING We have chosen to return true on input 1. It is not clear to us why the number 1 is not considered a prime. It looks really prime to us. True, the wording of the some statements (e.g. unique factorization) has to be slightly altered. However, other statements become easier. It also makes for cleaner code in many applications.

Example

#include <nttl/isPrime.h>
...
if( IsPrime( 1239873, 20 ) )
   cout << "It is prime!" << endl;

Algorithm: <Find a reference to the algorithm. Describe it, along with error probability.>