We write words using letter of the alphabet. Our messages are sent as numbers. We need to have some method of translating (encoding) text to numbers, and untranslating (decoding) numbers back to text.
Be sure to Evaluate this code:
Here is an overview:
q. These numbers must remain your secret.
nwill be a public number, but keep
e to be some number, less than
n and relatively prime to
e will be your public key.
e is the name of an positive integer that will be used for encyrption, not the irrational e.)
e is coprime (another word for relatively prime) to
phi, there is an integer
f such that
$$e \cdot f \equiv 1 \bmod(\phi(n))$$
Be sure to keep
f a secret.
Note: Dr Crisman (the author of NTIC) uses
f for the secret key exponent. Many authors use
d, for decryption
You'll need two large primes p and q that are never revealed.
Now choose a value for
e. It will need to be relatively prime to
phi. This code will check that.
We're ready to try encoding a message, but we need to check that the encoded message is less than
We need f the multiplicative inverse of e \bmod \phi(n)
Recall that the Sage command
gis the gcd(a, b)
vare the coefficients in the linear combination:
Take a look at:
xgcd(e,phi) in the next cell to find f
You can test you result here:
Finally, let's see ...: