## Questions

Design a modular modular algorithm based on the following observation: if divides then divides for every .
Assume that we are given an upper bound for the absolute value of a coefficient in any polynomial dividing . (Such upper bound exists and will be discussed in class.) Design a modular modular algorithm based on the following observation: if divides (in ) then divides modulo any prime number .
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.

Marc Moreno Maza
2008-03-18