Re: sqrt(x,n) for non-prime n?

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

On Tue, Nov 21, 2023 at 02:44:11PM +0100, Aurel Page wrote:
> On 21/11/2023 13:03, hermann@stamm-wilbrandt.de wrote:
> > So implementing Kunerth's method is only needed if factoring modulus
> > would take too much time.
> If you can compute square roots of arbitrary numbers modulo n, then you can
> factor n. Indeed, take some x modulo n, compute a square root y of x^2 mod
> n: then gcd(x-y,n) is a nontrivial factor of n with good probability.

No, you need two different squareroots that are not ± the others.

For example 2^64 is a root of -1 modulo (2^128+1) but it is not sufficient for
factoring.

But yes, there must be some unstated hypothesis for Kunerth's method to work.

Cheeers,
Bill