Skip to main content
SpringerLink
Log in
Birkhäuser

Cryptographic Applications of Analytic Number Theory

Complexity Lower Bounds and Pseudorandomness

  • Book
  • © 2003

Overview

Editors:
  1. Igor Shparlinski

    1. Department of Computing, Macquarie University, Australia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Progress in Computer Science and Applied Logic (PCS, volume 22)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (33 chapters)

  1. Front Matter

    Pages i-ix
    Download chapter PDF

  2. Introduction

    1. Introduction

      • Igor Shparlinski
      Pages 1-14

  3. Preliminaries

    1. Front Matter

      Pages 15-15
      Download chapter PDF

    2. Basic Notation and Definitions

      • Igor Shparlinski
      Pages 17-26

    3. Polynomials and Recurrence Sequences

      • Igor Shparlinski
      Pages 27-36

    4. Exponential Sums

      • Igor Shparlinski
      Pages 37-60

    5. Distribution and Discrepancy

      • Igor Shparlinski
      Pages 61-65

    6. Arithmetic Functions

      • Igor Shparlinski
      Pages 67-81

    7. Lattices and the Hidden Number Problem

      • Igor Shparlinski
      Pages 83-102

    8. Complexity Theory

      • Igor Shparlinski
      Pages 103-106

  4. Approximation and Complexity of the Discrete Logarithm

    1. Front Matter

      Pages 107-107
      Download chapter PDF

    2. Approximation of the Discrete Logarithm Modulo p

      • Igor Shparlinski
      Pages 109-122

    3. Approximation of the Discrete Logarithm Modulo p — 1

      • Igor Shparlinski
      Pages 123-128

    4. Approximation of the Discrete Logarithm by Boolean Functions

      • Igor Shparlinski
      Pages 129-141

    5. Approximation of the Discrete Logarithm by Real Polynomials

      • Igor Shparlinski
      Pages 143-156

  5. Approximation and Complexity of the Diffie—Hellman Secret Key

    1. Front Matter

      Pages 157-157
      Download chapter PDF

    2. Polynomial Approximation and Arithmetic Complexity of the Diffie-Hellman Secret Key

      • Igor Shparlinski
      Pages 159-177

    3. Boolean Complexity of the Diffie-Hellman Secret Key

      • Igor Shparlinski
      Pages 179-188

    4. Bit Security of the Diffie—Hellman Secret Key

      • Igor Shparlinski
      Pages 189-194

  6. Other Cryptographic Constructions

    1. Front Matter

      Pages 195-195
      Download chapter PDF
Back to top

Keywords

About this book

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.

Reviews

From the reviews:

“Igor Shparlinski is a very prolific mathematician and computer scientist … . The book is written at a very high level, suitable for graduate students and researchers in computer science and mathematics. … book has a unique perspective, and is not really comparable to other books in the area. … book contains many deep results, and the mathematically-sophisticated reader can find much that is novel. … this is an impressive work that will be of significant interest to researchers in cryptography and algorithmic number theory.” (Jeffrey Shallit, SIGACT News, Vol. 41 (3), September, 2010)

Editors and Affiliations

  • Department of Computing, Macquarie University, Australia

    Igor Shparlinski

Bibliographic Information

  • Book Title: Cryptographic Applications of Analytic Number Theory

  • Book Subtitle: Complexity Lower Bounds and Pseudorandomness

  • Editors: Igor Shparlinski

  • Series Title: Progress in Computer Science and Applied Logic

  • DOI: https://doi.org/10.1007/978-3-0348-8037-4

  • Publisher: Birkhäuser Basel

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer Basel AG 2003

  • Hardcover ISBN: 978-3-7643-6654-4Published: 11 December 2002

  • Softcover ISBN: 978-3-0348-9415-9Published: 03 October 2013

  • eBook ISBN: 978-3-0348-8037-4Published: 07 March 2013

  • Series ISSN: 2297-0576

  • Series E-ISSN: 2297-0584

  • Edition Number: 1

  • Number of Pages: IX, 414

  • Topics: Number Theory, Cryptology, Applications of Mathematics

Publish with us

Policies and ethics

Back to top

Search

Navigation