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.
