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

[Aurel Page <aurel.page@normalesup.org>]

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.

Cheers,
Aurel