Handbook of Information Security: Information Warfare, Social, Legal, and International Issues and Security Foundations, Volume 2

Number Theory for Information Security

Duncan A. Buell, University of South Carolina

Introduction

References

Divisibility

Notes

Example

Prime Numbers and Factoring

Congruences

Examples

Groups and Fields Defined Mod Primes

Examples

The Chinese Remainder Theorem

Polynomial Arithmetic

Polynomials

Divisibility

Greatest Common Divisor

Irreducible Polynomials

Congruences

Groups, Rings, and Fields Defined Modulo Polynomials

Primitive Polynomials and Shift Register Sequences

Examples

Bit Complexity

Timing Costs of Arithmetic

Worst Case of Greatest Common Divisor

Bit Complexity for Multiprecise Arithmetic

Complexity of Integer Arithmetic

Complexity of Polynomial Arithmetic

Montgomery Multiplication

Cross References

References

INTRODUCTION

The mathematical basis for the algorithms used in public key cryptosystems (RSA, Diffie–Hellman, discrete logarithms, elliptic curves, etc.) relies on some moderately deep concepts and results from number theory, which is covered in the specific chapters on these topics elsewhere in this handbook. Underlying the deep results in number theory, however, are some fundamentals that are almost, but perhaps not quite, obvious. Our purpose in this chapter is to present those parts of the theory of numbers necessary for an understanding of the more advanced material. We begin our discussion with a look at the ordinary integers. Central to work in number theory is the nature of arithmetic (addition, multiplication, and the like) modulo prime numbers. For some purposes, ...