Modular quadratic equation help

Question

our professor gave us one "equation to think at" (as he says). I tried to "think at" since friday but I don't know how to handle it properly and (if any) if there are solutions of families of solutions.
The equation seems pretty simple:
Given $P,N,a$ rigorously integer numbers greater than $0$.
We have that
$(X^2+a)$ Mod N = $P$
and
$(Y^2+a)$ Mod N = $P$
How can we find $X$ and $Y$ that yield to the solution ?  Of course $X$ and $Y$ must be different ($Xneq Y$)
I make an example :
a= 203
N = 7979
Then we have $X=2944$ and $Y=6378$ that give the same $P=2145$.
But then do exist other $X$ and $Y$ that give the same $P=2145$ result ?
Or, in other manner, if I say for example that $P=2001$, how can we find the solutions ($X$ and $Y$)?
Thanks

vvg · Accepted Answer

Partial answer:
Note that $X^2 + a equiv Y^2 + a equiv P mod N$
$implies X^2 equiv Y^2 mod N$
$implies (X - Y)(X + Y) equiv 0 mod N$
A family of the solutions can be found using the following:
Take $X-Y, X+Y$ to be divisors of $Nk$ for some integer $k$.
If $X - Y = d$ is a divisor of $N$, then you get
$$X - Y + X + Y = 2X = d + {Nk over d}$$
$$implies X = {d + {Nk over d} over 2}, k in Z$$
$$implies Y = {d + {Nk over d} over 2} - d$$
If you equate $X + Y = d$, you get the same family of solutions as above since $X-Y$ and $X+Y$ are the two divisors whose product equals $Nk$.
These are not the only solutions because there could be divisors of $Nk$ that are not divisors of $N$ (divisors of $k$).

Modular quadratic equation help

One Answer

Add your own answers!

Ask a Question