When many realworld problems are addressed or solved mathematically and computationally, the details of those problems are abstracted away until they can be represented directly as idealized mathematical structures (e.g., numbers, sets, trees, graphs, matrices, and so on). In this course, we will study a collection of such idealized mathematical objects: integers, groups, residues, and several others. We will see how these structures and their properties can be used for implementing random number generators, error correcting codes, defining simple cryptographic protocols, approximating and interpolating numerical functions, and other applications.
In covering the material for this course, we will use the standard language and conventions for discussing these mathematical structures that have been developed by the community of mathematicians. You will need to become familiar with these conventions in order to find, identify, and use the structures and techniques that have already been developed for solving certain computational problems. At the same time, we will also learn how modern programming languages and programming paradigms can be used to implement these structures and algorithms both accessibly and efficiently.
The development and application of mathematics involves abstraction. A problem can be viewed at multiple levels of abstraction, and in developing mathematics humans have adopted a variety of techniques that allow them to successfully employ abstraction to study natural phenomena and solve problems.
symbolic  abstract meaning  concrete meaning in application domain 
2 + 3  5  five objects 
{(1, 2), (1, 3)}  acyclic graph  file system 
{(1, 2), (2, 3), (3, 1)}  graph with cycle  network 
In this course, we will begin to reviewing the terminology and concepts of logic, integer arithmetic, and set theory, which we will use throughout the course. We will then show that the algebraic properties of the integers also apply to congruence classes of integers (i.e., the properties of modular arithmetic operations), and we will derive and utilize theorems that have useful computer science applications (such as for generating random numbers and creating cryptographic protocols). We will then go further and show that some of the algebraic properties that hold in integer and modular arithmetic can also apply to any data structure, and we will study how to recognize and take advantage of these properties.
formula  true or false  example of one possible Python representation 
true  always true  True 
false  always false  False

f_{1} and f_{2}  only true if both f_{1} and f_{2} are true  True and False 
f_{1} or f_{2}  true if f_{1} or f_{2} (or both) are true  True or (False and True) 
f_{1} implies f_{2}  if f_{1} is true, then f_{2} must be true or equivalently f_{1} is false, or f_{2} is true 

f_{1} iff f_{2}  f_{1} and f_{2} are either both true or both false  True == False 
¬ f  true if f is false  not (True or (False and True)) 
meaning of lefthand side (premise) 
meaning of righthand side (conclusion) 
meaning of entire formula 
comments 
true  true  true  if the premise is true and the conclusion is true, the claim of implication is true; thus, the whole formula is true 
true  false  false  if the premise is true but the conclusion is false, the conclusion is not implied by the premise, so the claim of implication is false; thus, the formula is false 
false  true  true  if the conclusion is true on its own, it doesn't matter that the premise is false, because anything implies an independently true conclusion; thus, the claim of implication is true, and so is the entire formula 
false  false  true  if we assume that a false premise is true, then "false" itself is "true"; in other words, false implies itself, so the formula is true 
term  what it represents  example of one possible Python representation 
0  0  0 
1  1  1 
z_{1} + z_{2}  the integer sum of z_{1} and z_{2}  3 + 4

z_{1}  z_{2}  the integer difference of z_{1} and z_{2}  (1 + 2)  4

z_{1} ⋅ z_{2}  the integer product of z_{1} and z_{2}  3 * 5

z_{1} mod z_{2}  the remainder of the integer quotient z_{1} / z_{2} z_{1}  ⌊ z_{1}/z_{2} ⌋ ⋅ z_{2} 
17 % 5

z_{1}^{z2}  product of z_{2} instances of z_{1}  2**3 pow(2,3)

formula  what it represents  example of one possible Python representation 
z_{1} = z_{2}  true if z_{1} and z_{2} have the same meaning; false otherwise 
1 == 2 
z_{1} < z_{2}  true if z_{1} is less than z_{2}; false otherwise 
4 < 3 
z_{1} > z_{2}  true if z_{1} is greater than z_{2}; false otherwise 
4 > 3 
z_{1} ≤ z_{2}  true if z_{1} is less than or equal to z_{2}; false otherwise 
4 <= 3 
z_{1} ≥ z_{2}  true if z_{1} is greater than or equal to z_{2}; false otherwise 
4 >= 3 
z_{1} ≠ z_{2}  true if z_{1} is not equal to z_{2}; false otherwise 
4 != 3 
predicate definition  example of one possible Python representation 
P(x) iff x > 0 and x < 2  def P(x): return x > 0 and x < 2 
Q(x) iff x > 3  Q = lambda x: x > 3 
formula  what it represents  example of one possible Python representation 
P(1)  true  P(1) 
P(1) or P(2)  true  P(1) or P(2)

Q(1) and P(1)  false  Q(1) and Q(1)

formula  what it represents 
x  y  y / x ∈ ℤ x divides y y is divisible by x y is an integer multiple of x y mod x = 0 x is a factor of y 
y is prime  y > 1 and x  y implies x = 1 or x = y y > 1 and y is divisibly only by 1 and itself 
term  what it represents  example of one possible Python representation 
∅  a set with no elements in it  set() 
{1,2,3}  {1,2,3}  {1,2,3} 
{2,..,5}  {2,3,4,5}  set(range(2,6)) 
{ x  x ∈ {1,2,3,4,5,6}, x > 3 }  {4,5,6}  {x for x in {1,2,3,4,5,6} if x > 3}

