Pell Equation – Reduction from Factoring to Solving Pell Equation

cryptographydiophantine equationsfactorizationnt.number-theory

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:

  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 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

Best Answer

If you had a fast method for solving Pell equations $x^2 - dy^2 =1$, you can factor numbers $N$ quickly: all you have to do is compute gcd$(x-1,d)$ for $d = N, 2N, 3N, \ldots$ until you find a factor; if the factor is not prime, repeat the procedure.

Schoof showed that you don't have to know the actual solution of the Pell equation, but that the size of the regulator is sufficient. His method uses Shanks' idea of infrastructure (see e.g. Jacobson and Williams, Solving the Pell Equation). By computing an ambiguous ideal (if the norm of the fundamental unit is positive) he can then factor $d = N$; if the ambiguous ideal is trivial, do the same for $d = 3N$ etc.

Of course you cannot expect to factor Fermat numbers by simply writing down a solution of the corresponding Pell equation. In the early days of factoring in the 1970s, Brillhart and Morrison suggested using small multiples of $N$ if the period of the continued fraction of $\sqrt{N}$ is too small - this hasn't changed.

Related Question