## CS 235 - Algebraic Algorithm [Fall 2014] - Andrei Lapets - Discussion session whiteboard

Course Page: http://cs-people.bu.edu/lapets/235/

Sessions: Wed. 4 pm - 5 pm in MCS B19; 5 pm - 6 pm in CAS 312

Office Hours:

Mon. 6:30 pm - 8 pm in CS Lab (I also hold tutoring hours from 4 pm - 6 pm)

Wed. 12:30 pm - 2 pm in CS Lab

Email: at the bottom of this page

Piazza: https://piazza.com/bu/fall2014/cs235/home

Link to Andrej's

Sessions: Wed. 4 pm - 5 pm in MCS B19; 5 pm - 6 pm in CAS 312

Office Hours:

Mon. 6:30 pm - 8 pm in CS Lab (I also hold tutoring hours from 4 pm - 6 pm)

Wed. 12:30 pm - 2 pm in CS Lab

Email: at the bottom of this page

Piazza: https://piazza.com/bu/fall2014/cs235/home

Link to Andrej's

**Random Exercise Generator**: http://cs-people.bu.edu/lapets/235/exercises.php**Class notes (in the reverse chronological order)**

Warning: Notes of discussion session is not always online.

Taking hand-written notes are usually helpful (esp. for understanding math)

Contents of { } or ''' ''' are usually useful/interesting facts/ideas/shower-time thoughts that are out of the scope of the class.

**Notes 13 - Dec. 10 - "How to make the cheating sheet?"**

0. Basics (You should have known without cheating sheet, well, in case...)

0.1 Notation of sets: groups, congruence class, algebraic closure, ... are all sets!

__Example 1: let OP be "+ mod 5", what is closure({2}, OP)?__

__Example 2: let S = { [a,b,c] | [a,b,c] is a permutation, a, b, c from {0,1,2}}, what's the size of S?__

__Example 2.i (take home question: try to express S as generated by closure)__

0.2 Fermat's little Theorem, the basic applications, its extension (Euler's theorem)

__Example 3: calculate 2^101 mod 101__

Example 4: calculate 3^101+2^101 mod 101

Example 5: calculate inv(2) mod 101

Example 4: calculate 3^101+2^101 mod 101

Example 5: calculate inv(2) mod 101

0.F Do copy other definitions / notations that you cannot remember!

1. Solving (systems of) equations in the congruence classes:

Step 1: Staring at each of them, if there are equations involving square-roots, apply the complicated formula above this link; if they are linear, pre-processing them first: ax = b (mod c)

Step 1.5: if gcd(a,b,c)=d>1, then ax=b (mod c) has the same solution with (a/d)x = b/d (mod c/d)

Step 1.5.1: else, if gcd(a,c) = e>1, then there's no solution;

Step 1.5.2: else (which means gcd(a,c)=1) find out v = a^-1 mod c, and solve x = b*v (mod c)

Step 2: (copy the formula on the cheating sheet!) put everything together using CRT, CRT* (if there are congruence classes that are coprime, do this processing)

__Example 6: solve the following system of equation: 2x = 5 mod 6; x^2 = 9 mod 16__

2. Some hard problems, and the basic protocol of RSA (Rabin is a special case for RSA), DH

__Example 7: Which of the following problem is not known to be computable in polynomial time?__

__7.1 Find x: x^2 = 3 mod N, where N is composite without knowing the factors.__

__7.2 Find x: x^2 = 3 mod N, where we know all the prime factors of N.__

__7.3 Find x: 2^x = 9 mod N, where we know all the prime factors of N.__

3. Checking Isomorphism: (copy the definition)

Step 1: check if the size of the sets are equal (if not then definitely not isomorphic)

Step 2: if the size are equal, and the bijection is given, check the bijection pair by pair; if the bijection is not given, then try to figure out the bijection. (The hardest is to prove non-isomorphism, for which in the worst case you cannot enumerate all the bijection efficiently, but... it might be...)

__Example 8: A = ( Z/10Z, "+ mod 10" ), B = ( Z/11Z*, "x mod 11"), are they isomorphic?__

**Notes 12 - Dec. 03**

Explain previous assignments, esp. Assignment 5.

The problem about "checking unreliable server" ( original problem, example )

