Re: Can bnfinit recognize square integer factors without factorization?

[John Cremona <john.cremona@gmail.com>]

In another well known paper by Hendrik Lenstra of around that time, he
showed that just about all algorithms in algebraic number theory are
exponential since finding the ring of integers of a number field,
given only a defining polynomial, required finding the largest square
factor of the polynomial's discriminant, and that was exponential,
being no easier than factoring.  On the other hand, if the
factorization of that discriminant was given, then all the rest was
polynomial time.

Caveat: others on this list are much more expert on all this than me!

John

On Tue, 8 Dec 2020 at 14:41, Georgi Guninski <gguninski@gmail.com> wrote:
>
> On Sun, Dec 6, 2020 at 7:29 PM Bill Allombert
> <Bill.Allombert@math.u-bordeaux.fr> wrote:
>
> > > n=p^2*q;addprimes(n);K=bnfinit(x^2+n);
> > >
>
> > ? quadclassunit(-n)
> > %12 = [603602686944,[603602686944],[Qfb(679298724049,-45901789467,1692713557093)],1]
> >
> > n is not prime since the class number is even.
> > Not sure how one can conclude that n is not squarefree.
> >
>
> Thanks. I believe if you can find the class number, you can factor
> the integer n.
>
> A Rigorous Time Bound for Factoring Integers
>
> https://www.researchgate.net/publication/28639458_A_Rigorous_Time_Bound_for_Factoring_Integers
>