Algorithms and Complexity Seminar

Monday, April 7, 2008, 4:00-5:15pm in 32-G575.

Subexponential Performance from Generic Group Algorithms

Andrew V. Sutherland (MIT)

"Birthday paradox" algorithms such as Shanks' baby-steps giant-steps algorithm and Pollard's rho method are examples of generic group algorithms, known for their versatility and their (typically) exponential running times. We present a generic approach that achieves subexponential performance for a certain class of search problems. We then apply this technique to address an open challenge: finding groups suitable for use in hyperelliptic curve cryptography.

Talk will be based on the paper "A Generic Approach to Searching for Jacobians" (http://arxiv.org/abs/0708.3168).

Host: Mike Sipser

(The Algorithms and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)