{ FYI: Verifiable computation has many applications (cloud computing, e-voting), for which researchers trying to find "practical" solutions. }

PrivateProducts( xs = [a1, a2, ..., an], p, q ) = a1*a2*...*an %p // q is for creating n=pq, used for verifying

n=p*q, pick random e (s.t. gcd(e, phi(n)) = 1) as the public key. d = inv(e) under phi(n)

Send to the server c = a1^e * a2^e * ... * an^e %n; Expected to get (a1*a2*...*an)^e%n

( This is an imaginary homomorphic encryption idea, but the real homomorphic encryption we know doesn't work in this way. )

In order to check consistence, we pick r randomly from Z/qZ, so that using the CRT isomorphism,

such that you are expecting the server to give you (product'*p*p^-1 + r'^n *q*q^-1)^e, then decrypt and check if r'^n%q = r^n%q.

To check (prove) or disprove

**Isomorphism**:

Recall the definition of Iso: (A, opA) is isomorphic to (B, opB) if there's a bijection f, such that:

forall a1, a2 in A (a1 and a2 could be the same),

**f(a1 opA a2) = f(a1) opB f(a2) = b1 opB b2**

- If the bijection is given, checking is efficient (let n be the size of A and B, has to do n^2 checks)

- If the bijection is not given, then the worst-case running time to prove or disprove is exponential

( naive algorithm: enumerate all the possible mapping. In general, don't have better algorithms. But in some special cases, one may be able to find the bijection mathematically)

**Notes 12i - Nov. 26**

Thanksgiving recess

**Notes 11 - Nov. 19**

Algebraic closure, Permutation, Isomorphism, Assignment 5

*Facts for the compositions of the permutations*: Permutation doesn't commute in general - see examples from this link. However, it seems that all the permutations in our lecture notes permute (doesn't imply that the permutations in our HWs permute)

**Notes 10 - Nov. 12**

A quiz (10 points, cheating sheet and calculator allowed, bring

__your share of secret__from OCT 29 )

Topic: CRT, modular arithmetic, quadratic equations; RSA encryption, Diffie-Hellman Key exchange

**Notes 09 - Nov. 05**

(Throughout this lecture P, Q, p, q, r, s are primes by default, N, n could be any integers, x and y are usually the unknown, a,b,c are usually (non-zero) constants)

A Warm-up Quiz for Modular Quadratic Operations (for HW4 and the Quiz next week):

In the following problems, do the solution always exists (Yes/No. If yes, think of how many?)

1. ax = 1 (mod p), for all 1<a<p

2. ax = 1 (mod N), for all 1<a<N

3. x^2 = 1 (mod p),

4. x^2 = a (mod p), for all 1<a<p

5. x^2 = a (mod N), for all 1<a<N

Whether the following problems are computable in polynomial time (Yes/No)

11. Input N; Output: all the prime factors of N

12. Input N; Output \phi(N)

13. Assuming you have a solver "phi_four(n)", that given any n=pqrs, output \phi(n), then there's a solver for "phi_two(N)", that suppose N = PQ, we have an algorithm running in polynomial time that output \phi(N).

14. Input g, p, g^a mod p, g^b mod p, Output g^{ab} mod p

{ Solutions: 1/ and 2/ x is the multiplicative inverse of a. When gcd(a,N)=1, x exists (and can be efficiently computed if phi(N) is known, by Euler's lemma. 3/ 1 and p-1 are the obvious solution. 4/ and 5/ not for all 1<a<N has a square-root mod N, an easy way to explain is: f(x)=x^2 mod N is not a permutation. 11/ and 12/ are proved to be equally hard (see notes 08). 13/ Top secret 14/ That's exact the Diffie-Hellman problem. }

**Notes 08 - Oct. 29**

Measuring the running time of computation.

Conjectures of the existence of hard problems. Basic notions of reductions of (hard) instances.

Conjecture 1: Factoring(N) is not computable in polynomial time.

Conjecture 2: Euler's quotient(N) is not computable in polynomial time.

Thm: Conjecture 1 is true if and only if conjecture 2 is true.

Proof: reduce Factoring(N) to E.Q.(N); reduce E.Q.(N)

Conjecture 3: Let C = a^b mod J, Discrete.Log(C, a, J)->b is not computable in polynomial time.

(we don't know how to reduce Conj 3 to 1; neither do we know how to reduce 1 to 3.)

{ Here "conjecture" means "we don't know", it doesn't mean "there's definitely no"}

**Notes 07 - Oct. 22**

Again, why this course?

- Key-exchange [Diffie-Hellman], Public-key Cryptography [Rivest-Shamir-Adleman]

- { How to play Mental Poker [Shamir-Rivest-Adleman] }

- Secret Sharing [Shamir] (

__Application: encouraging attendance of the discussion session__)

- { How to "seduce" millionaires to talk to each other? [Yao] }

- How to generate randomness? [Blum, Micali, Yao, ......]

- { How to prove something "without revealing anything else"? [Goldwasser-Micali-Rackoff] }

Explain the midterm.

**Notes 06 - Oct. 15**

Pre-Midterm-Quiz ( Prove or disprove

*Yilei's conjectures*):

1. {A dirty little secret for students who missed the session}

2. If a = b (mod m), c = d (mod n), then a+c = b+d (mod m+n)

3. If a = b (mod m), c = d (mod n), then ac = bd (mod mn)

4. For any n>2: in Z/nZ, n-1 always has it's multiplicative inverse.

5. \phi(10^100) = 10^100 - 10^99

6. 6173532828 is a Prime => 13^6173532827 = 1 (mod 6173532828)

7. If X = 3 (mod 100), 7X = 4 (mod 291), then X = 5703 (mod 29100)

8. {Another dirty little secret for students who missed the session}

{Solutions: 2/ False. To elaborate, let a = b+im, c = d+jn, i, and j are arbitrary integers. so that a+c = b+d+im+jn. To create the counterexample, let i and j be different integers. 3/ False, similar with 2. 4/ True. Since n-1 is always coprime with n. In fact the multiplicative inverse of n-1 mod n is n-1 itself. 5/ False. Since 10 is not a prime. Only the phi of the power of prime (p^k) can be p^{k-1}(p-1). 6/ True. A=>B is always True if A is False. 7/ False. The idea is that verifying is always easier than computing.}

**Notes 05 - Oct. 08**

Facts of facts about

**Multiplicative Inverse**: given a, n, find x s.t. ax = 1 (mod n), 0<a<n

- Existence of solution: (fact)

"a has a multiplicative inverse modular n" if and only if "gcd(a,n) = 1"

- How to compute?

(1) When N is a prime, use FLT (fact); (2) General case, Euler's Thm (fact)

Facts of facts about

**Chinese Remainder Theorem**(Why did Chinese invent that?)

- When solution exists? - Click this fact

- How to compute? - Click this fact

{ Extensions: CRT with error http://www.eng.tau.ac.il/~danar/Public-pdf/ieee-fin.pdf }

Facts of facts about

**Eular's Quotient**:

\phi(m) = |{x|x in Z/mZ and x has a multiplicative inverse in Z/mZ}| = |(Z/mZ)*|

For example: (red numbers have multiplicative inverse in Z/nZ)

Z/8Z = {0,1,2,3,4,5,6,7}, (Z/8Z)* = {1,3,5,7}, \phi(8) = 2^3-2^2 = 4

Z/15Z = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14},

(Z/15Z)* = {1,2,4,7,8,11,13,14}, \phi(15) = \phi(3) x \phi(5) = 2x4 = 8

Tips of

**programming in this course**:

Usually, solving problems with small test cases combined from {2,3,4,5,6,7,8,9,10,15,16,27,31} will guarantee your correctness, although may not solve the efficiency issue. (But usually again, the first place you stuck at is correctness, efficiency issues would be solved as a consequence.)

{ Exceptions known in mathematics and computer science, click this. Also cf. this }

**Notes 05i - Oct. 01**

CANCELLED

**Notes 04 - Sep. 24**

{

Tips for HW2: (It's marked as "out of the scope of the class" because: without these tips the problems are already well defined. Plus, the tips are not always correct)

- Personal opinion of 3.a: The only point that matters is the correctness of findCoprime(), not where the output lives.

- 3.b: The idea of using a with m such that gcd(a,m)=1 is, for all 1<x<y<m, ax!=ay (mod m), therefore, think of x and y as different indices in the sequence, then ax and ay will be "different" :P ( "random" = "different enough" for our class at this moment )

- Problem 4 is a case where you may learn that 2**99999%100000 is really slower than pow(2, 99999, 100000) in Python.

- If your solution in Problem 5 is correct but slow, that probably means there are something correct but slow in the previous problems...

- Weird tips for debug in Python: you can measure time elapsed.

}

Quiz ( All the variables are integers, all numbers are written in decimal. Choose True / False )

1. If p is a prime, 1<a<p, then gcd(a, p)=1?

2. If n>100 is a composite, a = 3 mod n, b = 8 mod n, then ab = 24 mod n?

3. If n|(ab), then n|a or n|b?

4. If p>100 is a prime, 1<a<b<p, let c = ab mod p, then c is neither equal to a nor b?

5. {173173173173173173173173 is a prime?}

6. Given n>100, randomly pick 1<a<n, if a^n = a mod n, then n is a prime?

7. Given n>100, randomly pick 1<a<n, if a^n = 2+a mod n, then n is a composite?

8. {173173173173163173173173 is a prime?}

9. You know how to distinguish coke and pepsi using Fermat's little theorem?

10. If 100<a<b<c<d are primes, then abcd+1 a prime?

11. HW2 is due tonight?

{ To students who don't come to class today: you miss the pie. Solutions: 1/ True. A prime number is coprime with anyone else. 2/ True, and doesn't matter if n is a composite or not. One can write a = 3+kn, b = 8+ln, so ab = 24 +(k+l+n)n, so ab = 24 mod n. 3/ False. Let N = 30, a = 3, b = 10. The case where it holds is when n is a prime. 4/ True. Try to prove by yourself. The msg I want to send is, if p is a prime, then for 1<a<b<p, ab is a different number from a or b. 5/ False. 6/ False, see Carmichael numbers in the last session notes. 7/ True. For any number n>100, if you pick arbitrary a but a^n != a mod n, then it's DEFINITELY a composite. 8/ False. 9/ If you don't know, send me a msg. 10/False. abcd+1 must be an even number. What's confusing: abcd+1 is coprime with a or b or c or d, but is not a prime itself.}

**Notes 03 - Sep. 17 (Known as Lobster Night)**

Measure of running time: on the length of the number but not the number itself

e.g. n=278931737821, digits d=12

addition: O(d); multiplication/division(with elementary method): O(d^2); try to figure out the others.

Prime_test(n):

- Trivial prime test, which is to find prime factors by enumerating t = 2, ... ,\sqrt(n) and check t|n, has exponential running time (in d). {Notice that deciding prime/composite could be easier than Factoring, since Factoring n solves prime test, but prime test doesn't necessary imply Factoring. In fact, we know how to do prime test in polynomial time (very efficient), but there are hard instance of composite numbers that we don't know how to factor in polynomial time}
- Probabilistic test: may have one side error
- Fermat's little theorem: " n is a prime => a^n = a (mod n), for all 0<a<n ", which means if the input n is prime, then we pick an arbitrary a => Pr_a[a^n = a (mod n)] = 100%; but if n is composite, the equivalence may still hold for some a => Pr_a[ a^n = a (mod n)]>=0% (here's the one-side error). e.g. for n=15, a = 4.
- Well, if for all n that are composite, if Pr_a[ a^n = a (mod n)] has some upper bound, say 1/2, can we solve the problem? Yes! By repeating k times, we get error probability <1/2^k.
- However, life is hard - there are composite numbers such that Pr_a[ a^n = a (mod n)] = 1, e.g. 561, 1105, 1729, 2465, ... see Carmichael numbers. Which means Fermat's test fails 100% on these numbers.

- {In practice, we use sophisticated probablistic algorithms such as Miller-Rabin test, combined with trivial test for small numbers...}
- {In 2002, Agrawal-Kayal-Saxena show a deterministic prime test algorithm running in polynomial time (d^12, where d is the digit-length of n). Winner of Goedel prize}

**Notes 02 - Sep. 10 (Teachers' Day in China)**

How to read/write loops in Python (cf. HW1)

**Notes 01 - Sep. 3**

Intro, {Backdoor of random number generator}; {How to find the source code of random lib in Python}; Wason selection task