Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate Students
Current Graduate Students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - May 24
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - May 24
Event date: Friday, May 24, 2013, at 11:10 AM
Location: GB 244
Speaker: Joachim von zur Gathen, Bonn-Aachen International Center for Information Technology
Title: Generating safe primes and safe moduli
Abstract:
Safe primes and safe RSA moduli are used in several cryptographic schemes. The most common notion is that of a prime p, where (p-1)/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 have -- so far -- not 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.