CS409: Cryptography

Upon successful completion of this unit, students will be able to:

• Describe the idea behind public key cryptography.
• Apply the RSA cryptography system to a practical problem.
• Test whether a large integer is prime via the naive method and probabilistic testing.
• Describe Euclid's algorithm and prove the Chinese Reminder Theorem.
• Describe the Legendre and Jacobi symbols.
• Define a subgroup.
• Explain the Pollard p-1 algorithm and Pollard Rho algorithm.
• Explain the Shanks' Square Forms Factorization algorithm.
• Explain the Solovay-Strassen test.
• Define strong pseudoprime.
• Explain the Miller-Rabin Prime test.