This lesson's interactive features are locked, please to keep using them

Totient and E

Now that we have p, q and n, we need to calculate:

The totient of n, which we'll call tot.
A random number that is relatively prime to tot, which we'll call e

The public key for RSA encryption is the pair of numbers: (n, e)

The Totient Function (Phi)

Euler's totient function counts the positive integers up to a given integer, n in our case, that are relatively prime to it.

In other words, the totient is the number of integers between 1 and n whose greatest common divisor is 1.

tot = ϕ(n) = (p - 1) * (q - 1)

Remember p and q are prime, which means their totient's are just p-1 and q-1. Because we know n = p * q, we know the totient of n is (p - 1) * (q - 1).

e

e is a random number between 1 and tot that is relatively prime to tot. This means that the greatest common divisor of e and tot is 1.

Assignment

Complete the getTot and getE functions.

func getTot(p, q *big.Int) *big.Int

Use the math/big package to calculate (p-1)(q-1) and return it as a pointer to a big.Int. This is the "totient" of n, which we can also call "phi of n", or ϕ(n).

func getE(tot *big.Int) *big.Int

Use the math/big package to generate a random number e that adheres to the following constraints:

e is greater than 1
e is less than tot
e and tot have a greatest common divisor of 1

The gcd function is provided for you. It calculates the greatest common divisor of two big ints.

Generate random e values in the range of [2, tot) until you find one that satisfies the constraints. Use crand.Int with the globally provided randReader to generate random big ints. You'll need to do some manual arithmetic to get the range you want because crand.Int only generates random numbers in the range of [0, max)