Download presentation

Presentation is loading. Please wait.

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

© 2023 SlidePlayer.com Inc.

All rights reserved.