3 Added claim by Stein. Clarifications.

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 tractable trivial for $d$ a Fermat number(and possibly for $d=a^2+1$). Experimentally in the above cases the . 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 tractable 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

2 Added references and tractable cases

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 tractable for $d$ a Fermat number (and possibly for $d=a^2+1$). Experimentally in the above cases 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 tractable cases with short period 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

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

1

# Reduction from factoring to solving Pell equation

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 tractable for $d$ a Fermat number (and possibly for $d=a^2+1$). Experimentally in the above cases the period of the continued fraction for $\sqrt{d}$ is $1$.