ИССЛЕДОВАНИЕ АЛГОРИТМОВ ПОИСКА ПРИМИТИВНЫХ ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ БОЛЬШОГО ПОРЯДКА

Одной из наиболее важных нерешенных и заведомо трудных задач в вычислительной теории конечных полей является разработка быстрого алгоритма для построения примитивных корней в конечном поле. С другой стороны, для многих приложений вместо примитивного корня достаточно элемента высокого мультипликативного порядка. Такие приложения включают, помимо прочего, криптографию, теорию кодирования, генерацию псевдослучайных чисел и комбинаторные схемы. Явные построения элементов высокого порядка обычно полагаются на методы комбинаторики, которые могут обеспечить доказуемую нижнюю границу порядка, но не вычисляют его точный порядок. Выполнение таких построений обычно основано на том, что факторизация порядка уже известна. В идеале мы должны иметь возможность получить примитивный элемент для любого конечного поля за разумное время. Однако если простая факторизация порядка группы неизвестна, этого сложно добиться. Таким образом, ставят менее амбициозную задачу – задачу построения элемента достаточно высокого порядка. В данной статье мы рассматриваем различные алгоритмы, которые находят элемент высокого порядка как для общих, так и для специальных конечных полей. Кроме того, в этой работе мы касаемся теории периодов Гаусса над конечными полями, их обобщениями и аналогами, которые, как известно, уже доказали свою полезность для ряда различных приложений.

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.