Can we use the extended euclidian algorithm to simplify factorization process of two products of large prime numbers with one common factor?

Question

We have two products of prime numbers with a large number of digits, so we don t have enough computing power to find its factors. The products have one common prime factor. Can we use the extended euclidian algorithm for finding GCD to simplify factorization process and make it computationally possible?

Answer 1

If you are given two numbers $pq$ and $pr$, where $p$, $q$, and $r$ are prime, then using the Euclidean algorithm on $pq$ and $pr$ (which is 'computationally efficient') will give you $p$. Then you can divide the previous numbers by $p$ to get $q$ and $r$, thus giving you a quick factoring.