IsPrime (Algorithm)

IsPrime

Testing for an integer's primality[1]. Is a given integer a prime number or not?

Agrawal–Kayal–Saxena (AKS)[2]

The algorithm was the first to determine whether any given number is prime or composite within polynomial time.

Visual Studio 2010 C++ Implementation

First, what is the largest int used in VS C++?[3]

Constant	Comment	Value
ULLONG_MAX	Maximum value for a variable of type unsigned long long	18446744073709551615 (0xffffffffffffffff)

Or 18,446,744,073,709,551,615 for an unsigned long long. But this won't work because library functions like log and pow only take a double. So back to using the long int, \( \pm \)2,147,483,647. A practical implementation for cryptographic purposes requires a Big Number solution.

• Removed all the unsinged and replaced with long. This eliminates errors due to casting.

• Step 5. Figure out how to implement Euler's totient function[4] of r. Using this implementation[5]

Now for using polynomial libraries in C/C++. The GNU Scientific Library (GSL)[6] performs polynomial operations and is reliable. Now to install it.

Internal Links

Parent Article: Algorithms (Advanced)