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.

3more comments