About this scholarly article

The modulo N extended GCD problem for polynomials by Thom Mulders; Arne Storjohann is a scholarly article available to read on EtoBox.

We study the following problem: Given a; b; N 2 F x with gcda; b; N = 1 and N nonzero, compute a minimal degree f 2 F x which satis es gcda + f b ; N =1. We give a deterministic algorithm for solving this problem that is applicable over any eld. The algorithm is designed to solve e ciently a succession of such problems for a xed N. When q = F deg N the solution will satisfy deg f = 0 . When q deg N we conjecture that the solution satis es deg f d log q deg Ne; in this case the complexity bound we give for the algorithm depends on this conjecture. As an application we demonstrate a deterministic algorithm for computing transforming matrices for the Smith normal form of a nonsingular A 2 F x nn . When q is too small most previous algorithms require working over an algebraic extension of F and may not produce transforming matrices over F x . The algorithm we propose will produce transforming matrices over F x , for elds F of any size.

Author

Thom Mulders; Arne Storjohann

Publisher

ACM

Published

1998

Language

EN