Power with modular exponentiation

Iterative Function to calculate (b^n) % m in O(log n)

( ^ ) %

Calculate

Output:

Greatest Common Divisor

Using the Euclidean approach

Two numbers are coprime if GCD is 1

1: 2:

Calculate

Output:

Fermat's Little Theorem

if p is a prime number, and a is an integer, then

a^p = a % p

a^(p-1) = 1 % p

a: p:

Calculate

Output:

RSA

Choose two prime numbers p and q

p: q:

Calculate

n = p * q =

φ(n) = (p-1) * (q-1) =

Choose e such that 1 < e < φ(n) and e and φ(n) are coprime

e:

Calculate

Compute a value for d such that d * e = 1 % φ(n)

Checking d: 0

d:

Calculate Keys

Public key is (e, n) =>

Private key is (d, n) =>

Message m:

Encrypt M

Encrypted c = (m^e) % n =

Encrypted cessage c:

Decrypt C

Decrypted m = (c^d) % n =