rwm: I thought the
primes page was getting too crowded so I added this as a new page. My intent on adding this was to help teach the math and provide a simple Tcl implementation of the algorithm. (It might belong in a cookbook of useful recipes??)
Warning - It only checks 'a'=2 which will include some 'liars'. It could be changed to check other a values as well.
References:
- http://en.wikipedia.org/wiki/Fermat_primality_test
Dependencies:
- binaryModExpo - a modular exponentiation function (I like the one at the bottom of RSA in Tcl)
proc primeCheckFermat {p} {
## based on fermats little theorem
## a**(p-1) == 1
## for a in the interval [1,p-1]
if {[binaryModExpo 2 $p $p] == 2} {
# possible prime (or fermat liar)
return 1
} else {
#puts stderr "failed fermat check ..."
# not possible
return 0
}
}
