Polynomial representations of the Lucas logarithm (Q2500606)

The authors provide results that are of interest for cryptosystems depending on the discrete logarithm problem. They look at the intractability of the so-called Lucas problem, which turns out to be computationally equivalent to the discrete logarithm problem over finite fields \(\mathbb F_{p^2}\). Moreover, they provide precise formulas for polynomials representing the Lucas algorithm. They also develop lower bounds on the degree of interpolation polynomials for the Lucas logarithm with respect to subsets of given data.