Number theory with cryptographic applications / by Barış Kendirli.

Includes bibliographical references (pages 521) and index.

Contents 1 Introduction 1 2 Divisibility Properties of Integers 5 2.1 The Greatest Common Divisor 10 2.2 Linear Diophantirıe equations 16 2.3 Primes 19 2.4 Fermat Faetorization 27 3 Congruences 31 3.1 Arithmetic Inverse: 36 3.2 Linear Congruence 39 3.3 Fermat's Little Theorem 45 4 Cryptography 54 4.1 Substitution Ciphers 54 4.2 Block Ciphers 63 4.3 Public- Key Cryptography 68 5 Polynornial Congruences 75 5.1 Chinese Remainder Theorem 75 5.2 Solutions of congruences modulo prime power 78 5.3 Reduction of polynomials 88 6 Primitive Roots: 95 6.1 Existence of primitive root modulo prime 98 6.2 Translation of muitiplicative problems into additive problems 103 6.3 Application to Cryptography 111 7 Quadratic Polynomial 113 7.1 Quadratic Residues 117 7.2 The Law of Quadratic Reciprocity (GAUSS) 120 7.3 Application to Diophantine Equations 126 7.4 Jacobi Symbol 129 8 Arithmetic Functions 134 8.1 Dirichlet Series 148 8.2 Euler Products 152 9 Some Nonlinear Diophantine Equations 160 9.1 The Equation x2 + y2 = z2 161 9.2 The equation x4+y4=z2 167 9.3 FERMAT'S Last Theorem and the equation x4+y4=z4 168 9.4 The Equation n=x2+y2+z2+w2 169 10 Continued Fractions: 172 10.1 Infinite Continued Fractions 182 10.2 Periodic continued fractions 184 10.3 Pell's Equation x2 ~ dy2 = n for d > 0 192 11 Primality Testing and Factoring 199 11.1 Factorization by Continued Fraction 207 11.2 Thep-1 Factoring Algorithm(Pollard) 211 11.3 Rho-Method(Poüard) 212 11.4 Factor Base Method 214 11.5 Quadratic Sieve Method 223 12 Quadratic Fields 226 12.1 Gaussian Integers 226 12.2 General Quadratic Fields 239 13 Binary Quadratic Forms 247 13.1 Connection Between Binary Quadratic Forms and free Z inodules of rank 2 in Quadratic Fields 248 13.2 The Correspondence between Binary Quadratic Forms and Free Z Modules of rank 2 252 13.3 The order of a free Z modüle of rank 2 259 14 Units in orders 267 14.1 Determination of Elements of a Free Z Modüle of Rank 2 whose norms are a given rational number 276 15 Factorization in the Orders of Quadratic Fields 291 15.1 Properties of Ideals in Od 299 16 Product of free % modules of rank 2 315 16.1 The factorization of prime integers in Q(Vd) 334 17 Kronecker Symbol 344 17.1 Class Number: 350 17.2 Application to Diophantine Equations 358 17.3 More about L functions 365 18 More on Binary Quadratic Forms 372 18.1 The Representation of Integers by Binary Quadratic Forms 385 18.2 Operations on binary quadratic forms 394 18.3 Genus Theory 410 19 Elliptic Curves 430 19.1 The Group Structure of an Elliptic Curve 434 19.2 Rational Points on Elliptic Curves 448 20 Finite Fields 458 20.1 Some Maple Applications on Finite Fields 464 21 Application to Cryptography 471 21.1 Finite Field Cryptosystems 471 21.2 Elliptic Curve Cryptosystems 490 22 TABLES 503