Given an equation $x^2\equiv(a+ib)\bmod(c+id)$ where $a,b,c,d\in\mathbb Z$ holds, how to test if the equation has solutions and how to find the solutions in polynomial in $\log(|abcd|)$ time if $c+id$ is a Gaussian prime and $p=c^2+d^2$ is a prime congruent to $1\bmod 4$?
$\begingroup$
$\endgroup$
7
-
5$\begingroup$ Note $\mathbb{Z}/(c+id)\mathbb{Z}$ is a finite field of size $p$, and any algorithm that works in a finite field will work here. In particular you can use binary exponentiation to check if a solution exists: $(a+ib)^{(p-1)/2}\bmod {c+id}$ is congruent to $1$ if $a+ib$ is a square. $\endgroup$– Ofir GorodetskyCommented May 15, 2023 at 23:36
-
$\begingroup$ @OfirGorodetsky How to handle when $p$ is not a prime? $\endgroup$– TurboCommented May 16, 2023 at 1:18
-
1$\begingroup$ @Turbo Finding modular square roots is essentially equivalent to factorization (under some form of randomized polynomial time reductions, not sure about the details). I don't know about just determining existence. $\endgroup$– WojowuCommented May 16, 2023 at 4:53
-
2$\begingroup$ Tonelli-Shanks. $\endgroup$– Peter TaylorCommented May 16, 2023 at 8:25
-
1$\begingroup$ @Turbo To make things concrete, there is an explicit isomorphism $\phi\colon \mathbb{Z}[i]/(c+id)\mathbb{Z}[i]\to \mathbb{Z}/p\mathbb{Z}$ given by $\phi(a+ib)=a+xb$ where $x\bmod p$ is a squareroot of $-1$ (and, as Peter Taylor indicated, this root can be computed efficiently). $\endgroup$– Ofir GorodetskyCommented May 16, 2023 at 10:47
|
Show 2 more comments