{1,2,3,4}  4  len({1,2,3,4})

term  what it represents  example of one possible Python representation 
S_{1} ∪ S_{2}  {z  z ∈ ℤ, z ∈ S_{1} or z ∈ S_{2}}  {1,2,3}.union({4,5}) 
S_{1} ∩ S_{2}  {z  z ∈ ℤ, z ∈ S_{1} and z ∈ S_{2}}  {1,2,3}.intersection({2,3,5}) 
S  the number of elements in S  len({1,2,3}) 
term  what it represents 
ℕ  {0, 1, 2, ...} 
ℤ  {..., 2, 1, 0, 1, 2, ...} 
formula  what it represents  example of one possible Python representation 
1 ∈ {1,2,3}  true  1 in {1,2,3} 
4 ∈ {1,2,3}  false  4 in {1,2,3} 
∀ x ∈ {1,2,3}, x > 0 and x < 4  true  forall({1,2,3}, lambda x: x > 0 and x < 4) 
∃ x ∈ {1,2,3}, x < 1 and x > 3  false  exists({1,2,3}, lambda x: x < 1 or x > 3) 
∀ x ∈ ∅, f  true  
∃ x ∈ ∅, f  false 
 iff 
 
 iff 

formula  what it represents  example of one possible Python representation 
3 ∈ {1,2,3}  true  3 in {1,2,3} 
{1,2} ⊂ {1,2,3}  true  subset({1,2}, {1,2,3}) 
{4,5} ⊂ {1,2,3}  false  subset({4,5}, {1,2,3}) 
formula  what it represents 
z ∈ S  true if z is an element of S; false otherwise 
S_{1} ⊂ S_{2}  ∀ z ∈ S_{1}, z ∈ S_{2} 
S_{1} = S_{2}  S_{1} ⊂ S_{2} and S_{2} ⊂ S_{1} 
term  what it represents  example of one possible Python representation 
{1,2} × {5,6,7}  {(1,5),(1,6),(1,7),(2,5),(2,6),(2,7)}  { (x,y) for x in {1,2} for y in {4,5,6,7} } 
predicate  definition  graphical example 
X × Y is the set product of X and Y  X × Y = { (x,y)  x ∈ X, y ∈ Y }  
R is a relation between X and Y  R ⊂ X × Y  
R is a function from X to Y R is a (manytoone) map from X to Y 
R is a relation between X and Y and ∀ x ∈ X, there is at most one y ∈ Y s.t. (x,y) ∈ R 

R is an injection from X to Y 
R is a relation between X and Y and ∀ y ∈ Y, there is at most one x ∈ X s.t. (x,y) ∈ R 

R is a surjection from X to Y 
R is a relation between X and Y and ∀ y ∈ Y, there is at least one x ∈ X s.t. (x,y) ∈ R 

R is a bijection between X and Y  R is an injection from X and Y and R is a surjection from X and Y 

R is a permutation on X  R ⊂ X × X and R is a bijection between X and X 

R is a reflexive relation on X  R ⊂ X × X and ∀ x ∈ X, (x,x) ∈ R 

R is a symmetric relation on X  R ⊂ X × X and ∀ x ∈ X, ∀ y ∈ X, (x,y) ∈ R implies (y,x) ∈ R 

R is a transitive relation on X  R ⊂ X × X and ∀ x ∈ X, ∀ y ∈ X, ∀ z ∈ X, (x,y) ∈ R and (y,z) ∈ R implies (x,z) ∈ R 

R is an equivalence relation on X R is a congruence relation on X 
R ⊂ X × X and R is a reflexive relation on X and R is a symmetric relation on X and R is a transitive relation on X 
predicate  required conditions 
X is the domain of R between X and Y  R is a function from X to Y 
Y is the codomain of R between X and Y  R is a function from X to Y 
B is the image of R between X and Y  R is a function from X to Y and B = {y  x ∈ X, (x',y) ∈ R, x = x'} 
B is the image of x under R between X and Y  R is a function from X to Y and B = {y  (x,y) ∈ R} 
A is the preimage of y under R between X and Y  R is a function from X to Y and A = {x  (x,y) ∈ R} 
 = 

 = 

a1.py
. Please follow the gsubmit directions.
primes(n)
that takes a single integer argument n
and returns the total number of primes less than or equal to n
.
composites(ns)
that takes a finite set of integers ns
as its one argument and returns True
if none of the integers in the set are prime, and False
otherwise.
(1,2)
). You should include the following definition in your code:
isReflexive()
that takes as its input two arguments: a set X
and a relation R
. The function should return True
if the relation R
is a reflexive relation on X
, and it should return False
otherwise.
R1
above so that R1
is an equivalence relation over X1
, and so that the following will evaluate to True
:
R2
above so that R2
is an equivalence relation over X2
, and so that the following will evaluate to True
:
R3
above so that R3
is an equivalence relation over X3
, and so that the following will evaluate to True
:
factors(n)
that takes a single positive integer argument n
and returns a finite set of integers containing all the factors k
of that number (i.e., all numbers k
such that k
 n
).
shared(S)
that takes any finite set of positive integers S
and returns a relation over S
in which any two numbers in S
that share at least one factor greater than 1 are related.
shared()
(assuming its input is a finite set of positive integers).
If all three properties hold, indicate this in a code comment. Define three veriables in your code:
None
to the corresponding variable. If a property does not apply to all outputs of shared()
, assign an input set to the corresponding variable that returns an output relation that does not satisfy that property.classes(S, n)
that takes two arguments: any finite set of integers S
and a single integer argument n
. The function should then break up the set of integers S
into a set of equivalence classes (i.e., a set of sets) corresponding to the congruence classes modulo n
. See the examples below. Hint: build a relation over the set S
using a set comprehension and the modulus operator, and then use quotient()
.
 = 

 = 

 = 

