COMPARISON STUDY OF FERMAT, SOLOVAY-STRASSEN AND MILLER-RABIN PRIMALITY TEST USING MATHEMATICA 6.0
Abstract
This paper presents three primality tests; Fermat test, Solovay-Strassen test, and Rabin-Miller test. Mathematica software is used to carry out the primality tests. The application of Fermat’s Litle Theorem as well as Euler’s Theorem on the tests was also discussed and this leads to the concept of pseudoprime. This paper is also discussed some results on pseudoprimes with certain range and do quantitative comparison. Those primality tests need to be evaluated in terms of its ability to compute as well as correctness in determining primality of given numbers. The answer to this is to create a source codes for those tests and evaluate them by using Mathematica 6.0. Those are Miller-Rabin test, Solovay-Strassen test, Fermat test and Lucas-Lehmer test. Each test was coded using an algorithm derived from number theoretic theorems and coded using the Mathematica version 6.0. Miller-Rabin test, SolovayStrassen test, and Fermat test are probabilistic tests since they cannot certainly identify the given number is prime, sometimes they fail. Using Mathematica 6.0, comparison study of primality test has been made and given the Miller- Rabin test as the most powerful test than other.
Downloads
References
Agrawal, Maninda & Kayal, Neeraj & Saxena, Nitin. (2003). Prime is in P. http://www.csc.iitk.ac.in/news/primality-v3.ps
Anderson, James A & Bell, James M. (1996). Number Theory with application. New Jersey: Prentice Hall
Bektas, Attila. (2005). Probabilistic Primality Test. Master’s thesis. The middle East Technical University.
Borneman, Kristen.(2007). Mersenne Primes and Lucas-Lehmer Test. [on-line], http://www.mattfind.com/Lucas-Lehmer test for mersenne primes.
Burton, David M.(2002). Elementary Number Theory. 5th edn. New York: McGraw Hill.
Ega, Gradini, Project report of MSc in Teaching of Mathematics, Universiti Sains Malaysia, 2009.
Jones, Gareth A & Jones, Mary J. (1998). Elementary Number Theory. London: SpringerVerlag.
Kumandari, Ramanujachary & Romero,Christina. (1998). Number Theory with Computer Application. New Jersey: Prentice- Hall.
Mollin, Richard A. (1998). Fundamental Number Theory with application. Florida: CRC Press.
Yan,Song, Y. (2000). Number Theory for computing. New York: Springer-Verlag. [11] Weis stein, Eric W. (2009).
Rabin-Miller Strong Pseudoprime Test. [online], http://mathworld.wolfram.com/RabinMillerStrong PseudoprimeTest.htm1
Abstract views: 182
PDF downloads: 363
