Unit 5: The RSA Cryptosystem and Factoring Integers
In this unit, we will learn the basic idea behind public key cryptography and explain in detail RSA as the most important example of public key cryptography. Next, we will discuss the algorithms used to determine whether an input number is prime. As noted earlier, these algorithms are important in public key cryptography because encryption depends on the factorization of prime numbers. This unit will present the mathematical background you need in order to understand these algorithms and in turn get a better picture of public key cryptography.
Completing this unit should take you approximately 23 hours.
5.1: Introduction
Read this introduction to public key cryptography.
5.1.1: Example of Public Key Cryptography
Read the linked page above to learn about RSA. Take for granted the Chinese Remainder theorem, which is explained later.
5.1.2: Primality Testing
Read this article on primality testing, which is crucial to the security of public-key cryptography. Make sure you understand the naive tests, probabilistic tests, and fast deterministic tests.
5.2: Math Background
5.2.1: Euclid's Algorithm
Read this page about Euclid's algorithm. Work through the given example.
5.2.2: Chinese Remainder Theorem
Read this page to learn how the Chinese Remainder theorem works.
5.2.3: Legendre Symbol
Read this definition of the Legendre symbol.
5.2.5: Subgroup
Read this definition of a subgroup.
5.3: Prime Factorization Algorithms (More Math)
Read this introduction to prime factorization.
5.3.1: Integer Factorization
Read this to learn about integer factorization.
5.3.2: The Pollard p-1 Algorithm
Read this to learn how to factor an integer with Pollard's p-1 algorithm.
5.3.3: The Pollard Rho Algorithm
Read this to learn how to factor an integer with Pollard's Rho algorithm.
5.3.4: Shanks' Square Forms Factorization
Read this article to learn about Shanks' square forms factorization. Make sure you understand the algorithm and the examples given.
5.3.5: The Solovay-Strassen Algorithm
Read this to learn the how Solovay-Strassen test works.
5.3.6: Strong Pseudoprimes
Read this article to learn the definitions and properties of pseudoprime numbers. Go through the examples.
5.3.7: Miller-Rabin Prime Test
Read this to learn the how Miller-Rabin prime test works.
5.4: Miller-Rabin Primality Test in Code
Create a java language program that performs Miller-Rabin primality test. One possible solution can be found via the link above. Study the solution code only after you have solved the problem or spent a substantial amount of time working on it.