6.

(a) Give an upper bound on how many operations i → gⁱ mod n one must perform in order to verify (or refute) that an invertible element g is a primitive root for Z_n^*

(b) Assume that you have a complete prime factorization of φ(n). Using Lagrange's theorem, how many operations gⁱ mod n do you now require, and for which values of i?