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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Jul 18, 2024 at 12:21:07PM +0300, Georgi Guninski wrote:
> I asked this on matherovflow at
> https://mathoverflow.net/questions/475285/on-an-integer-factoring-algorithm-based-on-smooth-class-number-of-quadratic-fiel
> 
> 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?

See Henri Cohen GTM 138, pp 473, 
The class group method of Schorr-Lenstra

""
     The idea of the method is as follows. We have seen in Section 8.6 that the
determination of the 2-Sylow subgroup of the class group of the quadratic field
Q( v' - N) is equivalent to knowing all the factorizations of N. In a manner
analogous to the continued fraction method, we consider the class numbers
h( -kN) of Q( v' -kN) for several values of k. Then, if h( -kN) is smooth, we
will be able to apply the p - 1 method, replacing the group IF; by the class
group of Q( v' -kN). As for the p - 1 method, this will enable uS to compute
the (unknown) order of a group, the only difference being that from the order
of IF; we split N by computing a GCD with N, while in our case we will split
N by using ambiguous forms.
""

Cheers,
Bill.