term  what it represents 
z z mod m z + mℤ 
{z + (a ⋅ m)  a ∈ ℤ} 
c_{1} + c_{2}  {(x + y)  x ∈ c_{1}, y ∈ c_{2}} 
c_{1}  c_{2}  {(x  y)  x ∈ c_{1}, y ∈ c_{2}} 
c_{1} ⋅ c_{2}  {(x ⋅ y)  x ∈ c_{1}, y ∈ c_{2}} 
c^{z}  c ⋅ ... ⋅ c 
c!  c ⋅ (c1) ⋅ (c2) ⋅ ... ⋅ 1 
formula  what it represents 
c_{1} ≡ c_{2}  true only if c_{1} = c_{2} where "=" is set equality applied to the congruence classes c_{1} and c_{2}; false otherwise 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 


 ≡ 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
≡ 
 
≡ 

property  definition 
ℤ/mℤ is closed under +  ∀ x,y ∈ ℤ/mℤ, x + y ∈ ℤ/mℤ 
+ is commutative on ℤ/mℤ  ∀ x,y ∈ ℤ/mℤ, x + y ≡ y + x 
+ is associative on ℤ/mℤ  ∀ x,y,z ∈ ℤ/mℤ, (x + y) + z ≡ x + (y + z) 
+ has a (left and right) identity 0 in ℤ/mℤ  ∀ x ∈ ℤ/mℤ, 0 + x ≡ x and x + 0 ≡ x 
ℤ/mℤ has inverses with respect to +  ∀ x ∈ ℤ/mℤ, (m  x) + x ≡ 0 
ℤ/mℤ is closed under ⋅  ∀ x,y ∈ ℤ/mℤ, x ⋅ y ∈ ℤ/mℤ 
⋅ is commutative on ℤ/mℤ  ∀ x,y ∈ ℤ/mℤ, x ⋅ y ≡ y ⋅ x 
+ is associative on ℤ/mℤ  ∀ x,y,z ∈ ℤ/mℤ, (x ⋅ y) ⋅ z ≡ x ⋅ (y ⋅ z) 
+ has a (left and right) identity 1 in ℤ/mℤ  ∀ x ∈ ℤ/mℤ, 1 ⋅ x ≡ x and x ⋅ 1 ≡ x 
⋅ distributes across + in ℤ/mℤ  ∀ x,y,z ∈ ℤ/mℤ, x ⋅ (y + z) ≡ (x ⋅ y) + (x ⋅ z) 
 ≡ 
 
 ≡ 

 = 
 
 = 
 
 = 
 
 ≡ 

 = 
 
 = 
 
 = 
 
 ≡ 

  
 
 = 
 
 ≡ 
 
 ≡ 

 = 
 
 = 
 
 = 
 
 ∈ 
 
  

  
 
 ∈ 
 
 = 
 
 = 
 
 = 
 
 = 


 ≡ 
 
  
 
  
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ∤ 
 
 ≢ 
 
 ∤ 
 
 ≢ 

 ≡ 
 
 ≡ 
 
 = 
 
 = 
 
  

  
 
 = 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 

 = 
 
= 

 ≠ 
 
 = 
 
 = 
 
 = 
 
  

 = 

 = 
 
 = 
 
 = 

 = 
 
 = 
 
 = 

 = 

 = 

 = 

 = 
 
 = 

 = 
 
 = 
 
 = 
 
= 
 
= 
 
= 

 ≢ 
 
 ≢ 

 = 
 
 = 
 
 = 
 
 = 
 
 = 

 = 
 
 = 
 


 = 
 
= 
 
= 
 
≈ 

algorithm input  algorithm output  meaning  description 
actually a composite number (this is not known at time of input) 
composite  the input is composite  true negative 
actually a prime number (this is not known at time of input) 
prime  the input is prime  true positive 
algorithm input  algorithm output  meaning  description 
actually a composite number (this is not known at time of input) 
composite  the input is definitely composite 
true negative 
actually a composite number (this is not known at time of input) 
probably prime  the input is either composite or prime 
false positive 
actually a prime number (this is not known at time of input) 
probably prime  the input is either composite or prime 
true positive 
actually a prime number (this is not known at time of input) 
composite  impossible  false negative (we will not consider algorithms that return such outputs) 
input number 
perfect algorithm 
perfect probable prime algorithm 
less accurate probable prime algorithm 
very inaccurate probable prime algorithm 
2  prime  probably prime 
probably prime 
probably prime 
3  prime  probably prime 
probably prime 
probably prime 
4  composite  composite  probably prime 
probably prime 
5  prime  probably prime 
probably prime 
probably prime 
6  composite  composite  composite  probably prime 
7  prime  probably prime 
probably prime 
probably prime 
8  composite  composite  probably prime 
probably prime 
9  composite  composite  composite  probably prime 
10  composite  composite  probably prime 
probably prime 
 ≡ 

 = 
 
