Questions

$(1)$

Design a modular modular algorithm based on the following observation: if $g$ divides $f$ then $g(z)$ divides $f(z)$ for every $z \in {\mbox{${\mathbb{Z}}$}}$ .

$(2)$

Assume that we are given an upper bound for the absolute value of a coefficient in any polynomial $h$ dividing $f$ . (Such upper bound exists and will be discussed in class.) Design a modular modular algorithm based on the following observation: if $g$ divides $f$ (in ${\mbox{${\mathbb{Z}}$}}[x]$ ) then $g$ divides $f$ modulo any prime number $p$ .

$(3)$

No complexity analysis is required. However, you are asked to suggest why the second algorithm is likely to be more efficient that the first one.