Questions

$(1)$

Why do we care about $\overline{u} {\Phi}(\overline{a}) {\Phi}(\overline{b})$ ?

$(2)$

Give a running time estimate for the computation of $\overline{u} {\Phi}(\overline{a}) {\Phi}(\overline{b})$

$(3)$

Show that ${\ell}$ divides $f_3$ and let $f_4$ be the quotient.

$(4)$

Show that ${\gamma} = q_1 + f_4$ holds

$(5)$

How to choose ${\ell}$ such that ${\gamma}$ can be computed in $3 M(d) + O(d)$ operations in ${\mathbb{K}}$ ?