## "Interesting" Square Roots of 1: Primality Testing in Cryptography |

**Kathryn Lesh**

Union College

October 17, 2005

4:30 pm

Bailey Hall 201

Pastries and drinks will be served at 4:00 pm in Bailey Hall 204

In modern cryptography, the public-key methods that secure Internet transactions require the use of large primes. How does one come up with a large prime? Typically, one generates a random number of the desired size and then tests it for primality. A widely used test is the Miller-Rabin test, which relies on the fact that if n is composite, then the number 1 has "interesting" square roots in "clock" (modular) arithmetic for that n. I will discuss the overview of primality testing used in cryptography, and then describe the Miller-Rabin test and the "interesting" square roots of the number 1.

For additional information, send e-mail to math@union.edu or call (518) 388-6246.

Union College Math Department Home PageComments to: math@union.edu Created automatically on: Tue Oct 23 07:39:11 EDT 2018 |