= 

 = 
 
 = 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
≡ 

for the chosen a we have... 
what it means  probability of this occurring if m is a nonCarmichael composite 
a  m  a is a nontrivial factor of m, so m is composite 
(# integers in {2,...,m1} that are factors with m) / (m2) 
gcd(a,m) ≠ 1  m and a have a nontrivial factor, so m is composite 
(# integers in {2,...,m1} that share factors with m) / (m2) 
a^{m1} mod m ≠ 1  a is a Fermat witness that m is composite 
at least 1/2 
m = 15 and a = ...  2  3  4  5  6  7  8  9  10  11  12  13  14 
a  m  PP  C  PP  C  PP  PP  PP  PP  PP  PP  PP  PP  PP 
gcd(a,m) ≠ 1  PP  C  PP  C  C  PP  PP  C  C  PP  C  PP  PP 
a^{m1} mod m = ...  4  9  1  10  6  4  4  6  10  1  9  4  1 
Euclid's lemma generalization 
⇐  multiples of coprime a in ℤ/mℤ are a permutation 

⇑  
Fermat's little theorem 
random number generator 
⇒  gcd(m,m+1) = 1  
⇑  ⇑  
greatest common divisor algorithm 
⇐  Fermat primality test 
⇐  probable prime detector 

⇑  
probable prime generator 
a2.py
(submitted to the location hw2/a2.py
). Please follow the gsubmit directions.
pow()
function, which can compute modular exponents efficiently (as in, a^{k} mod n can be written in Python as pow(a,k,n)
).
Your file may not import any other modules or employ any external library functions associated with
integers and sets unless explicitly permitted to do so in a particular problem. Solutions to each of the programming problem parts below should be fairly concise. You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on the lecture notes and on each other; carefully consider whether you can use functions from the lecture notes, or functions you define in one part within subsequent parts.
'''
...'''
, in a2.py
. You may use the =
ascii character to represent the ≡ relational operator on congruence classes.digits()
that takes a single positive integer argument n
where n
>= 0 and returns the number of digits in the decimal (base 10) representation of n
.
changeRandomRange(r, n, min, max)
that takes four positive integer arguments: r
is a number in the range 1 to n
(inclusive) that may have been generated by a random number generator; n
is a positive integer; and min
and max
are two integer arguments (where min
< max
and max
 min
< n
). Assuming r
was generated randomly, the changeRandomRange()
function should use r
to return a random number in the range between min
and max
(inclusive).
twoUnequalCoprimes()
that takes a single positive integer argument d
where d
>= 1 and returns a pair containing two unequal numbers which are both coprime with each other, and which are both coprime with the number 10^{d} + 1. Hint: use facts about coprime numbers and the fact that 10 = 2 ⋅ 5. Your implementation does not need to return exactly the same answers as you see in the example outputs. However, the output generated by your implementation must have the required properties.
randByIndex()
that takes two positive integer arguments: d
represents the number of digits of the result, and i
represents an index. You may assume d
≥ 1 and that 1 ≤ i
≤ 10^{d}. The function must return the i
th "random" number in a permutation of the numbers {1,...,10^{d}}. Your implementation does not need to return exactly the same answers as you see in the example outputs. However, the output generated by your implementation must produce a permutation when used in a comprehension, as in the example below.
randByIndex()
must represent a permutation as in the above examples. You should approach this problem by first determining an appropriate modulus m
in terms of d
, generating two distinct coprimes in ℤ/m
ℤ, and then using these two seeds along with facts about permutations to generate a "random" integer corresponding to one of the congruence classes in ℤ/m
ℤ.probablePrime()
that takes a single integer argument m
where m
>= 1. The function should return True
if m
is probably prime, and False
otherwise. Your code should employ the Fermat primality test by generating some number of random witnesses in the appropriate range and using them to test the primality of m
. You will need to determine what is a reasonable number of potential witnesses to test. Note that implementations that perform an exponentially large exhaustive search, even if the algorithm is mathematically correct, will not earn full credit.
makePrime()
that takes a single integer argument d
where d
>= 1 and returns a probably prime number that has d
digits. Your implementation should be sufficiently efficient to produce an output for d
= 100
in a reasonably short amount of time. Note that implementations that perform an exponentially large exhaustive search, even if the algorithm is mathematically correct, will not earn full credit.
 = 
 
⋮  
 = 

 ≡ 
 
⋮  
 ≡ 

 ≡ 
 
 ≡ 

 = 
 
 = 

 ≡ 

efficient modular arithmetic 

⇓  
Chinese remainder theorem 
⇐  CRT solver  ⇐  range ambiguity resolution 
⇑  
Shamir secret sharing protocol 
 = 

 = 

 := 
 
 := 
 
 := 
 
 := 
 
 := 
 
⋮ 
 := 
 
 := 
 
 := 
 
 := 
 
 := 
 
⋮ 
 > 
 
≥ 
 
 = 
 
⋮  
 = 

 ≡ 
 
⋮  
 ≡ 

 = 

greatest common divisor algorithm 
Fermat's little theorem 
Euler's theorem 

⇑  ⇑  ⇑  
Bézout's identity 
⇐  extended Euclidean algorithm 
⇐  algorithm for finding multiplicative inverses 
⇒  Euler's totient function φ 
⇑  
Chinese remainder theorem 
⇐  CRT solver for two equations 

⇑  
induction  ⇐  CRT solver for n equations 
 ≡ 
 
≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 
 ≡ 


 ≡ 
 
 ≡ 
 
 ≡ 
 
 = 
 
 ≡ 

 ≡ 

 
 ≡ 


 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 

 ≡ 

 = 

 = 

 = 

 = 
 
 = 
 
 = 

 = 
 
 = 
 
 = 

 = 

 = 
 
 = 

 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 

 < 

 < 
 < 
 
 < 
 < 

 = 

 = 
 
 = 
 
 ≡ 
 
 = 

 = 
 
= 
 
= 

 = 

 = 
 
 ≡ 
 
 ≡ 

 = 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 = 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
⋮  
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 
 
 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 


 > 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 = 
 
 = 

 ≥ 
 
 ≥ 
 
 ≥ 
 
 ≥ 


 ≡ 
 

 ≡ 
 

 ≡ 

 
 
 
 

 = 
 
 = 
 
= 
 
= 

 = 
 
= 
 
= 

 = 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 

 = 

 = 
 
= 

 = 

 = 
 
 = 
 
 = 
 
= 
 
= 
 
= 
 


 = 

 = 

 ≡ 
 
= 
 
 = 
 
= 
 
= 

 = 

 = 

 ≡ 
 
= 
 
= 
 
= 

 ≡ 
 
= 
 
= 
 
= 

 ≡ 
 
= 
 
= 
 
= 
 
= 
 
= 

 = 
 
 = 

 = 

 = 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
 ≡ 
 
≡ 
 
≡ 

a3.py
(submitted to the location hw3/a3.py
). Please follow the gsubmit directions.
pow()
function can compute modular exponents efficiently (as in, a^{k} mod n can be written in Python as pow(a,k,n)
);sum()
function returns the sum of a list of integers (e.g., sum(1,2,3,4)
returns 10
).'''
...'''
, in a3.py
. You may use the =
ascii character to represent the ≡ relational operator on congruence classes.

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

invPrime(a, p)
that takes two integers a
and p
> 1 where p
is prime. The function should return the multiplicative inverse of a
∈ ℤ/p
ℤ (if a
≡ 0, it should return None
). Your solution must use Fermat's little theorem.
a
and b
, egcd(a, b)
returns a solution (s, t)
to the following instance of Bézout's identity:
 = 

egcd()
, implement a function inv(a, m)
that takes two integers a
and m
> 1. If a
and m
are coprime, it should return the multiplicative inverse of a
∈ ℤ/m
ℤ. If a
and m
are not coprime, it should return None
.
solveOne(c, a, m)
that takes three integers c
, a
, and m
≥ 1. If c
and m
are coprime, the function should return the solution x ∈ {0, ..., m
1} to the following equation:
 ≡ 

c
and m
are not coprime, the function should return None
.
solveTwo(e1, e2)
that takes two tuples e1
and e2
as inputs, each of the form (c, a, m)
(i.e., containing three integer elements). Each tuple (c, a, m)
corresponds to an equation of the form:
 ≡ 

(c, a, m)
and (d, b, n)
, correspond to a system of equations of the form:
 ≡ 
 
 ≡ 

solveTwo()
should return the unique solution x to the above system of equations. If either equation cannot be solved using solveOne()
, or n
and m
are not coprime, the function should return None
.
solveAll(es)
that takes a list of one or more equations, each of the form (c, a, m)
. The list corresponds to the system of equations (assume all the m_{i} are mutually coprime):
 ≡ 
 
⋮  
 ≡ 

solveAll()
should return the unique solution x to the above system of equations. If any individual equation cannot be solved using solveOne()
, or if the moduli are not all mutually coprime, the function should return None
.
[(2,4),(3,5),(6,3)]
represents the sum of powers 2^{4} + 3^{5} + (−6)^{3}.
sumOfPowers(nes, ps)
that takes a list of one or more tuples nes
(i.e., nes
is of the form [(a1,n1),...,(ak,nk)]
) as its first argument, and a list of one or more primes ps
(i.e., of the form [p1,...,pm]
) as its second argument. The function should return the correct result of the sum of powers as long as the following is true (e.g., on a computer with unlimited memory and time):
 ≤ 
 < 

sumOfPowers()
so that it can handle inputs even if the exponents themselves are extremely large. You must use Euler's theorem to accomplish this; you may not assume that any particular patterns will exist in the bases or exponents.


 = 
 
 = 
 
 = 

 = 
 
= 

 = 
 
= 
 
= 
 
= 
 
= 
 
 = 

 < 
 ≤ 

 = 
 
= 
 
= 
 
< 
 
< 

 ≡ 
 
 ≡ 

 = 
 
= 

solver for problem B 
⇒ ⇒ ⇒ 
conversion from output(s) from B to output from A 
⇑⇑⇑  ⇓  
conversion from input for A to input(s) for B 
⇐  solver for problem A 
problem B  ⇐  problem A 
finding multiplicative inverses 
⇐  solving twoequation systems using CRT 
problem B premise: can be solved in polynomial time B ∈ P 
⇐  problem A conclusion: can be solved in polynomial time A ∈ P 
problem B conclusion: cannot be solved in polynomial time B ∉ P 
⇐  problem A premise: cannot be solved in polynomial time A ∉ P 
 = 
 
 = 
 
 = 
 
 = 
 
 = 

 = 
 
 = 

 = 
 
 = 

 = 
 
 = 
 
= 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 ∈ 
 
 = 

computing φ(n) conclusion: cannot be solved in polynomial time computing φ(n) ∉ P 
⇐  factoring n conjecture: cannot be solved in polynomial time factoring ∉ P 
 = 

 ≡ 

 = 

 
 ∈ 

 
 = 


 = 
 = 

 ∈ 
 
 ∈ 
 
 = 


 = 
 = 

 
 
 
 
 
 

 
 
 
 

 = 

 = 
 
= 
 
= 
 
 = 
 
 = 
 
= 
 
 
 


 = 
 
 = 
 
= 
 
= 
 
= 
 
 = 
 
= 
 
 = 
 
= 
 
= 
 
= 

 ≡ 
 
 ≡ 
 
≡ 
 
 ≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
≡ 
 
 ≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 



 ≡ 

 ≡ 

 ≡ 

 = 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

  

  

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 = 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 

 = 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 = 

 = 
 
 = 
 
= 
 
  

congruent squares (square roots of congruence classes) 

⇑  ⇑  
computing φ(n) for n = p ⋅ q 
⇐ ⇒ 
factoring n = p ⋅ q 

⇑  ⇑  
RSA problem (eth roots of congruence classes) 

discrete logarithm (logarithms of congruence classes) 
forging private identifier for n conclusion: cannot be solved in polynomial time forging ∉ P 
⇐  factoring n conjecture: cannot be solved in polynomial time factoring ∉ P 
alternative efficient algorithm 
⇐  forging private identifier for n 
⇒  factoring n 
 ≡ 
 
= 
 
 = 
 
= 
 
= 
 
= 
 
= 
 
= 

 ≡ 
 
 ≡ 

breaking Rabin encryption 
⇐  congruent squares (square roots of congruence classes) 

⇑  ⇑  
finding RSA secret key 
⇐  computing φ(n) for n = p ⋅ q 
⇐ ⇒ 
factoring n = p ⋅ q 

⇑  ⇑  
decrypting individual RSA messages 
⇐  RSA problem (eth roots of congruence classes) 

breaking DiffieHellman 
⇐  discrete logarithm (logarithms of congruence classes) 
a4.py
(submitted to the location hw4/a4.py
). Please follow the gsubmit directions.
'''
...'''
, in a4.py
. You may use the =
ascii character to represent the ≡ relational operator on congruence classes.
 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

factorsFromPhi(n, phi_n)
that takes two integers n
and phi_n
. You may assume (i.e., you do not need to verify in your code) that n
is a product of two distinct positive prime numbers and that phi_n
= φ(n
). The function should return both prime factors of n
as a tuple.
factorsFromRoots(n, x, y)
that takes three integers n
, x
, and y
. You may assume that n
is a product of two distinct positive prime numbers, and that the following is true:
 ≡ 
 
 ≢ 

n
as a tuple.
factor(n)
that takes an integer n
and returns both prime factors of n
.
root(b, a, n)
that takes three integers a
, b
, and n
and returns the
a
th root of b
in ℤ/n
ℤ. You may assume that n
is a product of two distinct prime numbers. In other words, it should be true that:
 ≡ 

a
and pow(b, a, n)
parameters in the equation were switched from those in the example). Since this was discovered shortly before the assignment deadline, we will accept either order for the parameters in your implementation. We leave the sample input as it was originally, and adjust the equation above to match it.
dlog(a, b, p)
that takes three integers a
, b
, and p
and returns the discrete logarithm of a
with respect to base b
in ℤ/p
ℤ. You may assume that p
is prime. In other words, it should be true that:
 ≡ 

roots(a, n)
that takes two integers a
and n
and returns all four square roots of a
in ℤ/n
ℤ as a tuple. You may assume that n
is the product of two distinct positive prime numbers. Hint: in addition to the decryption functions above, you may need to employ the Chinese remainder theorem.
sqrtsPrime(a, p)
that takes two arguments: an integer a
and a prime number p
. You may assume that a
and p
are coprime. If p
is not in 3 + 4ℤ or a
has no square roots in ℤ/p
ℤ, the function should return None
. Otherwise, it should return the two congruence classes in ℤ/p
ℤ that solve the following equation:
 ≡ 

sqrtsPrimePower(a, p, k)
that takes three arguments: an integer a
, a prime number p
, and a positive integer k
. You may assume that a
and p
are coprime. If p
is not in 3 + 4ℤ or a
has no square roots in ℤ/p
^{k}ℤ, the function should return None
. Otherwise, it should return the congruence classes in ℤ/p
^{k}ℤ that solve the following equation:
 ≡ 

sqrts(a, pks)
that takes two arguments: an integer a
and a list of tuples pks
in which each tuple is a distinct positive prime number paired with a positive integer power. You may assume that a
and n
are coprime. You may assume that all the primes in pks
are in 3 + ℤ/4ℤ (if any are not, the function should return None
). Let n
be the product of all the prime powers in the list pks
. Then the function should return a set of all the distinct square roots of a
in ℤ/n
ℤ that are solutions to the following equation:
 ≡ 

n
ℤ to look for square roots), and it must work for any positive number of entries in pks
.




 ≡ 
 
≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 

 = 
 
 = 


 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 



 ≡ 
 
 ≡ 

 = 
 = 



 = 


 = 
 
= 
 
 = 
 
= 
 
= 
 
 = 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 



 = 



 = 

 = 
 
 = 
 
 = 
 
S_{2}  ℤ/2ℤ 
[0,1]  0 
[1,0]  1 
S_{2}  ℤ/2ℤ 
[0,1] o [0,1] = [0,1]  0 + 0 = 0 
[0,1] o [1,0] = [1,0]  0 + 1 = 1 
[1,0] o [0,1] = [1,0]  1 + 0 = 1 
[1,0] o [1,0] = [0,1]  1 + 1 = 0 
+ o 
0 [0,1] 
1 [1,0] 
0 [0,1] 
0 [0,1] 
1 [1,0] 
1 [1,0] 
1 [1,0] 
0 [0,1] 
C_{3}  ℤ/3ℤ 
[0,1,2] o [0,1,2] = [0,1,2]  0 + 0 = 0 
[0,1,2] o [1,2,0] = [1,2,0]  0 + 1 = 1 
[0,1,2] o [2,0,1] = [2,0,1]  0 + 2 = 2 
[1,2,0] o [0,1,2] = [1,2,0]  1 + 0 = 1 
[1,2,0] o [1,2,0] = [2,0,1]  1 + 1 = 2 
[1,2,0] o [2,0,1] = [0,1,2]  1 + 2 = 0 
[2,0,1] o [0,1,2] = [2,0,1]  2 + 0 = 2 
[2,0,1] o [1,2,0] = [0,1,2]  2 + 1 = 0 
[2,0,1] o [2,0,1] = [1,2,0]  2 + 2 = 1 
 = 
 
 = 

