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

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

On 21/11/2023 15:10, Bill Allombert wrote:
> 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.
Of course, that's why I said "with good probability" (ok, I should have 
taken x uniformly random mod n).

Cheers,
Aurel