Euler's Theorem defines that \(a^{\phi} \equiv 1 \pmod N\), and where \(N= pq \), and \(\phi = (p-1) (q-1)\). \(N\) and \(a\) must be co-prime, and where they do not share any factors (\(gcd(N,a)=1\)) [Euler with single value]:
Euler's Theorem |
Method
Euler's formula
\(a^{\phi} \equiv 1 \pmod N\)
where \(N\) is \(p q\), and \(\phi=(p-1)(q-1)\). The values of \(a\) and \(N\) must be co-prime.
If we try a value of \(a=7\), \(p=7\) and \(q=11\), \(a\) and \(N\) are co-prime, thus the result is 1:
a= 3 p= 7 q= 11 PHI= 60 ---------- N and a are co-prime, and this should work ---------- Result of a^{PHI} (mod N)= 1
If we try a value of \(a=3\), \(p=8\) and \(q=9\), \(a\) and \(N\) are NOT co-prime, thus the result will not be 1:
a= 3 p= 8 q= 9 PHI= 56 ---------- This will not work as N and a are not co-prime ---------- Result of a^{PHI} (mod N)= 9
Code
An outline of the code used is:
import sys p=101 q=103 a=7 def gcd(a, b): while( b != 0 ): Remainder = a % b; a = b; b = Remainder; return a; N=p*q PHI=(p-1)*(q-1) res = gcd(N,a) val = a** (PHI) % N print ("a=\t",a) print ("p=\t",p) print ("q=\t",q) print ("PHI=\t",PHI) print ("----------") if (res>2): print ("This will not work as N and a are not co-prime") else: print ("N and a are co-prime, and this should work") print ("----------") print ("Result of a^{PHI} (mod N)=",val)