TAILIEUCHUNG - 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 .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.