Fermat's Little TheoremFermat's Little Theorem shows that \(a^{p-1}\mod(p)=1\), and is at the core of the RSA public key method (where a and p must have no common factors apart from 1 - this defined as the greatest common denominator: gcd(a,p)=1). p is a prime number: |
Examples
The following are some examples:
- a=6, p=7. Try
- a=12, p=17. Try
- a=21, p=31. Try
- a=21, p=22 (will not work as p is not prime). Try
- a=25, p=41. Try
- a=50, p=10 [will work as gcd(50,10)=1]. Try
Code
The following is an outline of the code:
public string fermatcalc(uint a, uint p) { Microsoft.SolverFoundation.Common.BigInteger aval,pval, res=0; string result = ""; try { aval = (Microsoft.SolverFoundation.Common.BigInteger)a; pval = (Microsoft.SolverFoundation.Common.BigInteger)p; res = Microsoft.SolverFoundation.Common.BigInteger.Power(aval, pval-1); result = "a^(p-1) gives " + res.ToString() + "\n"; Microsoft.SolverFoundation.Common.BigInteger q; Microsoft.SolverFoundation.Common.BigInteger.DivMod(res, pval, out q, out res); result += "a^(p-1) mod 1 gives " + res.ToString() + "\n"; } catch (Exception ex) { ViewData["encrypted"] = "Something went wrong!"; } return (result); }
And here is the Python code:
import sys a=13 p=71 def gcd(a, b): while b: a, b = b, a%b return a print "a=",a print "p=",p print "GCD(a,p)=",gcd(a,p) print "Result: ",(a**(p-1)) % p