Skip to main content
1 of 3
joro
  • 25.4k
  • 10
  • 66
  • 121

Reduction from factoring to solving Pell equation

The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims

There are reductions from factoring to solving Pell’s equation, and from solving Pell’s equation to solving the principal ideal problem [BW89b]

Can't find their reference [BW89b] on the internet and the extended abstract found doesn't address the issue.

What is the reduction from factoring to solving Pell equation?

The motivation is that solving the Pell equation $x^2-d y^2=1$ is tractable for $d$ a Fermat number (and possibly for $d=a^2+1$). Experimentally in the above cases the period of the continued fraction for $\sqrt{d}$ is $1$.

joro
  • 25.4k
  • 10
  • 66
  • 121