1 / 21

# CSC2110 Discrete Mathematics Tutorial 6 Chinese Remainder Theorem, RSA and Primality Test - PowerPoint PPT Presentation

CSC2110 Discrete Mathematics Tutorial 6 Chinese Remainder Theorem, RSA and Primality Test. Hackson Leung. 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

I am the owner, or an agent authorized to act on behalf of the owner, of the copyrighted work described.

## PowerPoint Slideshow about 'CSC2110 Discrete Mathematics Tutorial 6 Chinese Remainder Theorem, RSA and Primality Test' - anastacia

Download Policy: Content on the Website is provided to you AS IS for your information and personal use and may not be sold / licensed / shared on other websites without getting consent from its author.While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server.

- - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - -
Presentation Transcript

### CSC2110 Discrete MathematicsTutorial 6Chinese Remainder Theorem, RSA and Primality Test

Hackson Leung

• Homework Set 2 is released!

• 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

• Chinese Remainder Theorem

• RSA

• Primality Test

• Example 1

• Solve for

• Since

• Then 3-1 exists and

• Therefore,

• Example 2

• Solve for

• Since

• We reduce it to

• Same as example 1

• What if ?

• Solve the following

• Consider so that

• Step 1: Let

• Step 2: Construct

• 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

• Example 1

• Solve for largest such that

• Step 1:

• Step 2:

• Step 3:

• Step 4:

• Step 5:

• What if ?

• We can always reduce them

• Example 2

• Solve the largest such that

• Analyze first

• Thus, we have

• Take a look at

• So

• Same as example 1

• We want s to be relatively prime only!

• Step 1: , and very large prime

• Step 2:

• Step 3: Choose

• Step 4: Find

• Public key:

• Private key:

• Example 1

• Let

• Give the public and private keys in RSA cryptosystem

• Step 1:

• Step 2:

• Step 3: , the choice is ok

• Step 4:

• Public key:

• Private key:

• Example 2: Encrypt 5

• Example 3: Decrypt

• Example 3

• 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

• 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
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}