File tree Expand file tree Collapse file tree
Expand file tree Collapse file tree Original file line number Diff line number Diff line change 1+ # Python program to show the usage of Fermat's little theorem in a division
2+ # According to Fermat's little theorem, (a / b) mod p always equals a * (b ^ (p - 2)) mod p
3+ # Here we assume that p is a prime number, b divides a, and p doesn't divide b
4+ # Wikipedia reference: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
5+
6+
7+ def binary_exponentiation (a , n , mod ):
8+
9+ if (n == 0 ):
10+ return 1
11+
12+ elif (n % 2 == 1 ):
13+ return (binary_exponentiation (a , n - 1 , mod ) * a ) % mod
14+
15+ else :
16+ b = binary_exponentiation (a , n / 2 , mod )
17+ return (b * b ) % mod
18+
19+
20+ # a prime number
21+ p = 701
22+
23+ a = 1000000000
24+ b = 10
25+
26+ # using binary exponentiation function, O(log(p)):
27+ print ((a / b ) % p == (a * binary_exponentiation (b , p - 2 , p )) % p )
28+
29+ # using Python operators:
30+ print ((a / b ) % p == (a * b ** (p - 2 )) % p )
You can’t perform that action at this time.
0 commit comments