Igor Shparlinski - Böcker

The theme of this book is the study of the distribution of integer powers modulo a prime number. It provides numerous new, sometimes quite unexpected, links between number theory and computer science as well as to other areas of mathematics. Possible applications include (but are not limited to) complexity theory, random number generation, cryptography, and coding theory. The main method discussed is based on bounds of exponential sums. Accordingly, the book contains many estimates of such sums, including new estimates of classical Gaussian sums. It also contains many open questions and proposals for further research.

This is a survey of achievements in the theory and applications of finite fields and in many related areas such as algebraic number theory, theoretical computer science, coding theory and cryptography. Topics treated include polynomial factorization over finite fields, the finding and distribution of irreducible primitive and other special polynomials, constructing special bases of extensions of finite fields, curves and exponential sums, and linear recurrent sequences. Besides a general overview of the area, its results and methods, it suggests a number of interesting research problems of various levels of difficulty.

“Number Theory and Related Fields” collects contributions based on the proceedings of the "International Number Theory Conference in Memory of Alf van der Poorten," hosted by CARMA and held March 12-16th 2012 at the University of Newcastle, Australia. The purpose of the conference was to promote number theory research in Australia while commemorating the legacy of Alf van der Poorten, who had written over 170 papers on the topic of number theory and collaborated with dozens of researchers. The research articles and surveys presented in this book were written by some of the most distinguished mathematicians in the field of number theory, and articles will include related topics that focus on the various research interests of Dr. van der Poorten.​

“Number Theory and Related Fields” collects contributions based on the proceedings of the "International Number Theory Conference in Memory of Alf van der Poorten," hosted by CARMA and held March 12-16th 2012 at the University of Newcastle, Australia. The purpose of the conference was to promote number theory research in Australia while commemorating the legacy of Alf van der Poorten, who had written over 170 papers on the topic of number theory and collaborated with dozens of researchers. The research articles and surveys presented in this book were written by some of the most distinguished mathematicians in the field of number theory, and articles will include related topics that focus on the various research interests of Dr. van der Poorten.​

The book introduces new techniques that imply rigorous lower bounds on the com­ plexity of some number-theoretic and cryptographic problems. It also establishes certain attractive pseudorandom properties of various cryptographic primitives. These methods and techniques are based on bounds of character sums and num­ bers of solutions of some polynomial equations over finite fields and residue rings. Other number theoretic techniques such as sieve methods and lattice reduction algorithms are used as well. The book also contains a number of open problems and proposals for further research. The emphasis is on obtaining unconditional rigorously proved statements. The bright side of this approach is that the results do not depend on any assumptions or conjectures. On the downside, the results are much weaker than those which are widely believed to be true. We obtain several lower bounds, exponential in terms of logp, on the degrees and orders of o polynomials; o algebraic functions; o Boolean functions; o linear recurrence sequences; coinciding with values of the discrete logarithm modulo a prime p at sufficiently many points (the number of points can be as small as pI/2+O:). These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of special interest since it corresponds to the representation of the rightmost bit of the discrete logarithm and defines whether the argument is a quadratic residue.

This volume contains the refereed proceedings of the Workshop on Cryptography and Computational Number Theory, CCNT'99, which has been held in Singapore during the week of November 22-26, 1999. The workshop was organized by the Centre for Systems Security of the Na­ tional University of Singapore. We gratefully acknowledge the financial support from the Singapore National Science and Technology Board under the grant num­ ber RP960668/M. The idea for this workshop grew out of the recognition of the recent, rapid development in various areas of cryptography and computational number the­ ory. The event followed the concept of the research programs at such well-known research institutions as the Newton Institute (UK), Oberwolfach and Dagstuhl (Germany), and Luminy (France). Accordingly, there were only invited lectures at the workshop with plenty of time for informal discussions. It was hoped and successfully achieved that the meeting would encourage and stimulate further research in information and computer security as well as in the design and implementation of number theoretic cryptosystems and other related areas. Another goal of the meeting was to stimulate collaboration and more active interaction between mathematicians, computer scientists, practical cryptographers and engineers in academia, industry and government.

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. We obtain several lower bounds, exponential in terms of logp, on the de­ grees and orders of • polynomials; • algebraic functions; • Boolean functions; • linear recurring sequences; coinciding with values of the discrete logarithm modulo a prime p at suf­ ficiently many points (the number of points can be as small as pI/He). These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of special interest since it corresponds to the representation of the right­ most bit of the discrete logarithm and defines whether the argument is a quadratic residue. We also obtain non-trivial upper bounds on the de­ gree, sensitivity and Fourier coefficients of Boolean functions on bits of x deciding whether x is a quadratic residue. These results are used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm. For example, we prove that any unbounded fan-in Boolean circuit. of sublogarithmic depth computing the discrete logarithm modulo p must be of superpolynomial size.

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. We obtain several lower bounds, exponential in terms of logp, on the de­ grees and orders of • polynomials; • algebraic functions; • Boolean functions; • linear recurring sequences; coinciding with values of the discrete logarithm modulo a prime p at suf­ ficiently many points (the number of points can be as small as pI/He). These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of special interest since it corresponds to the representation of the right­ most bit of the discrete logarithm and defines whether the argument is a quadratic residue. We also obtain non-trivial upper bounds on the de­ gree, sensitivity and Fourier coefficients of Boolean functions on bits of x deciding whether x is a quadratic residue. These results are used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm. For example, we prove that any unbounded fan-in Boolean circuit. of sublogarithmic depth computing the discrete logarithm modulo p must be of superpolynomial size.

The book introduces new ways of using analytic number theory in cryptography and related areas, such as complexity theory and pseudorandom number generation.Cryptographers and number theorists will find this book useful. The former can learn about new number theoretic techniques which have proved to be invaluable cryptographic tools, the latter about new challenging areas of applications of their skills.

This book provides an exhaustive survey of the most recent achievements in the theory and applications of finite fields and in many related areas such as algebraic number theory, theoretical computer science, coding theory and cryptography. Topics treated include polynomial factorization over finite fields, the finding and distribution of irreducible primitive and other special polynomials, constructing special bases of extensions of finite fields, curves and exponential sums, and linear recurrent sequences. Besides a general overview of the area, its results and methods, it suggests a number of interesting research problems of various levels of difficulty. The volume concludes with an impressive bibliographical section containing more than 2300 references. Audience: This work will be of interest to graduate students and researchers in field theory and polynomials, number theory, symbolic computation, symbolic/algebraic manipulation, and coding theory.