kobakhit/eulerprimalitytest

Primality test that uses Euler's criterion in javascript

EulerPrimalityTest

This repo contains codes for computing the Jacobi symbol and executing the Solovay-Strassen primality test to which I refer as Euler Primality test because it uses the Euler criterion.

JacobiSymbol.js and JacobiSymbol1.js are two different ways of computing the Jacobi symbol in javascript.

JacobiSymbol.js code was developed by Fred Richman. I retrieved and modified the code from: http://math.fau.edu/richman/

JacobiSymbol1.js code was developed by Peter Strandmark in Matlab language. I retrieved, converted to javascipt, and modified the code from: http://www.mathworks.com/matlabcentral/fileexchange/24672-jacobi-and-legendre-symbol/content/jacobi.m

Euler's criterion

The primality test that uses Euler's criterion:

For an integer and an odd integer , where ,

                                             If then is probably prime.

If is composite, then there exists at least one integer such that the congruence relation does not hold.

isEulerPrime.js is the code for Euler's primality test. First, the program randomly picks base . Second, for a potential odd prime number it computes the , and then determines whether is congruent to . If the congruence relationship holds then is probably prime. If it does not than is composite. For prime numbers the congruence relation holds for all integers between 1 and the prime number. For non prime odd numbers the relation does not hold for some integers between 1 and the non prime number, but for some it does. As a result, the accuracy of the test increases as you try several distinct bases ,i.e. integers between 1 and the odd number you check for primality. . If you check all bases from 1 to that is all numbers in the range and the aforementioned congruence relation holds for every number then is certainly prime. If the relation fails at least once then is composite.

Example

(Add example here)

Computation power problem

isPrimeEuler.js highly depends on the computation power of your machine. When checking a double digit odd number, for example 97, for primality you will encounter computation power problem unless you are using the appropriate hardware. The problem is in the code raising integers between 1 and the odd integer you are checking, 97 in our case, to a high power. For instance letting our base be 11 we get which is a number with 50 digits. It is unlikely that a laptop or a desktop will be able to store each digit in memory. Instead some digits will be discarded and the result of the test will be misleading. Using my 2013 macbook pro, and restricting the range of bases to (1,5) I was able to correctly get prime numbers up to 67. Beyond that my memory was not enough to carry out the test.