Re: How to find a congruence to the type of that simple equation without factoring the modulus?

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sun, Mar 16, 2025 at 12:22:17PM +0100, 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? Cordialement,
> 
> > You best bet is zncoppersmith, but this will only work if there is a solution
> (y,z) with relatively small y and z which will almost never be the case.
> 
> > You need fundamentaly new ideas.
> 
> > Cheers,
> > Bill.
> 
> Hi, sorry for the delay.
> And if I’m free to chose B² mod A (thereby being indirectly free to chose B),
> and thus only A can’t be chosen, would it be something easy to make y and z
> findable through zncoppersmith as a result, and if yes, how ?

This is a trick question, but you are just going in loops.
Say you chose B^2=1, then you have two choice for B:
B = 1 then of course y=±z
B = -1 ,then you need to solve a problem equivalent to computing a square root of -1 modulo A,
which is the problem you try to solve, so you are not making progress.

Cheers,
Bill.