tailieunhanh - Lecture notes on Computer and network security: Lecture 11 - Avinash Kak

Lecture 11, prime numbers and discrete logarithms. The goals of this chapter are: Primality testing, fermat’s little theorem, the totient of a number, the miller-rabin probabilistic algorithm for testing for primality, python and perl implementations for the miller-rabin primality test, the AKS deterministic algorithm for testing for primality, chinese remainder theorem for modular arithmetic with large composite moduli, discrete logarithms. | Lecture 11: Prime Numbers And Discrete Logarithms Lecture Notes on “Computer and Network Security” by Avi Kak (kak@) February 28, 2016 11:20pm c 2016 Avinash Kak, Purdue University Goals: • Primality Testing • Fermat’s Little Theorem • The Totient of a Number • The Miller-Rabin Probabilistic Algorithm for Testing for Primality • Python and Perl Implementations for the Miller-Rabin Primality Test • The AKS Deterministic Algorithm for Testing for Primality • Chinese Remainder Theorem for Modular Arithmetic with Large Composite Moduli • Discrete Logarithms CONTENTS Section Title Page Prime Numbers 3 Fermat’s Little Theorem 5 Euler’s Totient Function 12 Euler’s Theorem 15 Miller-Rabin Algorithm for Primality Testing 18 Miller-Rabin Algorithm is Based on an Intuitive Decomposition of an Even Number into Odd and Even Parts 20 Miller-Rabin Algorithm Uses the Fact that x2 = 1 Has No Non-Trivial Roots in Zp 21 Miller-Rabin Algorithm: Two Special Conditions That Must Be Satisfied By a Prime 24 Consequences of the Success and Failure of One or Both Conditions 28 Python and Perl Implementations of the Miller-Rabin Algorithm 29 Miller-Rabin Algorithm: Liars and Witnesses 38 Computational Complexity of the Miller-Rabin Algorithm 40 The Agrawal-Kayal-Saxena (AKS) Algorithm for Primality Testing 43 Generalization of Fermat’s Little Theorem to Polynomial Rings Over Finite Fields 45 The AKS Algorithm: The Computational Steps 50 Computational Complexity of the AKS Algorithm 52 The Chinese Remainder Theorem A Demonstration of the Usefulness of CRT 53 57 Discrete Logarithms 60 Homework Problems 64 Computer and Network Security by Avi Kak Lecture 11 : PRIME NUMBERS • Prime numbers are extremely important to computer security. As you will see in the next lecture, public-key .

• An ninh - Bảo mật
• Network security
• Lecture notes on Computer and network security
• Computer security
• Prime numbers
• Discrete logarithms
• Euler’s theorem