The Gao approach to construction of high order elements in arbitrary finite fields is to choose a convenient polynomial, which defines an extension of an initial prime field. This choice depends on one polynomial-parameter. That is why the mentioned approach can be considered as using of a finite field description with one degree of freedom. We explore in the paper the possibility of improvement of lower bound on element orders in finite fields of general form with using of two degrees of freedom. We have performed computer calculations in Maple environment, that would show possible winnings in this case, and given the correspondent results. Elements of high multiplicative order are used in a series of cryptographic primitives (Diffie-Hellman protocol, El-Gamal public key cryptosystem, El-Gamal digital signature).
[1] Agrawal M., Kayal N., Saxena N. PRIMES is in P // Annals of Mathematics, vol. 160, no. 2, 2004, p. 781-793. https://doi.org/10.4007/annals.2004.160.781
[2] Ahmadi O., Shparlinski I. E., Voloch J. F. Multiplicative order of Gauss periods // International Journal of Number Theory, vol. 6, no. 4, 2010, p. 877-882. https://doi.org/10.1142/S1793042110003290
[3] Conflitti A. On elements of high order in finite fields // in Cryptography and Computational Number Theory, vol. 20 of Progr. Comput. Sci. Appl. Logic, Birkhauser, Basel, 2001, p. 11-14. https://doi.org/10.1007/978-3-0348-8295-8_2
[4] Gao S. Elements of provable high orders in finite fields // Proceeding of American Math. Soc., vol. 127, no. 6, 1999, p. 1615-1623. https://doi.org/10.1090/S0002-9939-99-04795-4
[5] Lidl R., Niederreiter H. Finite Fields. - Cambridge: Cambridge University Press, 1997. 755 P. https://doi.org/10.1017/CBO9780511525926
[6] Mullen G. L., Panario D. Handbook of finite fields. Boca Raton: CRC Press, 2013. 1068 P. https://doi.org/10.1201/b15006
[7] Lambe T. A. Bounds on the Number of Feasible Solutions to a Knapsack Problem // SIAM Journal of Applied Mathematics, vol. 26, no. 2, 1974, p. 302-305. https://doi.org/10.1137/0126027
[8] Popovych R. Elements of high order in finite fields of the form Fq[x]/Φr(x) // Finite Fields and Their Applications, vol. 18, no. 4, 2012, p. 700-710.
[9] Popovych R. Elements of high order in finite fields of the form Fq[x]/(xm-a) // Finite Fields and Their Applications, vol. 19, no. 1, 2013, p. 86-92.
[10] Popovych R. On elements of high order in general finite fields // Algebra and Discrete Mathematics, vol. 18, no. 2, 2014, p. 295-300.
[11] Popovych B. Kompyuterna perevirka prypushchennya Gao, povyazanogo z otrymannyam elementiv velykogo poryadku v skinchennuch polyakh // Lvivska politechnika, Kompyuterni systemy ta merezhi, No. 905, 2018, s. 108-110.
[12] Young M. On the multiplicative independence of rational iterates, Preprint, 2018, available at https://arxiv.org/abs/1708.00944.