2
$\begingroup$

Let $n$ be integer with unknown factorization. Assume factoring $n$ is inefficient.

Let $a,b,c$ satisfy $a^2+b^2 \equiv c^2 \bmod{n}, 0 \le a,b,c \le n-1$.

Is it possibly to lift the above congruence to coprime integers in $O(\mathsf{polylog}(n))$ time with probability at least $O\Big(\frac1{\mathsf{polylog}(n)}\Big)$?

i.e., find coprime integers $A,B,C$ satisfying $$A^2+B^2=C^2, A \equiv a \bmod{n},B \equiv b \bmod{n},C \equiv c \bmod{n}$$

If we drop the coprime constraint, the problem is easy.

I do not know if this is equivalent to factoring $n$.


Explaining per comments.

Write $A=a+a'n, B=b+b'n, C=c+b'n$ for unknown integers $a',b'$.

Then $A^2+B^2-C^2=0$ is linear in $b'$.

Then $b'=-1/2*(a'^2*n^2 + 2*a*a'*n + a^2 + b^2 - c^2)/((b - c)*n)$ Since $n$ divides $a^2+b^2-c^2$, $b'= -1/2*(a'^2n+2a a'+ (a^2+b^2-c^2)/n)/(b-c) $.

If we can trial factor $b-c$ (it is prime with probability $1/\log{n}$), we try to solve $(a'^2n+2a a'+ (a^2+b^2-c^2)/n)=0$ modulo $2(b-c)$ for $a'$. If solution exists, we know $a',b'$ and the lift.

If we can't factor $b-c$ or solution doesn't exist, replace $b$ with $b+b''n$, this doesn't change the congruence and we will hit primes/numbers we can trial factor in the arithmetic progression $b-c + b''n$.

The problem with this approach is the lift is not coprime.


$\endgroup$
8
  • $\begingroup$ (1) This is impossible. You need at least time $\log n$ even to read $n$, let alone do any computation with it. For the same reason, it is impossible to compute anything from $a,b,c$ in time independent of the length of $a,b,c$. Presumably, you meant $O(\mathrm{poly}(\log n,\log a,\log b,\log c))$. (2) The task itself is unclearly described. Without further assumptions, such $A,B,C$ may not exist (e.g., if $n$ divides all three $a,b,c$). So, are there additional assumptions? $\endgroup$ – Emil Jeřábek Oct 19 '16 at 13:27
  • $\begingroup$ @EmilJeřábek Thanks, that was typo, fixed it. I meant poly(log(n)). a,b,c satisfy 0 <= a,b,c <= n-1 because of the congruence, so consider them reduced modulo n. In some cases it may be impossible, so that is why I am asking about probabilistic reduction. $\endgroup$ – joro Oct 19 '16 at 13:31
  • 1
    $\begingroup$ What do you mean by the last part of the comment? Whether an algorithm is deterministic or probabilistic has no bearing on the solvability of the problem. If a solution does not exist, it cannot be found by any kind of algorithm. So, what is the algorithm supposed to do about unsolvable instances? Does it have to explicitly report them as unsolvable, or can it just output garbage? $\endgroup$ – Emil Jeřábek Oct 19 '16 at 13:45
  • $\begingroup$ @EmilJeřábek At unsolvable instances it fails to find solution. If there is solution, the algorithm finds it with some probability or fails even though solution exists. $\endgroup$ – joro Oct 19 '16 at 13:58
  • 1
    $\begingroup$ @Wojowu I edited, giving algorithm for non-coprime solutions modulo composites. $\endgroup$ – joro Oct 19 '16 at 15:17
2
$\begingroup$

Unless I'm mistaken, if we had an efficient algorithm we would be able to factor integers efficiently. We may suppose $n$ is odd.

Randomly choose coprime integers $X, Y$, not both odd, in some large interval. Then $A = X^2 - Y^2$, $B = 2 X Y$, $C = X^2 + Y^2$ are a primitive Pythagorean triple. Now compute reduced residues mod $n' = 2n$, $a, b, c$, of $A, B, C$ respectively, and give them to the algorithm (with $n$ replaced by $n'$), obtaining $A', B', C'$ forming a primitive Pythagorean triple with $A' \equiv a \equiv A \mod n'$, $B' \equiv b \equiv B \mod n'$, $C' \equiv c \equiv C \mod n'$. In particular, $B'$ is even. Thus there are coprime integers $X'$, $Y'$ not both odd, with $A' = X'^2 - Y'^2$, $B' = 2 X' Y'$, $C' = X'^2 + Y'^2$, and these are efficiently computable from $A', B', C'$ by $X' = \sqrt{(A' + C')/2}$, $Y' = B'/(2X')$. We then have $2 X'^2 = A' + C' \equiv A + C = 2 X^2 \mod 2n$ so that $X'^2 \equiv X^2 \mod n$. Now if $n$ is composite, we should have with probability bounded away from $0$, $X' \not \equiv \pm X \mod n$, e.g. if $n = pq$ we might have taken $X'', Y''$ instead of $X, Y$, where $X'' \equiv X \mod 2p$, $Y'' \equiv Y \mod 2p$, $X'' \equiv -X \mod q$, $Y'' \equiv Y\mod q$, obtaining the same $a,b,c$. But if so, $\gcd(X'-X,n)$ and $\gcd(X'+X,n)$ gives us a nontrivial factorization of $n$.

$\endgroup$
4
  • $\begingroup$ Thanks, I think this will work. Probably you can work only modulo $n$, hoping for probabilistic chance about parity, which should happen with high probability. $\endgroup$ – joro Oct 20 '16 at 8:09
  • $\begingroup$ Do you think coprime lift exists with high probability if you fix $a,b$ and $c$ exists? $\endgroup$ – joro Oct 20 '16 at 16:13
  • $\begingroup$ Suppose $n$ is odd. Given $a,b,c$ coprime to $n$ with $a^2 + b^2 \equiv c^2 \mod n$, a necessary condition for the existence of a primitive Pythagorean triple $(A,B,C) \equiv (a,b,c) \mod n$ is that either $(c \pm a)/2$ or $(c \pm b)/2$ are squares mod $n$. If $c + a \equiv 2 x^2 \mod n$ and $c - a \equiv 2 y^2 \mod n$ and you choose the $x$ and $y$ correctly, you get a Pythagorean triple $A = x^2 - y^2$, $B = 2 x y$, $C = x^2 + y^2$. This will be primitive if $x$ and $y$ are coprime and not both odd. $\endgroup$ – Robert Israel Oct 20 '16 at 18:48
  • $\begingroup$ The coprime part can be arranged using Chinese Remainder Theorem, adding a suitable multiple of $n$ to $y$ to avoid any factors of $x$. $\endgroup$ – Robert Israel Oct 20 '16 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.