A COMPUTATIONAL INTRODUCTION TO NUMBER THEORY AND ALGEBRA

By Q. LIZIY

CONTENTS BASIC PROPERTIES OF THE INTEGERS DIVISIBILITY AND PRIMALITY IDEALS AND GREATEST COMMON DIVISORS SOME CONSEQUENCES OF UNIQUE FACTORIZATION CONGRUENCES DE?NITIONS AND BASIC PROPERTIES SOLVING LINEAR CONGRUENCES RESIDUE CLASSES EULER’S PHI FUNCTION FERMAT’S LITTLE THEOREM ARITHMETIC FUNCTIONS AND M¨OBIUS INVERSION COMPUTING WITH LARGE INTEGERS ASYMPTOTIC NOTATION MACHINE MODELS AND COMPLEXITY THEORY BASIC INTEGER ARITHMETIC COMPUTING IN ZN FASTER INTEGER ARITHMETIC (?) NOTES EUCLID’S ALGORITHM THE BASIC EUCLIDEAN ALGORITHM THE EXTENDED EUCLIDEAN ALGORITHM COMPUTING MODULAR INVERSES AND CHINESE REMAINDERING SPEEDING UP ALGORITHMS VIA MODULAR COMPUTATION RATIONAL RECONSTRUCTION AND APPLICATIONS THE DISTRIBUTION OF PRIMES CHEBYSHEV’S THEOREM ON THE DENSITY OF PRIMES BERTRAND’S POSTULATE MERTENS’ THEOREM THE SIEVE OF ERATOSTHENES THE PRIME NUMBER THEOREM AND BEYOND FINITE AND DISCRETE PROBABILITY DISTRIBUTIONS FINITE PROBABILITY DISTRIBUTIONS: BASIC DE?NITIONS CONDITIONAL PROBABILITY AND INDEPENDENCE RANDOM VARIABLES EXPECTATION AND VARIANCE SOME USEFUL BOUNDS THE BIRTHDAY PARADOX HASH FUNCTIONS STATISTICAL DISTANCE MEASURES OF RANDOMNESS AND THE LEFTOVER HASH LEMMA (?) 6 10 DISCRETE PROBABILITY DISTRIBUTIONS 6 11 NOTES PROBABILISTIC ALGORITHMS BASIC DE?NITIONS APPROXIMATION OF FUNCTIONS FLIPPING A COIN UNTIL A HEAD APPEARS GENERATING A RANDOM NUMBER FROM A GIVEN INTERVAL GENERATING A RANDOM PRIME GENERATING A RANDOM NON-INCREASING SEQUENCE GENERATING A RANDOM FACTORED NUMBER THE RSA CRYPTOSYSTEM ABELIAN GROUPS DE?NITIONS, BASIC PROPERTIES, AND EXAMPLES SUBGROUPS COSETS AND QUOTIENT GROUPS GROUP HOMOMORPHISMS AND ISOMORPHISMS CYCLIC GROUPS THE STRUCTURE OF ?NITE ABELIAN GROUPS (?) RINGS POLYNOMIAL RINGS IDEALS AND QUOTIENT RINGS RING HOMOMORPHISMS AND ISOMORPHISMS PROBABILISTIC PRIMALITY TESTING 10 1 TRIAL DIVISION 10 2 THE STRUCTURE OF Z? N 10 3 THE MILLER–RABIN TEST 10 4 GENERATING RANDOM PRIMES USING THE MILLER–RABIN TEST 10 5 PERFECT POWER TESTING AND PRIME POWER FACTORING 10 6 FACTORING AND COMPUTING EULER’S PHI FUNCTION 10 7 NOTES FINDING GENERATORS AND DISCRETE LOGARITHMS IN Z? P 11 1 FINDING A GENERATOR FOR Z? P 11 2 COMPUTING DISCRETE LOGARITHMS Z? P 11 3 THE DI?E–HELLMAN KEY ESTABLISHMENT PROTOCOL 11 4 NOTES QUADRATIC RESIDUES AND QUADRATIC RECIPROCITY 12 1 QUADRATIC RESIDUES 12 2 THE LEGENDRE SYMBOL 12 3 THE JACOBI SYMBOL 12 4 NOTES COMPUTATIONAL PROBLEMS RELATED TO QUADRATIC RESIDUES 13 1 COMPUTING THE JACOBI SYMBOL 13 2 TESTING QUADRATIC RESIDUOSITY 13 3 COMPUTING MODULAR SQUARE ROOTS 13 4 THE QUADRATIC RESIDUOSITY ASSUMPTION 13 5 NOTES MODULES AND VECTOR SPACES 14 1 DE?NITIONS, BASIC PROPERTIES, AND EXAMPLES 14 2 SUBMODULES AND QUOTIENT MODULES 14 3 MODULE HOMOMORPHISMS AND ISOMORPHISMS 14 4 LINEAR INDEPENDENCE AND BASES 14 5 VECTOR SPACES AND DIMENSION MATRICES 15 1 BASIC DE?NITIONS AND PROPERTIES 15 2 MATRICES AND LINEAR MAPS 15 3 THE INVERSE OF A MATRIX 15 4 GAUSSIAN ELIMINATION 15 5 APPLICATIONS OF GAUSSIAN ELIMINATION 15 6 NOTES SUBEXPONENTIAL-TIME DISCRETE LOGARITHMS AND FACTORING 16 1 SMOOTH NUMBERS 16 2 AN ALGORITHM FOR DISCRETE LOGARITHMS 16 3 AN ALGORITHM FOR FACTORING INTEGERS 16 4 PRACTICAL IMPROVEMENTS 16 5 NOTES MORE RINGS 17 1 ALGEBRAS 17 2 THE ?ELD OF FRACTIONS OF AN INTEGRAL DOMAIN 17 3 UNIQUE FACTORIZATION OF POLYNOMIALS 17 4 POLYNOMIAL CONGRUENCES 17 5 POLYNOMIAL QUOTIENT ALGEBRAS 17 6 GENERAL PROPERTIES OF EXTENSION ?ELDS 17 7 FORMAL POWER SERIES AND LAURENT SERIES 17 8 UNIQUE FACTORIZATION DOMAINS (?) 17 9 NOTES POLYNOMIAL ARITHMETIC AND APPLICATIONS 18 1 BASIC ARITHMETIC 18 2 COMPUTING MINIMAL POLYNOMIALS IN F[X]/(F) (I) 18 3 EUCLID’S ALGORITHM 18 4 COMPUTING MODULAR INVERSES AND CHINESE REMAINDERING 18 5 RATIONAL FUNCTION RECONSTRUCTION AND APPLICATIONS 18 6 FASTER POLYNOMIAL ARITHMETIC (?) 18 7 NOTES LINEARLY GENERATED SEQUENCES AND APPLICATIONS 19 1 BASIC DE?NITIONS AND PROPERTIES 19 2 COMPUTING MINIMAL POLYNOMIALS: A SPECIAL CASE 19 3 COMPUTING MINIMAL POLYNOMIALS: A MORE GENERAL CASE 19 4 SOLVING SPARSE LINEAR SYSTEMS 19 5 COMPUTING MINIMAL POLYNOMIALS IN F[X]/(F) (II) 19 6 THE ALGEBRA OF LINEAR TRANSFORMATIONS (?) 19 7 NOTES FINITE ?ELDS 20 1 PRELIMINARIES 20 2 THE EXISTENCE OF ?NITE ?ELDS 20 3 THE SUB?ELD STRUCTURE AND UNIQUENESS OF ?NITE ?ELDS 20 4 CONJUGATES, NORMS AND TRACES ALGORITHMS FOR ?NITE ?ELDS 21 1 TESTING AND CONSTRUCTING IRREDUCIBLE POLYNOMIALS 21 2 COMPUTING MINIMAL POLYNOMIALS IN F[X]/(F) (III) 21 3 FACTORING POLYNOMIALS: THE CANTOR–ZASSENHAUS ALGORITHM 21 4 FACTORING POLYNOMIALS: BERLEKAMP’S ALGORITHM 21 5 DETERMINISTIC FACTORIZATION ALGORITHMS (?) 21 6 FASTER SQUARE-FREE DECOMPOSITION (?) 21 7 NOTES DETERMINISTIC PRIMALITY TESTING 22 1 THE BASIC IDEA 22 2 THE ALGORITHM AND ITS ANALYSIS 22 3 NOTES