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

On Feb 13, 2025, at 2:37 PM, Laël Cellier wrote:

> Bon soir,
>
> I need both x and y to be positive. I think no problem for the  
> coprimes since a will always be a large semiprime…

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).