Re: How to find a solution to this equation so the result is a postive perfect square ?

[Laël Cellier <lael.cellier@laposte.net>]

The reason I know N is square mod a is I partly build N as a square mod 
a through the general algorithm. Hence the first example. What interest 
me too are the cases where N<a though I can work with N>a.

What matters for me is only the equation of the first post and having 
postive integers as the answer (which doesn’t contains z directly).

Remember, using modular inverses, it’s possible to have the square root 
both >sqrt(N) or <sqrt(N). Do you mean having s larger is better ?

In all cases, I’d prefer some Pari/gp specific clues on how to computer 
them… As Pari/ɢᴘ lacks an equation solver.

Cordialement,

Le 14/02/2025 à 04:38, Laël Cellier a écrit :
> First, in my last post, reducing s*z mod N was completely wrong. We're 
> working mod a here. I was a bit puzzled by the remark above. You can 
> of course "know" that a is a "large semiprime" without knowing its 
> factors; there are plenty of them on offer as factorization 
> challenges. But if you don't know the factorization of the "large 
> semiprime" a, it is not clear to me how you would know that N is a 
> square (mod a), let alone having a modular square root. One was is 
> using the SCF for sqrt(a), which gives a series of quadratic residues 
> of order sqrt(a), with a square root of each. But let us just assume 
> that a, N, and s are given, where gcd(N, a) == 1 and Mod(s,a)^2 == 
> Mod(N, a).
> We want y^2 - N*z^2 = -x*a, where x, y, and z are positive integers.
>
> As Denis points out, this means that Mod(y/z, a)^2 = Mod(N,a). 
> Obviously Mod(y,a) = Mod(s*z,a) or Mod(-s*z,a) will make (y^2 - 
> N*z^2)/ a an integer. However, we want this integer to be negative. 
> Alas, pre-selecting a small value of z is unlikely to make this 
> possible because (s*z)%a is unlikely to be small enough to make y^2 - 
> N*z^2 negative. And indeed, in the first example, the value of z, 
> 519229685853482762853049632922093, is not exactly small. However, the 
> value of y in that example, 21, IS small. And that points in a 
> fruitful direction. If instead of pre-selecting z we pick y first, we 
> can take *any* positive integer y < sqrt(N). This forces y^2 - N < 0.
> So if z = lift(Mod(y/s, a)); we are guaranteed that z >= 1, so
>
> y^2 - N*z^2 <= y^2 - N <  0
>
> and since y == s*z (mod a) we are also guaranteed that (y^2 - N*z^2)/a 
> is an integer. Assuming y is not a square root of N (mod a), we can 
> relax the bound to y < 2*sqrt(N). Assuming y is not a square root of 
> either N or 4*N (mod a), we can relax the bound to 3*sqrt(N), and so 
> on. So you can produce solutions easily by choosing "small" values of 
> y and computing the corresponding values of z = lift(Mod(y*s,a)) using 
> any square root s of N (mod a).