(ℤ/2ℤ, +)  ((ℤ/3ℤ)*, ⋅) 
0 + 0 = 0  1 ⋅ 1 = 1 
0 + 1 = 1  1 ⋅ 2 = 2 
1 + 0 = 1  2 ⋅ 1 = 2 
1 + 1 = 0  2 ⋅ 2 = 1 
(ℤ/2ℤ, +)  ((ℤ/6ℤ)*, ⋅) 
0 + 0 = 0  1 ⋅ 1 = 1 
0 + 1 = 1  1 ⋅ 5 = 5 
1 + 0 = 1  5 ⋅ 1 = 5 
1 + 1 = 0  5 ⋅ 5 = 1 
 ≡ 

 ≡ 

ℤ/3ℤ  ℤ/3ℤ 
0  0 
1  2 
2  1 
ℤ/3ℤ  ℤ/3ℤ 
0 + 0 = 0  0 + 0 = 0 
0 + 1 = 1  0 + 2 = 2 
0 + 2 = 2  0 + 1 = 1 
1 + 0 = 1  2 + 0 = 2 
1 + 1 = 2  2 + 2 = 1 
1 + 2 = 0  2 + 1 = 0 
2 + 0 = 2  1 + 0 = 1 
2 + 1 = 0  1 + 2 = 0 
2 + 2 = 1  1 + 1 = 2 
 ≡ 

 = 

 = 

 ≡ 
 ≡ 

 = 

 = 

 ≡ 

 ≡ 

