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 useful computational solutions to problems such as random number generation, prime number generation, error correction, trusted and distributed storage, secure communication, and others.
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 over the course of history. 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 representing and 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 
{(0,1), (1,2), (2,0)}  permutation  random number sequence 
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  meaning  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} 

False <= True 
f_{1} iff f_{2} 

True == False 
¬ f  true if f is false  not (True or (False and True)) 
( f )  true if f is true  (True and (not (False)) 
predicate example  depends on the definition of the predicate 
isPrime(7) 
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 

the sun is visible  it is daytime  meaning  interpretation 
true  true  true  a sunny day 
true  false  false  
false  true  true  a cloudy day 
false  false  true  nighttime 

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 is prime 

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}) {1,2,3}  {4,5} 
S_{1} ∩ S_{2}  {z  z ∈ ℤ, z ∈ S_{1} and z ∈ S_{2}}  {1,2,3}.intersection({2,3,5}) {1,2,3} & {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, ...} 
subset()
operation on sets.
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 
X
and Y
.
R
is a relation over a set X
.

R
and a set X
and determines whether that relation is asymmetric? Recall that we can represent the implication logical operator using the Python operator <=
.
 = 

 = 

{'Alice', 'Bob', 'Carl', 'Dan', and 'Eve'}
:
hw1/hw1.py
. Please follow the gsubmit directions.
cube(n)
that takes a single positive integer argument n
and returns True
if and only if n
is a perfect cube (i.e., there exists an integer k
such that k
^{3} = n
). You cannot use loops, and you must use exists()
to receive credit. Efficiency is not important.
properPrimeFactors(n)
that takes a single positive integer argument n
and returns a finite set of integers containing all the prime proper factors of that number.
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 prime proper factor are related. If a number has no proper prime factors, then it shares no proper prime factors with any other number (including itself).
shared()
(assuming its input is a finite set of positive integers). Define three veriables in your code; each will represent a counterexample input (if it exists) that leads to an output that does not have the corresponding property:
shared()
, simply assign 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. For example, if we were doing the same thing for the property of asymmetry, we would choose a value for asymmetric
such that:
(1,2)
).isSymmetric()
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 symmetric relation on X
, and it should return False
otherwise.
isTransitive()
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 transitive relation on X
, and it should return False
otherwise.isEquivalence()
that takes as its input two arguments: a set X
and a relation R
. The function should return True
if the relation R
is an equivalence relation on X
, and it should return False
otherwise. Hint: read the notes in this section carefully and reuse functions that have already been defined.
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
:
R3
. Solutions that use an explicitly defined set will receive no credit.
 = 

 = 

 = 

 ∈ 
 
 ∈ 

 = 
 
 = 
 
 = 

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} and c_{2} ⊂ c_{1}, i.e., 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 
hw2/hw2.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)
), the abs()
function for computing the absolute value of an integer, and the //
for integer division (you should avoid using /
because it does not work for very large integers). 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.
'''
...'''
, in hw2.py
. You may use the =
ascii character to represent the ≡ relational operator on congruence classes.closest(t, ks)
that takes two arguments: a target integer t
and a list of integers ks
. The function should return the integer k
in ks
that is closest to t
(i.e., the integer k
in ks
that minimizes the absolute value of the difference t
− k
 between the two numbers). This will serve as a helper function for subsequent problems in this assignment.
findCoprime(m)
that takes a single positive integer argument m
and returns an integer b
where b
> 1 and b
is coprime with m
. 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 be coprime with the input. Hint: use facts about coprime numbers (e.g., this, this, this, this, and/or this); the efficiency of the probable prime generator you must assemble in the last problem will depend on the coprimes your algorithm finds not being on the "edges" of the range.
randByIndex(m, i)
that takes two positive integer arguments: m
represents the upper bound of random numbers to be generated, and i
represents an index specifying which random number in a the sequence should be generated. You may assume m
≥ 4 and that 1 ≤ i
≤ m
− 1. The function must return the i
th "random" number in a permutation of the numbers {0, ..., m
− 1}. 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 examples below.
//
when dividing;m.bit_length()
method to efficiently obtain the bit length of an integer.probablePrime(m)
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. Implementations that perform an exponentially large exhaustive search, even if the algorithm is mathematically correct, will not earn full credit.
makePrime(d)
that takes a single integer argument d
where d
>= 1 and returns a probably prime number that has exactly d
digits. Your implementation should be sufficiently efficient to produce an output for d
= 100
in a reasonably short amount of time. 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 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 
 ≡ 


 ≡ 
 
 ≡ 
 
 ≡ 
 
 = 
 
 ≡ 

 ≡ 

 
 ≡ 


 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 

 ≡ 

 = 

 = 

 = 

 = 
 
 = 
 
 = 

 = 
 
 = 
 
 = 

 = 

 = 
 
 = 

 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 

 < 

 < 
 < 
 
 < 
 < 

 = 

 = 
 
 = 
 
 ≡ 
 
 = 

 = 
 
