### 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.4: Calculating the Jacobi Symbol

Read this page.

Read this page.

### 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.