- 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.

*
*

2008-03-18