= 
 
= 

 = 

 = 
 
 ≡ 
 
 ≡ 

 = 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 = 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
⋮  
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 
 
 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 


 > 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 = 
 
 = 

 ≥ 
 
 ≥ 
 
 ≥ 
 
 ≥ 


 ≡ 
 

 ≡ 
 

 ≡ 

 
 
 
 

 = 
 
 = 
 
= 
 
= 

 = 
 
= 
 
= 

 = 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 

 = 

 = 
 
= 

 = 

 = 
 
 = 
 
 = 
 
= 
 
= 
 
= 
 


 = 

 = 

 ≡ 
 
= 
 
 = 
 
= 
 
= 

 = 

 = 

 ≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
= 
 
= 
 
= 

 ≡ 
 
= 
 
= 
 
= 
 
= 
 
= 

 = 
 
 = 

 = 
 
= 
 
= 
 
= 
 
= 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 = 

 = 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
 ≡ 
 
≡ 
 
≡ 

hw3/hw3.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 hw3.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) 
hw4.py
(submitted to the location hw4/hw4.py
). Please follow the gsubmit directions.
'''
...'''
, in hw4.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.
phiFromPhiFour(n)
for the existing intractable problem of computing φ that uses a solver for φfour (call it phi_four()
) as a subroutine. Note: remember that the four primes must be distinct; your reduction must work for all possible instances of the intractable problem.
generate(k)
that takes a single integer input k
and returns a tuple (n,e,d)
corresponding to the public values n
and e
and private key d
in the RSA cryptographic protocol. The output n
must be the product of two distinct, randomly chosen k
digit primes. You may import and use the Python random number generator (from random import random
or from random import randint
), and you may want to reuse the extended Euclidean algorithm implementation provided in the previous homework assignment.encrypt(m, t)
that takes two inputs: an integer m
and a tuple (n,e)
representing an RSA public key. It should return a single integer: the RSA ciphertext c
.decrypt(c, t)
that takes two inputs: an integer c
representing the ciphertext and a tuple of two integers (n,d)
representing an RSA private key. It should decrypt c
and return the original message m
.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
.
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. Your algorithm in this problem must work on all possible inputs under the assumption that decryptMsgRabin()
also works on all inputs (not just the fake inputs handled by the definitions above) and that an encrypted message c is never represented by the same congruence class as the original, unencrypted message m or − m (i.e., the implementation follows the guideline regarding good ranges for messages at the end of the definition of the Rabin protocol).


 = 



 = 

 = 
 
 = 
 
 = 
 
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 
 = 
 
 = 
 
 = 

 = 

 ≡ 

 = 

 = 

 ≡ 
 ≡ 

 = 

 = 

 ≡ 
 ≡ 

 ≡ 

 ≡ 

 = 

 = 

 = 

 = 

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




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.http://cspeople.bu.edu/lapets/235/unreliable.php
(e.g., the result of ((2 ⋅ 3 ⋅ 4) mod 7) can be obtained at http://cspeople.bu.edu/lapets/235/unreliable.php?n=7&data=2,3,4
). You can use the Python function below to invoke this script (this Python code needs to run on a computer connected to the internet).
http://cspeople.bu.edu/lapets/235/reliable.php
.privateProduct(xs, p, q)
that takes three inputs: a nonempty list of integers xs
, a prime p
, and another distinct prime q
. The function must compute the product modulo p
of all the integers in the list xs
(assuming the web service performs its job correctly, which it may sometimes not do):
 = 

