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

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

On Thu, Feb 13, 2025 at 03:05:30PM +0100, Laël Cellier wrote:
> So, do you mean only square roots of a are the solution ? In the current
> example, I volontarily took a long a in the case it’s hard to factorize (up
> to 1024). On the other end, I don’t need a specific end result, but just for
> it to be a square…
> 
> And even then, what about the case I know a square root
> of 20422354090808007360481140437163150058277495681745577657420405131241 mod
> 53919893334301279589334030174040979997534463873026188556492192357233 (taking
> back the example) ?

Unless 20422354090808007360481140437163150058277495681745577657420405131241 is 
special, there is no hope:

N=53919893334301279589334030174040979997534463873026188556492192357233
A=random(N)
B=A^2%N
So now I have B and a squareroot A of B mod N.
But of course this gives no new information on N.

Cheers,
Bill.