Talk:Fermat primality test

both true

Both conditions, $1 \le a < p$ and $\operatorname{gcd}(a,p) = 1$, are true. if $a^{p-1} \equiv 1 \mod p\$ ist true, so every $(m\cdot p+a)^{p-1} \equiv 1 \mod p$ for every natural number $m\$ with $1\le m\$. So because every natural $a\$ with $1 \le a < p$ is $\operatorname{gcd}(a,p) = 1$, so is every natural number $a\$ different from prime $m\cdot p$ $a^{p-1} \equiv 1 \mod p\$. --Arbol01 00:40, 29 October 2005 (UTC)

If this is in regard to the rollback I did earlier, I did it because they broke the TeX. Anyway, whichever way looks better, go for it. CryptoDerk 00:45, 29 October 2005 (UTC)

usage section?

I believe that someone should remove the usage section because it is flat-out wrong. PGP is not a program, but rather a system for signing and encrypting information. GPG is a program that implements PGP. I have no idea what GPG uses, but an implementation of PGP, to the best of my knowledge, can use any primality checker it wants. I have not removed the section because I am not completely sure about this, and want to get it right. Does anyone else have any insight into the subject? - Alan 134.173.34.115 08:35, 25 April 2006 (UTC)

Pretty_Good_Privacy is a program. And it does indeed use the Fermat pseudo primality test to find the primes used for RSA keys. GPG is another implementation that is compatible with PGP. I.e. both programs implement the OpenPGP standard. However, in cryptographic applications the Miller-Rabin test is often prefered. See e.g. the Digital Signature Standard, FIPS PUB 186-3 (draft) Appendix D.5. 24.228.51.109 17:35, 3 September 2007 (UTC)