On an integer factoring algorithm based on smooth class number of quadratic fields

Question

We got an algorithm and toy implementation of integer factoring algorithm based on smooth class number of quadratic fields.

It is close to the elliptic curve factorization method (ECM) and succeeds if it can find find $B_1$ smooth integers (all primes factors are less than $B_1$).

Sketch of the algorithm:

For integers $a,b,c$, let $q$ be the binary quadratic form $Qfb(a,b,c)$ and define $D(q)=b^2-4ac$ (as defined in the pari/gp).

If $D(q)<0$, then $\{ q^k \}$ is abelian group of order divisor of $h$ where $h$ is the class number of $\mathbb{Q}{\sqrt{D(q)}}$ (not counting square factors).

Elements of order $2$ in the group are related to factoring $D(q)$.

If $h$ is $B_1$ smooth, write $h=2^k B_2$ with odd $B_2$. Compute $q_2:=q^{B_2}$ with enumerating the primes one by one.

Then compute $q_2^{2^i}$ hoping to find factorization of $D(q)$.

In case of failure, try a small multiple $m D(q)$.

The algorithm sometimes works for $D(q)>0$.

As a corollary, this algorithm might compute multiple of $h$.

Q1 Is this algorithm known, references?

If someone is interested in the toy pari/gp implementation, contact me at my gmail address.

Answer 1

This idea was first studied by Shanks, Pollard, Atkin and Rickert, although they didn't write a paper as far as I know. Schnorr and Lenstra gave a heuristic time complexity analysis in their 1987 paper. Since there's no standard name, I'll call it the class group method CGM.

The time complexity of CGM is soft-O of $L_n[1/2]$ meaning we drop logarithmic factors. There's a second constant in the time complexity but its not a strong predictor of an algorithm's practical performance so I'll ignore that. This time complexity is like all algorithms for factoring $n$ from that period with the sole exception of ECM. The time complexity of ECM is soft-O of $L_p[1/2]$ where $p$ is the smallest prime factor. Note that $n$ doesn't show up in the time complexity. In practice, the size of $p$ is the most important factor in the algorithm's performance.

There have been attempts to make CGM more competitive with ECM. The challenge there is that for ECM the practical performance is controlled by the size of the smallest prime factor of $n$ rather than the number itself (just what the time complexity would lead you to think). This is not true for CGM.

However, in the special case that $n$ is not squarefree there is new work on an algorithm that improves on CGM. The algorithm's time complexity depends on the size of the squarefree part of $n$. On the practical side, the author gives some evidence that the algorithm is fast compared to the best factoring libraries available for numbers of the form $n=pq^2$ where the primes $p$ and $q$ are of a certain size.

This algorithm takes advantage of properties of class groups of non-maximal orders. Modifying it to get a time complexity like ECM's for general $n$ would be hard and require a new idea.