There is a deterministic [polynomial-time algorithm](/page/Polynomial-Time%20Algorithm) $E$ which, on input signed binary encodings of two nonzero integers $a,b \in \mathbb{Z}$, outputs a signed binary encoding of the nonnegative integer $\gcd(a,b)$, where $\gcd(a,b)=\gcd(|a|,|b|)$.