Efficient polynomial time algorithms computing industrial-strength primitive roots

摘要

E. Bach, following an idea of T. Itoh, has shown how to build a small set of numbers modulo a prime p such that at least one element of this set is a generator of Z/pZ. E. Bach suggests also that at least half of his set should be generators. We show here that a slight variant of this set can indeed be made to contain a ratio of primitive roots as close to 1 as necessary. In particular we present an asymptotically O~ ((1/ε)~(1/2) log(p) + log~2 (p)) algorithm providing primitive roots of p with probability of correctness greater than 1 - ε and several O(log~α (p)), α ≤ 5.23, algorithms computing "Industrial-strength" primitive roots.