Reduction from factoring to solving Pell equation

Question

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

Answer 1

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.

Answer 2

I agree with Lemmermeyer, reductions of Factoring to Pell's Equation do not seem to yield an efficient method to factor Fermat numbers, or at least, not in a straightforward fashion.

To see this better, let's answer in detail your first question: how to reduce Factoring to Pell's Equation? Although you have explicitly forbidden the approach I am going to follow, I think it is quite pedagogical to imitate Peter Shor's factorisation algorithm.

Review: Shor Algorithm to factor a composite number $d$

1. Classical part. Use that you can always get a factor of $d$ if you are able to find non-trivial solutions of $x^2=1\mod d$. Then either $gcd(x-1,d)$ or $gcd(x+1,d)$ is a factor of $d$.
2. Quantum part. Use the order-finding quantum algorithm to find an non-trivial number $a$ of even order. This number fulfils condition 1.
3. Repeat on smaller number until you end.

Steps 1. and 2. are explained very clearly in Nielsen & Chuang's book. Wipedia has an article also.

Reduction: Factoring $d$ using Pell's Equation solver.

1. Classical part. Same as the previous one, making sure that the number to factor is not a square, i.e. $d\neq n^2$ (taking square roots of $d$ until you get a non-square $d'$).
2. Quantum part. Use Hallgreen's algorithm [2][3] (or a Pell's Equation solver) to find a non-trivial solution $(x_1, y_2)$ of $x^2-dy^2 = 1$, which is promised to exist as $d$ is not a square. The number $x_1$ fulfils condition 1 and you can obtain a factor of $d$ from it.
3. Repeat procedure.

Second question: can we factorise Fermat numbers?

As you have already highlighted, the above reduction does not give an efficient Fermat number factorisation routine:

1. There are no known classical algorithms to solve Pell's Equation, Order Finding or Period Finding (which is at the core of both), so we get stuck in step 2 in both cases.
2. If you try to restrict to Fermat numbers, using that you can solve Pell's Equation for them, this procedure does not work either unless the factors you find iteratively are also Fermat numbers.
3. Besides, I do not know of any efficient factorisation algorithms for general composite numbers which is not based on the same principles as Shor's. Therefore, in my view, finding a totally-different reduction that goes around all problems present on the above method seems to be quite tough question.

I guess you know many of these obstacles to solve problem 2, but maybe this view of the problem can be illustrative.

Answer 3

You may be aware of the following, and it probably doesn't answer all of your question. If $d > 0$ is both square-free and congruent to $2$ or $3 \pmod{4}$, and integers $x, y$ satisfy $x^2 - d y^2 = 1$ non-trivially with $y > 0$ and minimum among other solutions, then $\text{gcd}(2 x + 2, d)$ should be non-trivial. See Lemmermeyer's articles arXiv:math/0311306v1 and arXiv:math/0311310v1 . Examples: $(4, 1)$ satisfies $x^2 - 15 y^2 = 1$. $\text{gcd}(10, 15) = 5$. $(12, 1)$ satisfies $x^2 - 143 y^2 = 1$. $\text{gcd}(26, 143) = 13$.