The approximate-GCD, which is called *near-GCD* in [8],
of two polynomials
,
where *C*[*x*] is a complex number coefficient polynomial,
is stated as the following concept.

and deg is the highest possible degree for (5). Equivalently, a near-GCD of and satisfies

(6) |

A near-GCD at accuracy level will be denoted by .

Here, the norm of the polynomial means *L*_{1} norm. A near-GCD
is
computed via
Euclidean Algorithm and a relaxed
termination criterion which should be imposed at a given accuracy level .
The
algorithm to compute -GCD of *f*_{1} and *f*_{2} is summarized as follows:

- 1.
- Compute

and

for and*i*=1,2 with

*s*_{i-1}^{(i)}=0,*s*_{i}^{(i)}=1.

- 2.
- if
,
then

The polynomials *f*_{j} generated by the algorithm,
*f*_{1} and *f*_{2} are represented as

In our case,

where and .