a5.py
(submitted to the location hw5/a5.py
). Please follow the gsubmit directions.
'''
...'''
, in a5.py
.




l
modulo some 2^{n}:
privateSum(l, n)
that can compute the sum of a list of numbers modulo 2^{n} without revealing the actual sum to the public (i.e., the output printed by publicSum
should reveal no obvious information about the actual sum). Your implementation may not use any Python addition function other than publicSum
. Your function is allowed to use the multiplication operator *
and the modulus operator %
.
l
modulo some 2^{n}:
privateProduct(l, n)
that can compute the product of a list of numbers modulo 2^{n} without revealing the actual product to the public (i.e., the output printed by publicProduct
should reveal no information about the actual product to anyone, unless they can solve an intractable problem in modular arithmetic). Your implementation may not use any Python addition functions, and it may not use any multiplication functions other than publicProduct
. Your function is allowed to use the exponentiation operator **
, the modulus operator %
, and the function pow()
. You may also want to use some algorithms from previous assignments, such as inv()
and egcd()
from Assignment #3.
permute(p, l)
that takes two arguments: a permutation p
(represented as a Python list of integers) and a list l
of the same length as the permutation. It should return the list after it has been permuted according to the permutation.
C(k, m)
that takes two integers k
and m
where k
< m
and returns the cyclic permutation in C_{m} that shifts all elements up by k.
M(a, m)
that takes two coprime integers a
and m
where 0
< a
< m
and returns the multiplicationinduced permutation in M_{m} that corresponds to multiplication by a modulo m:
sort(l)
that takes a list of integers of some length n and returns:
None
otherwise.ps
to an input list l
. For this problem, assume that ps
only contains cyclic permutations from the set of permutations C_{2n} for some n ∈ ℕ (that is, the set of cyclic permutations on sets with 2^{n} elements).
privatePermute(l, ps)
that applies the sequence of permutations to l
without revealing either the original input list l
or the final result. Your implementation must use publicPermute()
to perform the list of permutations. When running, your implementation of privatePermute()
may make at most two additional calls to permute()
(these two calls must not be inside a loop body, they should only be executed once per call to privatePermute()
, and privatePermute()
must not be recursive).
 = 

 = 

 = 

 = 

 = 
 
 = 
 
 ⊂ 
 
 ⊂ 
 
 = 
 
 ≅ 

 ≅ 

 ≅ 
 ≅ 

 = 
 = 
 = 

 = 
 
 = 

 ≡ 

 = 
 
 = 
 
 = 
 
 ≡ 

 = 

 = 

 ≡ 

 ≡ 
 
 ≡ 

 = 

 = 

 = 

 = 

 = 
 
 = 

 = 

 = 

