tailieunhanh - Notes for the course advanced algorithms January 2000

A succession of steadily more powerful and flexible computing devices were constructed in the 1930s and 1940s, gradually adding the key features that are seen in modern computers. The use of digital electronics (largely invented by Claude Shannon in 1937) and more flexible programmability were vitally important steps, but defining one point along this road as "the first digital electronic computer" is 1940 Notable achievements include: | Notes for the course advanced algorithms January 2000 Johan Hastad email johanh@ 2 Contents 1 Introduction 7 2 Notation and basics 9 A couple of basic algorithms. 9 Greatest common divisor . 9 Systems of linear equations. 11 Depth first search . 11 3 Primality testing 13 Chinese remainner theorem. 11 Chinese remainder theorem in practice. 15 The Miller-Rabin primality test. 16 Some notes on the algorithm. 20 Other tests for primality. 20 4 Factoring integers 23 The naive algorithm. 23 Pollard s p-method. 23 A method used by Fermat. 25 Comainine eeqat onn. 22 Implementation tricks. 28 Other methods. 28 Continued fractions . 32 5 Discrete Logarithms 35 A digression. 36 A naive algorithm . 36 The baby step giant step algorithm . 36 Pollard s p-algorithm for discrete logarithms. 37 The algorithm by Pohlig and Hellman. 38 An even faster randomized algorithm. 40 6 Quantum computation 43 Some quantum mechanics. 43 Operating on qubits. 44 Simulating deterministic computations. 46 Relations to other models of computation. 48 Relation to probabilistic models . 48