Talk:Fermat primality test

both true

Both conditions, $1\leq 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\leq m\$ . So because every natural $a\$ with $1\leq 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)[reply]

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)[reply]

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)[reply]

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)[reply]

simple divisibility test

Why is no stipulation made that base 'a' must not divide the 'n' being primality tested? It seems to me that a basic divisibility check would would be step one before taking exponents and doing the modulus. In fact, this simple check would eliminate most liars and all of the Carmichael numbers. 134.204.1.226 (talk) 17:32, 12 November 2021 (UTC)[reply]

Divisibility isnt what you want. A check of coprimality would be more appropriate. And there is no reason to do it. If you use a^(n-1)%n==1 youre going to fail the test whenever a is not coprime to n. Whether or not n is Carmichael. 63.40.186.52 (talk) 01:12, 17 April 2024 (UTC)[reply]