"Interesting" Square Roots of 1: Primality Testing in Cryptography
October 17, 2005
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.
|Union College Math Department Home Page|
Comments to: firstname.lastname@example.org
Created automatically on: Sat Apr 21 13:26:14 EDT 2018