+612 9045 4394
Primes and Programming - Peter J. Giblin

Primes and Programming

Paperback Published: 1st November 1993
ISBN: 9780521409889
Number Of Pages: 252

Share This Book:


Ships in 10 to 15 business days

Peter Giblin describes, in the context of an introduction to the theory of numbers, some of the more elementary methods for factorization and primality testing; that is, methods independent of a knowledge of other areas of mathematics. Indeed everything is developed from scratch so the mathematical prerequisites are minimal. An essential feature of the book is the large number of computer programs (written in Pascal) and a wealth of computational exercises and projects, in addition to more usual theory exercises. The theoretical development includes continued fractions and quadratic residues, directed always towards the two fundamental problems of primality testing and factorization. There is time, all the same, to include a number of topics and projects of a purely "recreational" nature.

"An interesting, sophisticated introduction to number theory..." American Mathematical Monthly "Of the many volumes I have seen about 'number theory and computing', this delightful, if unorthodox, introductory text is probably the finest...a great strength of this book is its emphasis on computing and on computing examples. There are several programs included in the text, often different algorithms for achieving the same computational result, and both theoretical and practical reasons for preferring one method over another are discussed. The programming language is Pascal, which is perfectly appropriate...[and] there are a great many numerial exercises and examples...only the deadest of students could possibly consider this dry; the author has brought life and energy to the subject by his presentation." Duncan Buell, Mathematical Reviews

Prefacep. vii
Logical dependence of chaptersp. xi
The Fundamental Theorem, Greatest Common Divisors and Least Common Multiplesp. 1
Primes and the fundamental theoremp. 1
Greatest common divisor and least common multiplep. 7
Euclid's algorithm for the gcdp. 12
[x] and applicationsp. 24
Further projectsp. 29
Listing Primesp. 37
Primes by divisionp. 37
Primes by multiplication (elimination of composites)p. 50
Approximations to [pi](x)p. 52
The sieve of Eratosthenesp. 55
Congruencesp. 69
Congruences: basic propertiesp. 69
Inverses mod m and solutions of certain congruencesp. 74
Further examples of congruencesp. 81
Powers and Pseudoprimesp. 86
Fermat's (little) theoremp. 86
The power algorithmp. 89
Head's algorithm for multiplication mod mp. 93
Pseudoprimesp. 98
Wilson's theoremp. 102
Miller's Test and Strong Pseudoprimesp. 104
Miller's testp. 104
Probabilistic primality testingp. 109
Euler's Theorem, Orders and Primality Testingp. 112
Euler's function (the [phis]-function or totient function)p. 112
Euler's theorem and the concept of orderp. 119
Primality testsp. 124
Periods of decimalsp. 130
Cryptographyp. 133
Exponentiation ciphersp. 134
Public key cryptography: RSA ciphersp. 136
Coin-tossing by telephonep. 145
Primitive Rootsp. 147
Properties and applications of primitive rootsp. 147
Existence and nonexistence of primitive rootsp. 149
The Number of Divisors d and the Sum of Divisors [sigma]p. 158
The function d(n)p. 158
Multiplicative functions and the sum function [sigma](n)p. 162
Tests for primality of the Mersenne numbers 2[superscript m] - 1p. 170
Continued Fractions and Factoringp. 174
Continued fractions: initial ideas and definitionsp. 175
The continued fraction for [square root]np. 180
Proofs of some properties of continued fractionsp. 186
Pell's equationp. 189
The continued fraction factoring methodp. 191
Quadratic Residuesp. 200
Definitions and examplesp. 200
The quadratic character of 2p. 203
Quadratic reciprocityp. 206
The Jacobi symbol and a program for finding (n/p)p. 211
Solving the equation x[superscript 2] [identical with] a (mod p): quadratic congruencesp. 217
Bibliographyp. 225
Indexp. 231
Index of Listed Programsp. 236
Index of Notationp. 237
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9780521409889
ISBN-10: 0521409888
Audience: Tertiary; University or College
Format: Paperback
Language: English
Number Of Pages: 252
Published: 1st November 1993
Country of Publication: GB
Dimensions (cm): 22.5 x 14.99  x 1.45
Weight (kg): 0.36

This product is categorised by