Theory Seminar: Square Roots in Finite Fields

Friday, January 22, 2016 - 2:00pm
CS 4310

Speaker Name: 

Eric Bach

Speaker Institution: 




Cookies Location: 

CS 4310


An efficient digit-by-digit method for square root extraction has been known to Westerners since Fibonacci's Liber Abaci (1202). Why is there no comparably efficient method for computing square roots in finite fields? Since there are good randomized algorithms, this question is emblematic of a central topic in theoretical computer science: is the power of efficient computation enhanced by the ability to make random choices? In this talk, I will explain why the square root problem for finite fields is almost (but not quite) in P, the class of problems solvable in deterministic polynomial time, and outline recent progress that has been made toward proving that it is so.