Re: Can bnfinit recognize square integer factors without factorization?

[Georgi Guninski <gguninski@gmail.com>]

On Tue, Dec 8, 2020 at 5:47 PM John Cremona <john.cremona@gmail.com> wrote:
>
> 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.
>

I am not sure the paper bellow is efficient since it isn't cited
and don't feel like paying $51 for it.

A factoring algorithm using quadratic residue

In this paper, we do a study upon an integer factoring algorithm based
on a new idea that using quadratic residue. This method is effective
especially on factoring Blum numbers and on n = p^2 q type composite
numbers.

https://www.tandfonline.com/doi/pdf/10.1080/00207160008804943
https://www.researchgate.net/publication/233344386_Factoring_algorithm_using_quadratic_residue