Number theoretic methods in cryptography. Complexity lower bounds
type: Item
instance of: scholarly article
title: Number theoretic methods in cryptography. Complexity lower bounds
zbMATH Open document ID: 0912.11057
published in: Progress in Computer Science and Applied Logic
publication date: 1999-02-23T00:00:00Z
review text: From the Preface of the book: ``The book introduces new techniques which imply rigorous lower bounds on the complexity of some number theoretic and cryptographic problems. These methods and techniques are based on bounds of character sums and numbers of solutions of some polynomial equations over finite fields and residue rings. It also contains a number of open problems and proposals for further research.'' Much of the book is concerned with obtaining lower bounds on the degrees and orders of polynomials, algebraic functions, Boolean functions and linear recurring sequences that give the discrete logarithm modulo a prime \(p\) on some subset of indices, where it is recalled that the discrete logarithm of an element \(x =g^u\) of the residues modulo \(p\) for some fixed primitive element \(g\) is \(u\), also referred to as the index of \(x\), \(\text{ind}(x)\) for \(u\) the least non-negative integer. One can ask about a polynomial \(f(X) \in Z[X]\) that represents the discrete logarithm in the sense that: \[ \text{ind} (x)\equiv f(x)\bmod{p},\qquad x=1,2, \dots, p-1. \] It is known that the unique interpolation polynomial for this problem is of degree \(p-2\), the largest polynomial degree. Much of the volume is concerned with determining bounds on the degree of such interpolating polynomials for partial representations such as on small intervals of the form \([N+1, N+H]\), very sparse sets or on random sets, using the four types of approximation functions previously mentioned. While studying the congruences modulo the prime \(p\) is natural, since \(\text{ind} (x)\) is in the residue ring modulo \(p-1\), approximations modulo \(p-1\) are also studied. In addition the functions are considered over the residue ring modulo an arbitrary divisor \(d\) of \(p-1\) since the case of \(d=2\) corresponds to the representation of the right-most bit of the discrete logarithm, and also whether the argument is a quadratic residue of the prime. The book is in five parts (fourtee…
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 94-02
Mathematics Subject Classification ID: 11-02
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11T23
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 1253589
zbMATH Keywords: lower bounds on complexity
zbMATH Keywords: open problems
zbMATH Keywords: degrees and orders of polynomials
zbMATH Keywords: algebraic functions
zbMATH Keywords: Boolean functions
zbMATH Keywords: linear recurring sequences
zbMATH Keywords: discrete logarithm
zbMATH Keywords: interpolating polynomials
zbMATH Keywords: Diffie-Hellman cryptosystem
zbMATH Keywords: permutation polynomials
zbMATH Keywords: polynomial representations of nonlinear pseudo-random number generators
zbMATH Keywords: Zech logarithms
zbMATH Keywords: primitive root testing
zbMATH Keywords: RSA generator
zbMATH Keywords: Blum-Blum-Schub generator
zbMATH Keywords: prime field
author: Igor E. Shparlinski
reviewed by: Ian Blake
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1253589