AN ALGORITHM TO COMPUTE THE DEGREE OF A DICKSON POLYNOMIAL

Year 2021, , 25 - 29, 30.08.2021

Erdal İmamoğlu

https://doi.org/10.20290/estubtdb.841749

Abstract

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

Project Number

119F426

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

Abstract

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.

Keywords

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

Supporting Institution

Türkiye Bilimsel ve Teknolojik Araştırma Kurumu (TÜBİTAK)

Project Number

119F426

References

• [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.