maths.fermat_little_theorem

Attributes

a
b
p

Functions

binary_exponentiation(→ int)

Calculate (a ** n) % mod using binary exponentiation, which runs in O(log n) time.

Module Contents

maths.fermat_little_theorem.binary_exponentiation(a: int, n: int, mod: int) → int

Calculate (a ** n) % mod using binary exponentiation, which runs in O(log n) time.

>>> binary_exponentiation(2, 10, 17)
4
>>> binary_exponentiation(3, 0, 5)
1
>>> binary_exponentiation(5, 3, 13)
8

maths.fermat_little_theorem.a = 1000000000

maths.fermat_little_theorem.b = 10

maths.fermat_little_theorem.p = 701