**We saw in the first chapter that running the Euclidean
Algorithm in
can lead to a significant expression swell.
Let us try to estimate how coefficients grow.
That is, we want to estimate the maximal space
needed to store one coefficient of an intermediate polynomial.
Let
be the number of bits of a machine word.
**

(1) |

(2) |

(3) |

- .
- .

(4) |

(5) |

It is not hard to see that

(6) |

Then

(7) |

Thus

(8) |

Recall that

(9) |

Since we obtain

(10) |

Indeed and .

*
*

2008-01-07