ℤ/2ℤ × ℤ/3ℤ  ℤ/6ℤ 
(0,0)  0 
(0,1)  4 
(0,2)  2 
(1,0)  3 
(1,1)  1 
(1,2)  5 



 ≡ 
 
 ≡ 

 = 
 
 = 

 ≡ 
 
 ≡ 

 = 
 
 = 

 = 
 
 = 

 = 
 
 = 

 = 

 ≡ 
 
 ≡ 

 = 
 
 = 


 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 


 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

greatest common divisor algorithm 
Fermat's little theorem 
Euler's theorem 

⇑  ⇑  ⇑  
Bézout's identity 
⇐  extended Euclidean algorithm 
⇐  algorithm for finding multiplicative inverses 
⇒  Euler's totient function φ 
⇑  
Chinese remainder theorem 
⇐  CRT solver for two equations 

⇑  
linear congruence theorem 
⇐  general CRT solver for two equations 

⇑  
induction  ⇐  general CRT solver for n equations 
formula for 3+4ℤ primes 
⇐  square roots modulo p 

⇑  
Hensel's lemma  ⇐  square roots modulo p^k 

⇑  
CRT solver for two equations 
⇐  square roots modulo n ⋅ m 
[]
.
a6.*
(submitted to the location hw6/a6.*
). The file extension may be anything you choose; please ask before submitting a file in an exotic or obscure file format (plain text is preferred). Please follow the gsubmit directions.
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

hw6/a6.py
using gsubmit
any time before the date of the final):
Suppose you are given an efficient function blackbox()
that takes three positive integers k1
, k2
, and n
where k1
< k2
. For each possible exponent k
∈ {k1
, ..., k2
}, the function computes the average of the set of values:

k
∈ {k1
, ..., k2
}. An inefficient but equivalent implementation is provided below for testing purposes:
factor(n)
that can take any composite n
that is the product of two distinct primes, and returns a pair (p,q)
where p
and q
are the factors of n
. Your implementation of factor()
may make a number of calls to blackbox()
that is polynomial in log(n
), but not more than that.
 ≡ 
 
 ≡ 

 ∈ 
 
 ∈ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ∈ 
 
 ∈ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ∈ 
 
 ∈ 

 ∈ 

 ≡ 

 = 

 = 

 

 = 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 

 = 

 = 


 = 

 = 
 
 = 
 
 ≡ 

 → 
 
 → 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 


csa2/csa3
.True
and False
.and
, or
, and not
.+
, *
, 
, and /
. The infix operator //
represents integer division, and the infix operators **
represents exponentiation. Negative integers are prefixed with the negation operator 
.==
, !=
, <
, >
, <=
, >=
are available.int()
function can convert a string that looks like an integer into an integer.'
or "
characters. Strings can be treated as lists of singlecharacter strings. Another way to look at this is that there is no distinction between a character and a string: all characters are just strings of length 1. Multiline strings can be delimited using """
or '''
(i.e., three quotation mark characters at the beginning and end of the string literal).''
or ""
.+
.len()
returns the length of a string.s[i]
). These characters are also strings themselves.[
and ]
, with the individual list entries separated by commas. Lists cannot be members of sets.[]
.+
.len()
returns the length of a list.a[i]
).in
relational operator.(
and )
, with entries separated by commas. The main distinction between lists and tuples is that tuples are hashable (i.e., they can be members of sets).()
.x
is denoted using (x, )
.+
.list()
function.tuple()
function.len()
returns the length of a tuple.t[i]
).in
relational operator.set()
..union()
and .intersect
correspond to the standard set operations.set()
function.list()
or list()
function, respectively.len()
returns the size of a set.in
relational operator.frozenset()
function.
{}
.list(d.keys())
.list(d.values())
.len()
returns the number of entries in the dictionary.d[key]
).for
clause. This will filter which combinations are actually used to add a value to the resulting list.
type()
can be used to determine the type of a value. Below, we provide examples of how to check whether a given expression has one of the common Python types:
if
, else
, and/or elif
), an iteration construct (i.e., a for
or while
loop), a return
statement, or a break
or continue
statement.def
keyword, followed by the name of the function or procedure, and then by one or more arguments (delimited by parentheses and separated by commas).
else
). The body of each branch is an indented sequence of statements.
if
). The body is executed over and over until the expression in the condition evaluates to False
, or a break
statement is encountered.