Symbolic Computation Group
David R. Cheriton School of Computer Science


Friday, May, 31, 2013, at University of Waterloo Generating safe primes and safe modulii Joachim von zur Gathen, University of Bonn Abstract: Safe primes and safe RSA moduli are used in several cryptographic schemes. The most common notion is that of a prime p, where (p1)/2 is also prime. The latter is then a Sophie Germain prime. Under appropriate heuristics, they exist in abundance and can be generated efficiently. But the modern methods of analytic number theory haveso farnot even allowed to prove that there are infinitely many of them. Also for other notions of safe primes, there is no algorithm in the literature that is unconditionally proven to terminate, let alone to be efficient. This talk considers a different notion of safe primes and moduli. They can be generated in polynomial time, without any unproven assumptions, and are good enough for the cryptographic applications that we are aware of. Joint work with Igor Shparlinski, Sydney.

Last modified on Thursday, 23 May 2013, at 13:41 hours.