http://www.exampleproblems.com/wiki/index.php?title=Fermat_primality_test&feed=atom&action=history Fermat primality test - Revision history 2022-08-10T07:42:26Z Revision history for this page on the wiki MediaWiki 1.33.0 http://www.exampleproblems.com/wiki/index.php?title=Fermat_primality_test&diff=35052&oldid=prev Todd at 10:28, 28 March 2006 2006-03-28T10:28:11Z <p></p> <p><b>New page</b></p><div>The '''Fermat primality test''' is a [[randomized algorithm|probabilistic]] test to determine if a number is composite or ''probably'' prime. <br /> <br /> ==Concept== <br /> [[Fermat's little theorem]] states that if ''p'' is prime and &lt;math&gt;1 \le a &lt; p&lt;/math&gt;, then <br /> <br /> :&lt;math&gt;a^{p-1} \equiv 1 \pmod{p}&lt;/math&gt;.<br /> <br /> If we want to test if ''n'' is prime, then we can pick random ''a'''s in the interval and see if the equality holds. If the equality does not hold for a value of ''a'', then ''n'' is composite. If the equality does hold for many values of ''a'', then we can say that ''n'' is probably prime, or a [[pseudoprime]].<br /> <br /> It may be in our tests that we do not pick any value for ''a'' such that the equality fails. Any ''a'' such that <br /> <br /> :&lt;math&gt;a^{n-1} \equiv 1 \pmod{n}&lt;/math&gt;<br /> <br /> when ''n'' is composite is known as a ''Fermat liar''. If we do pick an ''a'' such that <br /> <br /> :&lt;math&gt;a^{n-1} \not\equiv 1 \pmod{n}&lt;/math&gt;<br /> <br /> then ''a'' is known as a ''Fermat witness'' for the compositeness of ''n''.<br /> <br /> ==Algorithm and running time==<br /> The algorithm can be written as follows:<br /> :'''Inputs''': ''n'': a value to test for primality; ''k'': a parameter that determines the number of times to test for primality<br /> :'''Output''': &lt;u&gt;composite&lt;/u&gt; if ''n'' is composite, otherwise &lt;u&gt;probably prime&lt;/u&gt;<br /> :repeat ''k'' times:<br /> ::pick ''a'' randomly in the range [1, ''n'' &amp;minus; 1]<br /> ::if ''a''&lt;sup&gt;''n'' &amp;minus; 1&lt;/sup&gt; mod ''n'' &amp;#8800; 1 then return &lt;u&gt;composite&lt;/u&gt;<br /> :return &lt;u&gt;probably prime&lt;/u&gt;<br /> <br /> Using fast algorithms for [[modular exponentiation]], the running time of this algorithm is O(''k'' &amp;times; log&lt;sup&gt;3&lt;/sup&gt;''n''), where ''k'' is the number of times we test a random ''a'', and ''n'' is the value we want to test for primality.<br /> <br /> ==Flaws==<br /> There are certain values of ''n'' known as [[Carmichael number]]s for which &lt;u&gt;all&lt;/u&gt; values of ''a'' for which gcd(a,n)=1 are Fermat liars. Although Carmichael numbers are rare, there are enough of them that Fermat's primality test is often not used in favor of other [[primality test]]s such as [[Miller-Rabin primality test|Miller-Rabin]] and [[Solovay-Strassen primality test|Solovay-Strassen]].<br /> <br /> In general, if ''n'' is not a Carmichael number then at least half of all<br /> <br /> :&lt;math&gt;a\in(\mathbb{Z}/n\mathbb{Z})^*&lt;/math&gt;<br /> <br /> are Fermat witnesses. For proof of this let ''a'' be a Fermat witness and ''a''&lt;sub&gt;1&lt;/sub&gt;, ''a''&lt;sub&gt;2&lt;/sub&gt;, ..., ''a''&lt;sub&gt;''s''&lt;/sub&gt; be Fermat liars. Then <br /> <br /> :&lt;math&gt;(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}&lt;/math&gt;<br /> <br /> and so all ''a'' &amp;times; ''a''&lt;sub&gt;i&lt;/sub&gt; for ''i'' = 1, 2, ..., ''s'' are Fermat witnesses.<br /> <br /> ==Usage==<br /> The encryption program [[PGP]] uses this primality test in its algorithms.<br /> <br /> ==References==<br /> <br /> * [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Pages 889&amp;ndash;890 of section 31.8, Primality testing.<br /> <br /> [[Category:primality tests]]<br /> [[Category:modular arithmetic]]</div> Todd