Primality Testing
Loading...
Date
2009-05
Authors
GRADINI, EGA
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Primality testing is the process to testing whether a given integer n is a prime or not
There are two types of primality tests: deterministic and probabilistic. Deterministic test
is primality test that determine with absolute certainty whether a number is prime or
not. Lucas-Lehmer test is one of the deterministic primality tests. Probabilistic test also
determine whether a given number n is a prime or not, but probabilistic test can
potentially (although with very small probability) falsely identify a composite number
as prime (not vice versa). However, they are in the general much faster than
deterministic test. Fermat test, Solovay-Strassen test, and Miller-Rabin test are some of
probabilistic primality test.
This project discusses the principles, implementation and comparisons of four primality
test; Lucas-Lehmer, Fermat, Solovay-Strassen, and Miller-Rabin test. In order to see
the differences and perform the ability of them, the algorithm of the test coded in
Mathematica (6.0 version).
Description
Keywords
Primality Testing