The paper [Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem](http://www.cse.psu.edu/~hallgren/pell.pdf) 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:

1. One can get the trivial $x \equiv \pm 1 \mod d$
2. 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](ftp://www.hacktic.nl/pub/mirrors/Advances%20in%20Cryptology/HTML/PDF/C89/335.PDF) 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](http://cr.yp.to/bib/1982/schoof.html)

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.2173&rep=rep1&type=pdf)


>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](ftp://ftp.di.ens.fr/pub/users/pnguyen/Asia09.pdf)