RESEARCH OF ALGORITHMS FOR SEARCHING PRIMITIVE ELEMENTS OF A FINITE FIELD OF HIGH ORDER

One of the most important unsolved and notoriously difficult problems in computational finite field theory is the development of a fast algorithm for constructing primitive roots in a finite field. It is known that for many applications, instead of a primitive root, just an element of high multiplicative order is sufficient. Such applications include, but are not limited to, cryptography, coding theory, pseudorandom number generation, and combinatorial schemes. Explicit constructions of high-order elements usually rely on combinatory methods that can provide a provable lower bound on the order, but this does not compute the exact order. Its execution usually implies knowledge of the factorization of the order. Ideally, we should be able to get a primitive element for any finite field in a reasonable amount of time. However, if the simple factorization of the group order is unknown, it is difficult to achieve the goal. Thus, we set the task of constructing an element, probably of a high order. This article discusses various algorithms that find a high-order element for general or special finite fields. This work also represents another contribution to the theory of Gauss periods over finite fields and their generalizations and analogues, which have already proven their usefulness for a number of different applications.

1. Prachar K. Primzahlverteilung, Springer, Berlin, 1957, pp. 77, doi: https://doi.org/10.2307/3608911.

2. Wang Y. On the least primitive root of a prime, Acta Math. Sinica, 9, 1959, pp. 432–441. (English translation in Sci. Sinica 10 (1961)).

3. Shoup V. Searching for primitive roots in finite fields, Math. Comp., 58, 1992, pp. 369–380.

4. Bach E. Comments on search procedures for primitive roots, Math. Comp., 66(220), 1997, pp. 1719– 1727.

5. Shparlinski I.E. On finding primitive roots in finite fields, Theoret. Comput. Sci., 157, 1997, pp. 273– 275.

6. Shparlinski I.E. Finite fields: Theory and computation, Kluwer Academic Publishers, Dordrecht, 1999.

7. Gao S. Elements of provable high orders in finite fields, Proc. Amer. Math. Soc., 127, 1999, pp.1615– 1623.

8. Conflitti A. On elements of high order in finite fields, in: Cryptography and Computational Number Theory, Birkhauser, Basel, 2001, pp. 11–14.

9. Von zur Gathen J. and Shparlinski I. Orders of Gauss periods in finite fields, Applicable Algebra in Engineering, Comm. Comput., 9, 1999, pp.15–24.

10. Von zur Gathen J. and Shparlinski I. Constructing elements of large order in finite fields, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: AAECC-13, Lecture Notes in Computer Science, Springer, Berlin, 1719, 1999, pp. 404–409.

11. Von zur Gathen and Shparlinski I. Gauss periods in finite fields, Proceedings of the Fifth Conference of Finite Fields and their Applications, Springer, Berlin, 1999, P. 162–177.

12. Cheng Q. Constructing finite field extensions with large order elements, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004, pp. 1123–1124, https://doi.org/10.1137/S0895480104445514.

13. Cheng Q. Primality proving via one round in ECPP and one iteration in AKS, D. Boneh (Ed.), Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO), Lecture Notes in Computer Science, Santa Barbara, Springer, Berlin, 2729, 2003, pp. 338–348.

14. Voloch J.F. On some subgroups of the multiplicative group of finite rings, 2003, http://www.ma.utexas.edu/users/voloch/preprint.html.

15. Shparlinski I.E. On constructing primitive roots in finite fields with advice. IEEE Trans. Inform. Theory, 64, 2018, pp. 7132–7136.

16. Bhowmick A. and Lê T. H. On primitive elements in finite fields of low characteristic, Finite Fields Appl., 35, 2015, pp. 64–77.