xs
on its own; it must use unreliableUntrustedProduct()
to do so, and at the same time it must not send the actual integers in xs
over the web or reveal them to the web service. Your implementation should leak no information about the entries in xs
or the product obtained by multiplying them to anyone (unless they can solve an intractable problem in modular arithmetic).q
to create public and private RSA keys, and then encrypt all the integers in xs
(you will need to encrypt them modulo n
instead of modulo p
because RSA needs a composite modulus). Next, use unreliableUntrustedProduct()
to compute the product of the RSAencrypted integers modulo n
(i.e., take advantage of this isomorphism as in this homomorphic encryption example). Finally, your privateProduct()
implementation should decrypt the result and return the product modulo p
.
validPrivateProduct(xs, p, q)
that takes three inputs: a nonempty list of integers xs
, a prime p
, and another distinct prime q
. The function must always correctly compute the product modulo p
of all the integers in the list xs
:
 = 

xs
on its own; it must use unreliableUntrustedProduct()
to do so, and at the same time it must not send the actual integers in xs
over the web or reveal them to the web service.r
in ℤ/q
ℤ. For each integer xs[i]
in the list, convert the pair (xs[i], r)
into a value in ℤ/n
ℤ via the CRT isomorphism. Then encrypt all these ℤ/n
ℤ values using RSA and use unreliableUntrustedProduct()
to compute their product. Finally, your validPrivateProduct()
implementation should decrypt the result and convert it back to an answer modulo p
via the opposite direction of the CRT isomorphism.
unreliableUntrustedProduct()
is actually correct, determine whether the decrypted value modulo q
has the expected value (i.e., is it really r
^{len(xs)} modulo q
). If this check fails, keep repeating the entire process from the beginning until it succeeds.
isomorphism(A, B)
that takes two tuples A
and B
as inputs. Each tuple consists of two entries: the first is an ordered list of elements from an algebraic structure, and the second is a function on elements of that binary structure. Thus, the tuple A
represents an algebraic structure (A, ⊕), and the tuple B
represents an algebraic structure (B, ⊗). You may assume that the list of elements is closed under the operation represented by the function. You may also assume that the bijection between the sets A and B is already provided by the order of the elements in each list (i.e., the ith entry in the first list corresponds to the ith entry in the second). The isomorphism()
function should return True
if there is indeed an isomorphism between (A, ⊕) and (B, ⊗), and False
otherwise.
 ≅ 

 ≅ 

 ≅ 
 ≅ 

 = 
 = 
 = 

 = 
 
 = 

 ≡ 

 = 
 
 = 
 
 = 
 
 ≡ 

 = 

 = 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 = 




 ≡ 

 ≡ 

 ≡ 
 
≡ 

 = 

ℤ/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 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

""
be the empty string. Then (S, +) is an algebraic structure that is a monoid because string concatenation is associative and ""
is the identity with respect to string concatenation.
[]
be the empty list. Then (L, +) is an algebraic structure that is a monoid because list concatenation is associative and []
is the identity with respect to list concatenation.
[]
.
abstract algebraic structure  concrete data structure 
element in set of generators S  individual character, string, or data object 
set of generators S  base cases; alphabet; data containers 
operator ⊕  constructor for node with children; operator/function/method on data items 
element in closure of S under ⊕  individual data object 
closure of S under ⊕  set of all possible data objects 
magma  commutative magma 
semigroup  commutative semigroup 
monoid  group  abelian group 

typical data structures 
binary trees under node constructor 
binary trees with unordered branches under node constructor 
lists with list concatenation; strings with string concatenation 
sets with duplicates 
lists with list concatenation and empty list; strings with string concatenation and empty string 

distributed computation 
must operate on data in its original ordering and hierarchization 
must operate on data in its original hierarchization 
must operate over original ordering 
can operate on data in any order 
can employ identity as a base case; can ignore identity entries 
can "cancel" pairs of adjacent inverses 
can "cancel" all elements that can be paired with an inverse 
distributed storage 
must store original ordering and hierarchization 
must store original hierarchization 
must store original ordering  can store in any order 
no need to store identities 

