Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleApproximate polynomial : Small degree and small height perturbations
Author(s) Maurice Mignotte, Igor E. Shparlinski, Joachim von zur Gathen
TypeArticle in Journal
AbstractWe 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”.
KeywordsEuclidean algorithm, gcd, Approximate computation
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S074771711000060X
LanguageEnglish
JournalJournal of Symbolic Computation
Volume45
Number8
Pages879 - 886
Year2010
Edition0
Translation No
Refereed No
Webmaster