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 trivial for $d$ a Fermat number. The period of the continued fraction for $\sqrt{d}$ is $1$.

**EDIT**

I am aware one gets the congruence $x^2 \equiv 1 \mod d$.

I don't consider this *reduction to factoring* because:

- One can get the trivial $x \equiv \pm 1 \mod d$
- Even if one gets non trivial factor it may be composite which is not complete factorization.

Other easy cases with short period of the continued fraction of $\sqrt{d}$ appear:

$$ d=a^2 \pm 1 $$ $$ d=a^2 \pm 4 $$ $$ d=a^2 \pm a $$ $$ d=a^2 \pm 4a $$ $$ d=b^2c^2 \pm b $$ $$ d=b^2c^2 \pm 2b$$

(the last two are due to Franz Lemmermeyer ).

BW89b contains

...can be used to determine the regulator $R$ of $\mathcal{O}$ in polynomial time. One can then use the method described in [Schoof 8] to factor in polynomial time.

Schoof 8 might be R.J. Schoof, Quadratic fields and factorization

Andreas Stein repeats this claim: "Knowledge of the regulator, together with a technique due to Schoof can then in turn be used to factor $\Delta$" in EQUIVALENCES BETWEEN ELLIPTIC CURVES AND REAL QUADRATIC CONGRUENCE FUNCTION FIELDS

Does solving the Pell equation allows complete factoring of $d$? If yes how?

The motivation is finding factors of Fermat numbers would be interesting to me if possible.

Remotely related (using the regulator) is Factoring $pq^2$ with Quadratic Forms: Nice Cryptanalyses

11more comments