BİR DİCKSON POLİNOMUNUN DERECESİNİ HESAPLAMAK İÇİN BİR ALGORİTMA

Bu çalışmada, bir birinci tür Dickson Polinomu'nun bir noktada bilinen bir değerinden derecesini kesaplayan bir algoritma tarif edilmiştir. Algoritma, birinci tür Dickson Polinomları ile birinci tür Çebişev Polinomları arasındaki bir matematiksel eşitliği baz almaktadır.

Anahtar Kelimeler:

Sembolik Hesaplama, Algoritmalar, Dickson Polinomları, Pohlig-Hellman Algoritması

AN ALGORITHM TO COMPUTE THE DEGREE OF A DICKSON POLYNOMIAL

In this study, we describe an algorithm that computes the degree of a Dickson Polynomial of the First Kind from its known value at a point. Our algorithm is based on a mathematical relation between Dickson Polynomials of the First Kind and Chebyshev Polynomials of the First Kind.

Keywords:

Symbolic Computation, Algorithms, Dickson Polynomials, Pohlig-Hellman Algorithm,

PDF

___

[1] Dickson LE. The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group. Ann Math 1896; 1; 6, 65-120.
[2] Wang Q, Yucas JL. Dickson polynomials over finite fields. Finite Fields Th App 2012; 18, 4, 814-831.
[3] Dominici D. Orhogonality of the Dickson polynomials of the (k+1)-th kind. https://arxiv.org/abs/2011.10673, 2020.
[4] Imamoglu E, Kaltofen EL. On computing the degree of a Chebyshev polynomial from its value. J Symb Comput 2021; 104, 159-167, In press.
[5] Pohlig S, Hellman M. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE T Inform Theory 1978; 24, 1, 106-110.
[6] Menezes AJ, Vanstone SA, Van Oorschost PC. Handbook of applied cryptography. Boca Raton, FL, CRC Press, 1996.