Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Dictionaries and scholars have offered a variety of definitions. The Merriam-Webster dictionary offers a definition of the term: "the practical application of knowledge especially in a particular area" and "a capability given by the practical application of knowledge".[1] Ursula Franklin, in her 1989 "Real World of Technology" lecture, gave another definition of the concept; it is "practice, the way we do things around here".[7] The term is often used to imply a specific field of technology, or to refer to high technology or just consumer electronics, rather than technology as a whole.[8] Bernard Stiegler, in Technics and Time, 1, defines. | Notes for the course advanced algorithms January 2000 Johan Hastad email johanh@nada.kth.se 2 Contents 1 Introduction 7 2 Notation and basics 9 2.1 A couple of basic algorithms. 9 2.1.1 Greatest common divisor . 9 2.1.2 Systems of linear equations. 11 2.1.3 Depth first search . 11 3 Primality testing 13 3.1 Chinese remainner theorem. 11 3.1.1 Chinese remainder theorem in practice. 15 3.2 The Miller-Rabin primality test. 16 3.2.1 Some notes on the algorithm. 20 3.3 Other tests for primality. 20 4 Factoring integers 23 4.1 The naive algorithm. 23 4.2 Pollard s p-method. 23 4.3 A method used by Fermat. 25 4.4 Comainine eeqat onn. 22 4.4.1 Implementation tricks. 28 4.5 Other methods. 28 4.5.1 Continued fractions . 32 5 Discrete Logarithms 35 5.1 A digression. 36 5.2 A naive algorithm . 36 5.3 The baby step giant step algorithm . 36 5.4 Pollard s p-algorithm for discrete logarithms. 37 5.5 The algorithm by Pohlig and Hellman. 38 5.6 An even faster randomized algorithm. 40 6 Quantum computation 43 6.1 Some quantum mechanics. 43 6.2 Operating on qubits. 44 6.3 Simulating deterministic computations. 46 6.4 Relations to other models of computation. 48 6.4.1 Relation to probabilistic models . 48
