You are previewing Applied Algebra and Number Theory.
O'Reilly logo
Applied Algebra and Number Theory

Book Description

Harald Niederreiter's pioneering research in the field of applied algebra and number theory has led to important and substantial breakthroughs in many areas. This collection of survey articles has been authored by close colleagues and leading experts to mark the occasion of his 70th birthday. The book provides a modern overview of different research areas, covering uniform distribution and quasi-Monte Carlo methods as well as finite fields and their applications, in particular, cryptography and pseudorandom number generation. Many results are published here for the first time. The book serves as a useful starting point for graduate students new to these areas or as a refresher for researchers wanting to follow recent trends.

Table of Contents

  1. Cover
  2. Half-title page
  3. Frontispiece
  4. Title page
  5. Copyright page
  6. Contents
  7. Preface
  8. 1. Some highlights of Harald Niederreiter’s work
    1. 1.1 A short biography
    2. 1.2 Uniform distribution theory and number theory
    3. 1.3 Algebraic curves, function fields and applications
    4. 1.4 Polynomials over finite fields and applications
    5. 1.5 Quasi-Monte Carlo methods
    6. References
  9. 2. Partially bent functions and their properties
    1. 2.1 Introduction
    2. 2.2 Basic properties
    3. 2.3 Examples and constructions
    4. 2.4 Partially bent functions and difference sets
    5. 2.5 Partially bent functions and Hermitian matrices
    6. 2.6 Relative difference sets revisited: a construction of bent functions
    7. References
  10. 3. Applications of geometric discrepancy in numerical analysis and statistics
    1. 3.1 Introduction
    2. 3.2 Numerical integration in the unit cube
    3. 3.3 Numerical integration over the unit sphere
    4. 3.4 Inverse transformation and test sets
    5. 3.5 Acceptance-rejection sampler
    6. 3.6 Markov chain Monte Carlo and completely uniformly distributed sequences
    7. 3.7 Uniformly ergodic Markov chains and push-back discrepancy
    8. References
  11. 4. Discrepancy bounds for low-dimensional point sets
    1. 4.1 Introduction
    2. 4.2 Upper discrepancy bounds for low-dimensional sequences
    3. 4.3 Upper discrepancy bounds for low-dimensional nets
    4. 4.4 Lower discrepancy bounds for low-dimensional point sets
    5. 4.5 Conclusion
    6. References
  12. 5. On the linear complexity and lattice test of nonlinear pseudorandom number generators
    1. 5.1 Introduction
    2. 5.2 Lattice test and quasi-linear complexity
    3. 5.3 Quasi-linear and linear complexity
    4. 5.4 Applications of our results
    5. 5.5 An open problem
    6. References
  13. 6. A heuristic formula estimating the keystream length for the general combination generator with respect to a correlation attack
    1. 6.1 The combination generator
    2. 6.2 The model
    3. 6.3 Preliminaries
    4. 6.4 The correlation attack
    5. 6.5 The formula
    6. References
  14. 7. Point sets of minimal energy
    1. 7.1 Introduction
    2. 7.2 Generalized energy and uniform distribution on the sphere
    3. 7.3 Hyper-singular energies and uniform distribution
    4. 7.4 Discrepancy estimates
    5. 7.5 Some remarks on lattices
    6. References
  15. 8. The cross-correlation measure for families of binary sequences
    1. 8.1 Introduction
    2. 8.2 The definition of the cross-correlation measure
    3. 8.3 The size of the cross-correlation measure
    4. 8.4 A family with small cross-correlation constructed using the Legendre symbol
    5. 8.5 Another construction
    6. References
  16. 9. On an important family of inequalities of Niederreiter involving exponential sums
    1. 9.1 Introduction
    2. 9.2 Concepts
    3. 9.3 A hybrid Erdos–Turán–Koksma inequality
    4. References
  17. 10. Controlling the shape of generating matrices in global function field constructions of digital sequences
    1. 10.1 Introduction
    2. 10.2 Global function fields
    3. 10.3 Constructions revisited
    4. 10.4 Designing morphological properties of the generating matrices
    5. 10.5 Computational results
    6. 10.6 Summary and outlook
    7. References
  18. 11. Periodic structure of the exponential pseudorandom number generator
    1. 11.1 Introduction
    2. 11.2 Preparations
    3. 11.3 Main results
    4. 11.4 Numerical results on cycles in the exponential map
    5. 11.5 Comments
    6. References
  19. 12. Construction of a rank-1 lattice sequence based on primitive polynomials
    1. 12.1 Introduction
    2. 12.2 Integro-approximation by rank-1 lattice sequences
    3. 12.3 Construction
    4. 12.4 Applications
    5. 12.5 Conclusion
    6. References
  20. 13. A quasi-Monte Carlo method for the coagulation equation
    1. 13.1 Introduction
    2. 13.2 The quasi-Monte Carlo algorithm
    3. 13.3 Convergence analysis
    4. 13.4 Numerical results
    5. 13.5 Conclusion
    6. References
  21. 14. Asymptotic formulas for partitions with bounded multiplicity
    1. 14.1 Introduction
    2. 14.2 Asymptotic expansion of M[sub(U,q)]
    3. 14.3 Proof of Theorem 14.2
    4. References
  22. 15. A trigonometric approach for Chebyshev polynomials over finite fields
    1. 15.1 Introduction
    2. 15.2 Trigonometry in finite fields
    3. 15.3 Chebyshev polynomials over finite fields
    4. 15.4 Periodicity and symmetry properties of Chebyshev polynomials over finite fields
    5. 15.5 Permutation properties of Chebyshev polynomials over finite fields
    6. 15.6 Conclusions
    7. References
  23. 16. Index bounds for value sets of polynomials over finite fields
    1. 16.1 Introduction
    2. 16.2 Value sets of univariate polynomials
    3. 16.3 Permutation polynomial vectors
    4. References
  24. 17. Rational points of the curve y[sup(q)[sup(n)]] − y = γx[sup(q)[sup(h)]][sup(+1)] − α over F[sub(q)sup(m)]
    1. 17.1 Introduction
    2. 17.2 Preliminaries
    3. 17.3 Proof of the main theorem
    4. References
  25. 18. On the linear complexity of multisequences, bijections between Zahlen and Number tuples, and partitions
    1. 18.1 Introduction and notation
    2. 18.2 Single sequences
    3. 18.3 Multilinear complexity
    4. 18.4 Partitions, bijections, conjectures
    5. 18.5 Open questions and further research
    6. 18.6 Conclusion
    7. References