Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\).
type: Item
instance of: scholarly article
title: Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\).
zbMATH Open document ID: 1039.94007
DOI: 10.1016/S0166-218X(02)00445-6
author: Tanja Lange
author: Arne Winterhof
published in: Discrete Applied Mathematics
publication date: 2003-06-10T00:00:00Z
review text: \textit{I. E. Shparlinski} [Number theoretic methods in cryptography, Prog. Comput. Sci. Appl. Logic 17. Birkhäuser, Basel (1999; Zbl 0912.11057)] established several complexity lower bounds on the discrete logarithm in finite prime fields. These results are extended to arbitrary finite fields of odd characteristic. In detail, complexity lower bounds for Boolean functions representing the least significant bit of the discrete logarithm are shown. Furthermore, lower bounds on the sparsity and the degree of polynomials over \(GF(q)\) in several variables computing the discrete logarithm modulo a prime divisor of \(q-1\) are given. The latter results are valid for characteristic 2 as well. Most of the proofs are based on bounds for character sums.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 1925282
reviewed by: Harald Niederreiter
MaRDI profile type: Publication
cites work: On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping.
cites work: A class of Boolean functions with linear combinational complexity
cites work: Q4699308
cites work: On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
cites work: Q4312125
cites work: Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
cites work: Incomplete character sums over finite fields and their application to the interpolation of the discrete logarithm by Boolean functions
cites work: Constant depth circuits, Fourier transform, and learnability
cites work: Q4839061
cites work: Reducing elliptic curve logarithms to logarithms in a finite field
cites work: Q4718481
cites work: A polynomial representation for logarithms in GF(q)
cites work: Incomplete character sums and polynomial interpolation of the discrete logarithm
cites work: Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
cites work: Equations over finite fields. An elementary approach
cites work: Q4699468
cites work: Q3762226
cites work: Some estimates for character sums and applications
cites work: Polynomial interpolation of the discrete logarithm
full work available at URL: s0166-218x(02)00445-6
OpenAlex ID: W2067307917
Recommended article: Interpolation of the discrete logarithm in finite fields by Boolean functions
Recommended article: Polynomial interpolation of the discrete logarithm
Recommended article: Polynomial Interpolation of the k-th Root of the Discrete Logarithm
Recommended article: Incomplete character sums over finite fields and their application to the interpolation of the discrete logarithm by Boolean functions
Recommended article: Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a finite field
Recommended article: Q3539814
Recommended article: Incomplete character sums and polynomial interpolation of the discrete logarithm
Recommended article: Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
Recommended article: Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem
Recommended article: Q4314374
description: scientific article; zbMATH DE number 1925282