<s>[INST] 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.

 [/INST] 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$.  
</s>