Đang chuẩn bị liên kết để tải về tài liệu:
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@purdue.edu) 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 11.1 Prime Numbers 3 11.2 Fermat’s Little Theorem 5 11.3 Euler’s Totient Function 12 11.4 Euler’s Theorem 15 11.5 Miller-Rabin Algorithm for Primality Testing 18 11.5.1 Miller-Rabin Algorithm is Based on an Intuitive Decomposition of an Even Number into Odd and Even Parts 20 11.5.2 Miller-Rabin Algorithm Uses the Fact that x2 = 1 Has No Non-Trivial Roots in Zp 21 11.5.3 Miller-Rabin Algorithm: Two Special Conditions That Must Be Satisfied By a Prime 24 11.5.4 Consequences of the Success and Failure of One or Both Conditions 28 11.5.5 Python and Perl Implementations of the Miller-Rabin Algorithm 29 11.5.6 Miller-Rabin Algorithm: Liars and Witnesses 38 11.5.7 Computational Complexity of the Miller-Rabin Algorithm 40 11.6 The Agrawal-Kayal-Saxena (AKS) Algorithm for Primality Testing 43 11.6.1 Generalization of Fermat’s Little Theorem to Polynomial Rings Over Finite Fields 45 11.6.2 The AKS Algorithm: The Computational Steps 50 11.6.3 Computational Complexity of the AKS Algorithm 52 11.7 11.7.1 The Chinese Remainder Theorem A Demonstration of the Usefulness of CRT 53 57 11.8 Discrete Logarithms 60 11.9 Homework Problems 64 Computer and Network Security by Avi Kak Lecture 11 11.1: PRIME NUMBERS • Prime numbers are extremely important to computer security. As you will see in the next lecture, public-key .