compression  common subtrees  common hierarchies  runlength encoding  distinct elements with quantities 
can ignore identity entries 
can "cancel" pairs of adjacent inverses; can apply invertible transformations 
can "cancel" all elements that can be paired with an inverse 
example/ test case enumeration 
can enumerate examples/test cases automatically  
proving implementation works correctly for all inputs 
can show this by structural induction 
 = 

 ≡ 
 
 ≡ 

 = 

 = 


 ≡ 

 ≡ 

 = 
 
 = 

 ≅ 

 = 

 = 

 
 = 

 
 = 


hw6.py
(submitted to the location hw6/hw6.py
). Please follow the gsubmit directions.
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

solveOne(c, a, m)
that takes three integers c
, a
, and m
≥ 1. If it exists, the function should return the solution x ∈ {0, ..., m
1} to the following equation:
 ≡ 

None
. The function must work correctly for all possible equations (you should use the linear congruence theorem).
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()
, the function should return None
.
solveAll(es)
that takes a list of one or more equations, each of the form (c, a, m)
. The function should return the unique solution x to the system of equations represented by the list of equations. If the system of equations has no solution, the function should return None
.
factor(n)
that finds a nontrivial factor of a composite number input n
by calling quantum()
. Solutions that use exhaustive search will receive no credit.+
anywhere in your solutions to this problem. You may assume you are given access to a function plus256unreliable(x, y)
that returns an answer that is at most 4 away from the true sum modulo 256
(assume there is no chance of this error causing the answer to wrap around):
 < 

plus16(x, y)
that reliably returns (x + y) % 16
with 100% accuracy. You may use //
, *
, plus256unreliable()
, and numerical constants, but you may not use anything else in your definition. Hint: you can call plus256unreliable()
more than once.plus256(x, y)
that reliably returns (x + y) % 256
with 100% accuracy. Your solution must use solveAll()
, and you are allowed to use %
, but you may not use the addition or subtraction operators: choose four appropriate prime or mutually coprime moduli, perform the addition operations modulo those moduli, then restore the original result using solveAll()
.decompose()
that decomposes a given element in the algebra into a list in which each generator from {a, b, c, d, e, f, g} that occurs in the input element is paired with exactly one integer. The integer should be chosen so that reassemble()
below can work correctly. Your output should look something like the following (the full output is not revealed as it is part of the problem):
reassemble()
that takes a randomly rearranged output from decompose()
and reassembles an equivalent element within the algebraic structure.
 = 
 
 = 
 
 = 


 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 


 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ∈ 
 
 ∈ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ∈ 
 
 ∈ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ∈ 
 
 ∈ 

 ∈ 

 ≡ 

 

 = 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 

 = 

 = 


 = 

 = 
 
 = 
 
 ≡ 

 → 
 
 → 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

gsubmit
. This section reproduces and extends some of the instructions already made available by the BU Computer Science Department.csa
machines maintained by the CS Dept. You will need to physically visit the undergraduate computing lab located at 730 Commonwealth Avenue, on the third floor in room 302.csa
home directory. If you are using Windows, you will also need an SSH client (such as PuTTY).
local device

your csa2 /csa3 home directory 
your gsubmit directory for CS 235 
csa2
or csa3
using an SCP or SSH client and create a directory for your submission in your CS account home directory. Note that in the examples below %>
represents a terminal prompt, which may look different on your system.
local device

your csa2 /csa3 home directory

your gsubmit directory for CS 235 
csa2
or csa3
using an SCP client and copy your completed file(s) into that directory.
local device

⇒ 
your csa2 /csa3 home directory

your gsubmit directory for CS 235 
csa2
or csa3
using an SSH client and run the gsubmit
commands to copy the files from your CS account home directory to the gsubmit
directories to which the course staff has access.
local device

⇒ 
your csa2 /csa3 home directory

⇒ 
your gsubmit directory for CS 235

csa2/csa3
..py
. For example, suppose the following is contained within a file called example.py
:
python3
, python3.2
, python3.3
, etc. depending on the Python installation you're using). Note that in the examples below %>
represents a terminal prompt, which may look different on your system.
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]
).example()
is defined as follows:
*
operator, the scatter operator, or the splat operator) involves providing a list to the function, preceded by the *
symbol; the arguments will be drawn from the elements in the list.
**
operator) involves providing a dictionary to the function, preceded by the **
symbol; each named paramter in the function definition will be looked up in the dictionary, and the value associated with that dictionary key will be used as the argument passed to that parameter.
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.