Get 2 days of premium access
Study Guides (380,000)
US (220,000)
Berkeley (5,000)
COMPSCI (500)
Quiz

COMPSCI 70 Study Guide - Quiz Guide: Alistair Sinclair, Public-Key Cryptography, Prime NumberExam


Department
Computer Science
Course Code
COMPSCI 70
Professor
Rao Satish
Study Guide
Quiz

This preview shows page 1. to view the full 4 pages of the document.
CS 70 Discrete Mathematics and Probability Theory
Fall 2018 Alistair Sinclair and Yun Song HW 5
1 Quick Computes
Simplify each expression using Fermat’s Little Theorem.
(a) 333 (mod 11)
(b) 1000110001 (mod 17)
(c) 1010 +2020 +3030 +4040 (mod 7)
Solution:
(a) 333 (mod 11)33·(310)3(mod 11)27 ·13(mod 11)5(mod 11)
(b) 1000110001 (mod 17)100011·(1000116)625 (mod 17)10001 (mod 17)5(mod 17)
(c)
1010 +2020 +3030 +4040 (mod 7)104·106+202·2018
+300·3030 +404·4036 (mod 7)
104+202+300+404(mod 7)
34+62+20+54(mod 7)
34+ (1)2+20+ (2)4(mod 7)
81 +1+1+16 (mod 7)
4+1+1+2(mod 7)1(mod 7)
2 RSA Practice
Bob would like to receive encrypted messages from Alice via RSA.
(a) Bob chooses p=7 and q=11. His public key is (N,e). What is N?
(b) What number is erelatively prime to?
(c) eneed not be prime itself, but what is the smallest prime number ecan be? Use this value for
ein all subsequent computations.
CS 70, Fall 2018, HW 5 1
You're Reading a Preview

Unlock to view full version