# CSC2110 Discrete Mathematics Tutorial 6 Chinese Remainder Theorem, RSA and Primality Test Hackson Leung.

Fermat’s Little Theorem examples
Fermat’s Little Theorem examples

1
CSC2110 Discrete Mathematics Tutorial 6 Chinese Remainder Theorem, RSA and Primality Test Hackson Leung

2
Announcement Homework Set 2 is released! Deadline – 30 Oct 17:00 Sharp – No late submission is accepted – Submit at the drop box near SHB 924 Project – Those who have not registered, we assigned for you, please check CUHK email

3
Agenda Chinese Remainder Theorem RSA Primality Test

4
Chinese Remainder Theorem Example 1 – Solve for – Since – Then 3 -1 exists and – Therefore,

5
Chinese Remainder Theorem Example 2 – Solve for – Since – We reduce it to – Same as example 1 – What if ? Contradiction!

6
Chinese Remainder Theorem Solve the following

7
Chinese Remainder Theorem Consider so that Step 1: Let Step 2: Construct

8
Chinese Remainder Theorem Step 3: Find the multiplicative inverse of – Remember how to find multiplicative inverse? – Extended Euclid’s Algorithm! Step 4: Step 5: Adjust to meet the requirement

9
Chinese Remainder Theorem Example 1 Solve for largest such that

10
Chinese Remainder Theorem Step 1: Step 2: Step 3: Step 4: Step 5:

11
Chinese Remainder Theorem What if ? We can always reduce them Example 2 – Solve the largest such that

12
Chinese Remainder Theorem Analyze first Thus, we have

13
Chinese Remainder Theorem Take a look at So Same as example 1 We want s to be relatively prime only!

14
RSA Step 1:, and very large prime Step 2: Step 3: Choose Step 4: Find Public key: Private key:

15
RSA Example 1 – Let – Give the public and private keys in RSA cryptosystem

16
RSA Step 1: Step 2: Step 3:, the choice is ok Step 4:

17
RSA Public key: Private key: Example 2: Encrypt 5 Example 3: Decrypt

18
RSA Example 3

19
Primality Test Step 1: Pick a random number, set Step 2: Calculate Step 3: If not 1 (and not -1), composite, done Step 4: If -1, “probably” prime, done Step 5: If 1 and k is odd, “probably” prime, done Step 6:, go back to step 2 Check when k < n – 1

20
Primality Test Example: Test if 221 is prime Pick 174 to test Under this test, 221 is “probably” prime Pick 137 to test We are sure 221 is composite! 174: strong liar, 137: witness

21
The End

Similar presentations