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

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 <[email protected]> Date : 09/03/2025  12:49  (GMT+01:00) À : Laël Cellier <[email protected]> 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 rewrittenMod(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) andB = 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.