Title | **Approximate polynomial : Small degree and small height perturbations** |

Author(s) | Maurice Mignotte, Igor E. Shparlinski, Joachim von zur Gathen |

Type | Article in Journal |

Abstract | We consider the following computational problem: we are given two coprime univariate polynomials f 0 and f 1 over a ring R and want to find whether after a small perturbation we can achieve a large gcd . We solve this problem in polynomial time for two notions of “large” (and “small”): large degree (when R = F is an arbitrary field, in the generic case when f 0 and f 1 have a so-called normal degree sequence), and large height (when R = Z ). Our work adds to the existing notions of “approximate gcd”. |

Keywords | Euclidean algorithm, gcd, Approximate computation |

ISSN | 0747-7171 |

URL |
http://www.sciencedirect.com/science/article/pii/S074771711000060X |

Language | English |

Journal | Journal of Symbolic Computation |

Volume | 45 |

Number | 8 |

Pages | 879 - 886 |

Year | 2010 |

Edition | 0 |

Translation |
No |

Refereed |
No |