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:

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


We have

(y^2 + x*a)/N = z^2

y^2 - N*z^2 = -x*a where we want x positive. We obviously may assume  
that y and z are positive

We have

y^2 - N*z^2 == 0 (mod a) so that

Mod(y/z, a) == Mod(s, a) (s = some square root of N (mod a))

Since you want  x to be positive, we have (assuming of course that z  
is positive),

Taking y = s*z

for some integer s in the residue class Mod(s, a), where Mod(s,a)^2 =  
Mod(N,a) we have

(s*z)%N < sqrt(N)*z

If z > sqrt(N) this condition is satisfied trivially, so for each s  
there is a smallest positive z that works. Assuming 0 < s < a, then  
unless s is rather small, e.g. s < sqrt(N) I don't see a good way  
offhand to find the smallest positive z satisfying the condition. If z  
is given beforehand, there may be no solutions using any of the usual  
lifts of square roots s of N that are in (0, a).

However, any multiple of a can be added to s. Since we are assuming  
gcd(a, N) = 1, the arithmetic progression s, s + a, s + 2*a, etc. runs  
through all the residues (mod N). Assuming gcd(z, N) = 1 also, for a  
given z and any square root s of Mod(N,a)  in (0, a) it should not be  
too difficult to find a suitable k, for which

((s + k*a)*z)%N < sqrt(N)*z