ЖОҒАРЫ РЕТТІ АҚЫРЛЫ ӨРІСТІҢ ПРИМИТИВТІ ЭЛЕМЕНТТЕРІН ІЗДЕУ АЛГОРИТМДЕРІН ЗЕРТТЕУ

Ақырлы өрістерді есептеу теориясындағы ең маңызды шешілмеген және күрделі мәселелердің бірі ақырлы өрісте алғашқы түбірлерді құрудың жылдам алгоритмін дайындау. Екінші жағынан, көптеген қосымшалар үшін алғашқы түбірдің орнына жоғары мультипликативті ретті элемент жеткілікті. Мұндай қосымшаларға криптография, кодтау теориясы, псевдокездейсоқ сандар генерациясы және комбинаторлық схемалар кіреді, бірақ олармен шектелмейді. Жоғары ретті элементтердің айқын құрылыстары әдетте дәлелденетін төменгі реттік шекараны қамтамасыз ете алатын комбинаторика әдістеріне сүйенеді, бірақ бұл нақты ретті есептемейді. Оны орындау әдетте ретті факторизациялауды білуді білдіреді. Ең дұрысы, саналы уақыт ішінде кез келген ақырлы өріс үшін примитивті элементті ала алуымыз керек. Алайда егер топтық реттің қарапайым факторизациясы белгісіз болса, мақсатқа қалай жетуге болатыны белгісіз. Осылайша, мүмкіндігінше жоғары ретті элементті құру есебін қоямыз. Бұл мақалада жалпы немесе арнайы ақырлы өрістер үшін жоғары ретті элементті табатын әртүрлі алгоритмдер қарастырылады. Сонымен қатар ұсынылған жұмыс ақырлы өрістердегі Гаусс кезеңдерінің теориясына тағы бір үлес қосады және олардың әртүрлі қосымшалар үшін пайдалы екендігін дәлелдеген жалпылаулары мен аналогтар болады.

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.