#14MediumCryptography· Modular Exponentiation

Diffie-Hellman Key Agreement

Two parties agree on a public prime `p` and a public generator `g`. Alice picks a private exponent `a` and Bob picks a private exponent `b`. 1. Alice publishes `A = g^a mod p`. 2. Bob publishes `B = g^b mod p`. 3. Alice computes `B^a mod p` and Bob computes `A^b mod p`. Both equal `g^(a*b) mod p`, the shared secret. Return the shared secret. Exponents are as large as 10^9, so repeated multiplication is far too slow: implement **fast modular exponentiation** (square-and-multiply) yourself rather than calling a built-in power function.

Input format

p: prime modulus, g: generator, a: Alice's private exponent, b: Bob's private exponent

Output format

Integer: the shared secret `g^(a*b) mod p`

Examples

Input: p = 23, g = 5, a = 6, b = 15

Output: 2

A = 5^6 mod 23 = 8 and B = 5^15 mod 23 = 19. Alice computes 19^6 mod 23 = 2 and Bob computes 8^15 mod 23 = 2.

Input: p = 101, g = 2, a = 50, b = 2

Output: 1

The secret is 2^100 mod 101. By Fermat's little theorem 2^100 = 1 (mod 101).

Constraints

3 <= p <= 2^31 - 1, and p is prime
2 <= g <= p - 1
1 <= a, b <= 10^9

Study first

#cryptography
#math
#modular-exponentiation
#number-theory