Hallgren's algorithm for solving Pell's equation

Printer-friendly version
Speaker: 
Shahed Sharif
Institution: 
CSUSM and UCI
Time: 
Mon, 05/08/2017 - 3:00pm
Location: 
RH 440R

We will complete our discussion of Shor's algorithm for
factoring integers. Then we will begin discussing Hallgren's quantum
polynomial-time algorithm for solving Pell's equation x^2 - dy^2 = 1.
The paper can be found at

http://public.csusm.edu/ssharif/crypto/

Hallgren's idea is to adapt Shor's algorithm to estimate the regulator
of Q(\sqrt{d}), and recover a fundamental unit from the regulator. This
algorithm also provides the main ideas in the quantum unit group
algorithm of Eisentr\"ager, Hallgren, Kitaev, and Song.