10
$\begingroup$

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

$\endgroup$
16
  • 2
    $\begingroup$ I’d guess that you can use the solution to Pell’s equation to find a congruence of squares (en.wikipedia.org/wiki/Congruence_of_squares) or something to that effect. $\endgroup$ Jul 21, 2011 at 16:28
  • 1
    $\begingroup$ I’m not claiming to know how the reduction works. However, if I may venture another guess, I’d expect $d=n+1$ to be more useful than $d=n$ ($n$ is the number to factorize). $\endgroup$ Jul 21, 2011 at 17:28
  • 1
    $\begingroup$ @Emil If you can answer just answer the question, don't suggest wiki links. $\endgroup$
    – joro
    Jul 21, 2011 at 17:40
  • 1
    $\begingroup$ Maybe the method works by choosing considering several $d = n \cdot k_i$, where $k_i$ is a random integer. A solution $(x, y)$ to the Pell equation yields $x \equiv 1 \pmod{d}$. Now either $x \equiv \pm 1 \pmod{d}$, or you got a factor. If there is a not too bad chance that for some $k$, you get a non-trivial solution, this would yield a factoring method. For example, if $n = 15$ and $k = 2$, then a fundamental solution for $d = 30$ is $(x, y) = (11, 2)$, and $gcd(x, n) = 5$ is a non-trivial factor. $\endgroup$
    – felix
    Jul 21, 2011 at 18:11
  • 1
    $\begingroup$ You can't be bothered to write to the authors for a reprint, and you want us to tell you what is in a paper you have not seen? $\endgroup$
    – Will Jagy
    Jul 21, 2011 at 22:09

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ You said to repeat for $d=M,2N,3N,\dots$. How do we know the number of trials in logarithmic in $N$? $\endgroup$
    – Turbo
    Sep 11, 2013 at 14:38
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
24
  • $\begingroup$ Thanks. I suppose in $gcd(25,143)=13$, $25$ should be $26$ (the way you wrote it the gcd is $1$) $\endgroup$
    – joro
    Oct 7, 2011 at 4:51
  • $\begingroup$ What about $\equiv 1 \mod 4$? Fermat numbers are this case. $\endgroup$
    – joro
    Oct 7, 2011 at 4:56
  • $\begingroup$ Yes. I just edited that! $d \equiv 1 \pmod{4}$ should be just as easy. I' ll have a think about. We need to turn $x^2 - d y^2 = 1$ into a Pell conic for $d \equiv 1 \pmod{4}$. If $\Delta \equiv 1 \pmod{4}$ then $x^2 - \Delta y^2 = 4$ is a Pell conic. In this case, take $\text{gcd}(x +2 ,\Delta )$. $\endgroup$ Oct 7, 2011 at 5:54
  • $\begingroup$ $77 \equiv 1 \pmod{4}$. $(351, 40)$ is the least non-trivial solution to $x^2 - 77 y^2 = 1$. Small non-trivial points of the Pell conic $x^2 - 77 y^2 = 4$ are $(9, 1)$, $(79, 9)$, $(702, 80)$. The point $(351, 40)$ of the first equation corresponds to $(702, 80)$ of the second equation. $\text{gcd}(702 + 2, 77) = 11$. I think that I may occur that the point of the Pell conic obtained from the Pell equation is not the least non-trivial point, in which case from here it may occur that x+2 is a square, which would be a problem. I'll try a Fermat number next. $\endgroup$ Oct 7, 2011 at 6:10
  • 1
    $\begingroup$ People have said that solving $x^2 - d y^2 = 1$ should take more time than factoring, but I think that you have found a family of $d$ for which this might not be true. $\endgroup$ Oct 8, 2011 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.