Efficiently lifting $a^2+b^2 \equiv c^2 \pmod{n}$ to coprime integers 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.


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$.  
