Because you have a scientific calculator on your PC, manual calculations aren't necessary. Try decrypting the ciphertext on the next page.

Wow. Even with small primes like 7 and 13, we ended up having to do a lot of calculation. If you have a PC, it can be pretty fun using the calculator functions X^Y and MOD. (Choose the Scientific Calculator option from the calculator's menu.)

p=7, q=13, n=91, phi(n)=72. We have x^11 mod 91 = 5. Since phi(n)=72, we'll find the private key of 11 by computing a in 11a+72b=1, and we have a=59. Then we have x mod 91 = 5^59, and calculate x mod 91 = 73.

[What is RSA Cryptography?] RSA Cryptography is an example of a Public Key Cryptographical Algorithm, where two extremely large prime numbers p and q are used. In order for the sender and receiver to communicate with each other, the sender calculates pq = n. We have a message x, and phi(n)=(p-1)(q-1). We choose public key e such that e is coprime with phi(n), and compute ciphertext x^e. The only information available to the sender is the message x, public key e, and n. The receiver has a private key d such that ed mod phi(n) = 1, and raise the ciphertext to its dth power (according to Euler's Theorem, x^(ed) mod n = x) to obtain the original plaintext. Since phi(n) can be obtained easily by factoring n through heuristics, in practice extremely large numbers of p and q (2048-bit long) are used to prevent the factorizaion from being completed in a practical timeframe. This is how RSA stays secure. Let's see an example with some really small prime numbers.

Column [RSA Cryptography] Today I'll be the instructor. Number theory has a large number of practical applications. For example, number theory is an important member in cryptography. I'll introduce that with an example.