Re: How to solve the type of this simple diophantine equation with large Integers

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

In reality, I can set B to any square residue (resulting in kowing a square root of Mod(B,A)). This is mod A I don t choose. How does this makes the problem easier? How ro solve it?

Sincerely,

-------- Message d'origine --------

De : Kurt Foster <drsardonicus@earthlink.net>

Date : 09/03/2025 12:49 (GMT+01:00)

À : Laël Cellier <lael.cellier@laposte.net>

Objet : Re: How to solve the type of this simple diophantine equation with large Integers

On Mar 8, 2025, at 6:22 PM, Laël Cellier wrote:

> Bonjour,
> simple question. I ve B and a semiprime A which are very large 
> unrelated fixed integers impossible to factor.
> How to find y and z such as y²≡z²×B mod A? Which pari functions 
> to use? Nfroots?

The short answer is, you don't.  Not unless you already know a square 
root of Mod(B,A).

Specifically: your equation may be rewritten

Mod(y/z,A)^2 = Mod(B, A)

So, for the equation to be solvable, Mod(B, A) has to be a square. 
Given that you don't know the factorization of A, the only way to be 
sure of this is I can think of offhand  to use a construction like the 
one Bill indicated a while back - that is, take C = random(A) and

B = lift(Mod(C,A)^2).

Then you have that Mod(B,A)  is a square, with the square roots Mod(C, 
A) ad Mod(-C,A).

Then for any z, 0 < z < A, y= lift(Mod(z*C, A)) or lift(Mod(-z*C,A)) 
gives solutions to your equation.

Of course, you can pick random C, take Mod(B,A) = Mod(C,A)^2 , and 
construct pairs (y, z) for each as above until the cows come home, and 
you will be no closer to factoring A than when you started.