Everyone likes either math theses OR free pizza.

Therefore, everyone should come to the Dartmouth Mathematical Society talk.

When/Where:Wednesday, February 20, at 6pm in Kemeny 008.

Our Speaker: Noah. Lebowitz-Lockard. '13. The Man. The Legend. NSA alumnus. 

Generating Random Factored Gaussian Integers, Easily

Abstract: Given an positive integer N, is it possible to generate a random positive integer less than or equal to N, along with its factorization in polynomial time? It seems as though the only way to solve this problem would be to choose a random integer less than or equal to N and factor it. But, factoring takes too long. However, there is another way. In 2003, Adam Kalai showed that it is possible to solve this problem without factoring any numbers at all. Kalai's method requires log^2 N primality tests, which can be done in polynomial time. In this talk, I extend this result to the complex plane and introduce similar algorithms for the Gaussian and Eisenstein integers.