NOTE: This page contains all the machine-verifiable examples presented during the lectures, as well as all the homework assignments. Click here to go back to the main page with the course information and schedule.

• Introduction
• Informal Motivating Example: Random Number Generation
• Review of Logic with Sets, Relations, and Operators
  • Formulas (without quantifiers)
  • Terms: integers and term operators that take integer inputs
  • Formulas: relational operators and predicates dealing with integers
  • Terms: finite sets of integers, term operators that take set inputs, and set comprehensions
  • Formulas: quantifiers over finite sets of integers
  • Formulas: predicates dealing with finite sets of integers
  • Terms: set products and binary relations
  • Formulas: predicates dealing with relations
  • Assignment #1: Prerequisite Review: Logic, Integers, Sets, and Relations
  • Terms: set quotients and quotient maps
  • Term operators and their properties
• Modular Arithmetic
  • Terms: congruence classes in Z/mZ and term operators on congruence classes
  • Formulas: relational operators dealing with congruence classes in Z/mZ
  • Algebra of congruence classes
  • Example: Random Number Generation
  • Generating prime numbers
  • Greatest common divisor and related facts
  • Testing whether a number is probably prime
  • Assignment #2: Modular Arithmetic, Random Sequences, and Primes
  • Chinese remainder theorem and applications
  • Euler's totient function, multiplicative inverses in Z/mZ, and applications
  • Assignment #3: CRT, Totient Function, Inverses, and Applications
• Complexity of modular arithmetic algorithms
  • Complexity of (probably) intractable problems
  • Complexity of algorithms for solving tractable problems
  • Assignment #4: Reductions, Quadratic Residues, and Review
• Review #1
• Algebraic Structures
  • Algebraic Structures and Axioms
  • Implementations of Algebraic Structures and Operations
  • Group of all permutations (symmetric group)
  • Groups of shift permutations (cyclic groups)
  • Assignment #5: Algebraic Structures and Permutations
  • Isomorphisms: Equivalence of Algebraic Structures
  • Reasoning about Algebraic Structures using Induction
  • Subgroups and the Direct Product of Groups
  • Algebraic Structures and Cosets
  • Generalizations of CRT and Applications
  • Assignment #6: Generalizing CRT
• Review #2
• Bonus Assignment

---

Introduction

When many real-world 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, rings, residues, matrices, polynomials, 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 mathematics community. 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

The above illustrates the different levels of abstraction that may exist for a given problem. We employ a language of symbols to denote certain abstract structures, which may correspond to actual structures in the world. A string of symbols corresponds to a particular abstract object. Notice that the actual object being modelled and the abstract structure behave the same way, and that this behavior implies certain rules about how we can manipulate the symbols without changing the object that they name. For example, we can represent the same graph using the two strings of symbols "{(1,2),(2,3),(3,1)}" and "{(1,2),(2,3),(3,1)}", or the same number of objects using "2+3", "3+2", "1+4", and so on.

Informal Motivating Example: Random Number Generation

Let us informally consider the problem of generating a sequence of random positive integers. Random number generators are needed in many situations and applications, including:

• generating unique identifiers for database records, objects, etc.;
• generating a one-time pad for a simple encryption scheme;
• generating public and private keys for more sophisticated encryption and signature schemes;
• simulation and approximation methods that employ random sampling (Monte-Carlo, and so on).

Different applications will impose different requirements on what is and is not a sufficiently "random" sequence of number. Suppose we adopt the following method:

• n₀ = a number in the range (inclusive) 0 to 5;
• n_i = (2 ⋅ n_i-1 + 1) mod 6.

We can consider another method:

• n₀ = an initial seed integer 10⁴ > n ≥ 10³;
• n_i = only the last four digits of n_i-1².

Frequent repetition of a sequence may or may not be allowed in our given application. Does the above method produce repeating numbers? How often? For how many initial seeds? How do we choose a good seed? We can measure a physical process or component (a clock, a keyboard), but even under these circumstances we need a way to reason about the range of random values the measurement produces, and the range of random values the application requires. How do we begin to approach and formally characterize these aspects of the problem so that we are certain we are meeting the requirements imposed by the application?

One way to model a random number generation process is to view it is a permutation. In fact, there is more than one way to view the process as a permutation. We could simply count up from 0 to m and apply the same permutation to each 0 ≤ n ≤ m in order to produce the nth random number in the sequence. Is there an efficient way (i.e., using no more memory than O(log m)) to compute a random number from each n such that a number never repeats?

In this course we will learn about a variety of mathematical structures and their properties that will allow us to precisely specify the above problem and others like it, to identify what solutions are appropriate for such a problem, and to implement these solutions correctly and, where necessary, efficiently.

---

Review of Logic with Sets, Relations, and Operators

In this section, we will review several abstract structures and associated properties (and the symbolic language used to represent them) that you should have already encountered in past courses. Simultaneously, we will review one way in which these structures can be implemented and manipulated within the modern programming language Python.

As with most human languages that have developed organically over time, mathematics has a rich and often redundant vocabulary. We introduce many terms in this section that we will use consistently in this course. However, keep in mind that there are often other synonyms within mathematics and computer science for these structures.

Formulas (without quantifiers)

A logical formula or formula is a string of symbols that follow a certain syntax. If the formula is written using a correct syntax, we can ask whether the formula is true or false. The symbols or, and, not, implies, and iff are logical operators.

formula	true or false	example of one possible Python representation
true	always true	True
false	always false	False
f1 and f2	only true if both f1 and f2 are true	True and False
f1 or f2	true if f1 or f2 (or both) are true	True or (False and True)
f1 implies f2	if f1 is true, then f2 must be true or equivalently f1 is false, or f2 is true
f1 iff f2	f1 and f2 are either both true or both false	True == False
¬ f	true if f is false	not (True or (False and True))

The following table may help with gaining a good intuition for the meaning of the implies operator.

meaning of left-hand side (premise)	meaning of right-hand 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

Terms: integers and term operators that take integer inputs

A term is a string of symbols that represents some kind of mathematical structure. In our case, terms will initially represent integers or sets of integers. Terms may contain term operators. We can view these as functions that take terms as input and return terms as output. The term operators for terms that represent integers with which we will be working are +, -, ⋅, and mod.

term	what it represents	example of one possible Python representation
0	0	0
1	1	1
z1 + z2	the integer sum of z1 and z2	3 + 4
z1 - z2	the integer difference of z1 and z2	(1 + 2) - 4
z1 ⋅ z2	the integer product of z1 and z2	3 * 5
z1 mod z2	the remainder of the integer quotient z1 / z2 z1 - ⌊ z1/z2 ⌋ ⋅ z2	17 % 5
z1z2	product of z2 instances of z1	pow(2,3)

Formulas: relational operators and predicates dealing with integers

A term can only appear in a formula if it is an argument to a predicate. A few common predicates involving integers are represented using relational operators (e.g, ≤, ≥).

formula	what it represents	example of one possible Python representation
z1 = z2	true if z1 and z2 have the same meaning; false otherwise	1 == 2
z1 < z2	true if z1 is less than z2; false otherwise	4 < 3
z1 > z2	true if z1 is greater than z2; false otherwise	4 > 3
z1 ≤ z2	true if z1 is less than or equal to z2; false otherwise	4 <= 3
z1 ≥ z2	true if z1 is greater than or equal to z2; false otherwise	4 >= 3
z1 ≠ z2	true if z1 is not equal to z2; false otherwise	4 != 3

We can define our own predicates as well. Notice that one way we can represent these in Python is by defining a function that return a boolean result.

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)

In Assignment #1, you will define the following predicates. We will also use them throughout the course.

Definition: For any x,y ∈ Z, x | y    iff   y/x ∈ Z.

Definition: For any y ∈ Z, y is prime    iff    y > 1 and for any integer x > 0, x | y implies x = 1 or x = y.

formula	what it represents
x | y	y / x ∈ Z x divides y y is divisible by x y is an integer multiple of x y mod x = 0
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

Terms: finite sets of integers, term operators that take set inputs, and set comprehensions

The following are examples of terms the meaning of which is a finite set of integers (with the exception of the set size terms, the meaning of which is a positive integer).

term	what it represents	example of one possible Python representation
∅	a set with no elements in it	set([])
{1,2,3}	{1,2,3}	set([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}	set([x for x in set([1,2,3,4,5,6]) if x > 3])
|{1,2,3,4}|	4	len(set([1,2,3,4]))

The following are term operators on terms the meaning of which is a finite set of integers.

term	what it represents	example of one possible Python representation
S1 ∪ S2	{z | z ∈ Z, z ∈ S1 or z ∈ S2}	{1,2,3}.union({4,5})
S1 ∩ S2	{z | z ∈ Z, z ∈ S1 and z ∈ S2}	{1,2,3}.intersection({2,3,5})
|S|	the number of elements in S	len({1,2,3})

While these are not finite sets of integers, we introduce the following two set terms in order to reference them throughout the notes.

Definition: Let Z be the set of all integers.

Definition: Let N be the set of all positive integers, including 0.

term	what it represents
N	{0, 1, 2, ...}
Z	{..., -2, -1, 0, 1, 2, ...}

Formulas: quantifiers over finite sets of integers

Suppose we define the following two Python functions that take predicates (or, more specifically, functions that represent predicates) as input.


   def forall(X,P): return len(X) == len(set([x for x in X if P(x)]))
  
   def exists(X,P):
     for x in X:
       if P(x):
         return True
     return False
  
   def subset(X,Y): return forall(X, lambda x: x in Y)

Then we can introduce the following definitions and corresponding Python examples.

formula	what it represents	example of one possible Python representation
1 ∈ {1,2,3}	true	1 in set([1,2,3])
4 ∈ {1,2,3}	false	4 in set([1,2,3])
∀ x ∈ {1,2,3}, x > 0 and x < 4	true	forall(set([1,2,3]), lambda x: x > 0 and x < 4)
∃ x ∈ {1,2,3}, x < 1 and x > 3	false	exists(set([1,2,3]), lambda x: x < 1 or x > 3)
∀ x ∈ ∅, f	true
∃ x ∈ ∅, f	false

Notice that when we quantify over an empty set with a universal quantifier ∀, the formula is always true. When we quantify over an empty set with an existential quantifier, the formula is always false (since no element satisfying any formula could exist). We can see that the Python functions for these quantifiers are consistent with this interpretation.

Exercise: Implement Python functions that correspond to formulas which can be used to define each of the following statements about a set X and a predicate P.

• All the elements of a set X satisfy the predicate P.
  def all(X, P): return forall(X, P)
def all(X, P): return len({x for x in X if P(x)}) == len(X)
• None of the elements of a set X satisfy the predicate P.
  def none(X, P): return forall(X, lambda x: not P(x))
def none(X, P): return not exists(X, P(x))
def none(X, P): return len({x for x in X if P(x)}) == 0
• At most one of the elements of a set X satisfy the predicate P.
  def atMostOne(X, P): return len({x for x in X if P(x)}) <= 1
def atMostOne(X, P): return one(X, P) or none(X, P)
• At least one of the elements of a set X satisfy the predicate P.
  def atLeastOne(X, P): return exists(X, P)
def atLeastOne(X, P): return len({x for x in X if P(x)}) >= 1
• Exactly one of the elements of a set X satisfy the predicate P.
  def one(X, P): return len({x for x in X if P(x)}) == 1
def one(X, P): return atLeastOne(X, P) and atMostOne(X, P)

Formulas: predicates dealing with finite sets of integers

The following are examples of formulas that contain relational operators dealing with finite sets of integers.

formula	what it represents	example of one possible Python representation
3 ∈ {1,2,3}	true	3 in set([1,2,3])
{1,2} ⊂ {1,2,3}	true	subset(set([1,2]), set([1,2,3]))
{4,5} ⊂ {1,2,3}	false	subset(set([4,5]), set([1,2,3]))

Below are the general forms of formulas containing relational operators dealing with finite sets of integers.

formula	what it represents
z ∈ S	true if z is an element of S; false otherwise
S1 ⊂ S2	∀ z ∈ S1, z ∈ S2
S1 = S2	S1 ⊂ S2 and S2 ⊂ S1

Terms: set products and binary relations

Definition: The product of two sets X and Y is denoted X × Y and is defined to be the set of ordered pairs (x,y) for every possible combination of x ∈ X and y ∈ Y.

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)}	set([(x,y) for x in set([1,2]) for y in set([4,5,6,7])])

Definition: A set R is a relation between the sets X and Y if R ⊂ X × Y.

Formulas: predicates dealing with relations

There are several common properties that relations may possess.

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 (many-to-one) 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 -1 is the inverse of R	R -1 = { (b,a) | (a,b) ∈ 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
R is an antisymmetric relation on X	R ⊂ X × X and ∀ x ∈ X, ∀ y ∈ X, (x,y) ∈ R and (y,x) ∈ R implies x = y
R is a partial order on X	R ⊂ X × X and R is a reflexive relation on X and R is an antisymmetric relation on X and R is a transitive relation on X

Notice that we may have R such that R is a function, but R ^-1 is not a function.

Exercise: Write a Python function that takes a finite set of integers and builds the relation on that set corresponding to the operator ≤.

Exercise: Write a Python function that takes a relation R and a set X and determines whether R is a symmetric relation on X.

We introduce several terms that deal with the relationship between the relation and the members and subsets of the two sets that the relation involves.

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 pre-image of y under R between X and Y	R is a function from X to Y and A = {x | (x,y) ∈ R}

Exercise: Implement Python functions that correspond to each of the structures above.

Fact: If R is a function from X to Y and R is an injection from X to Y and R is finite, and if B is the image of R, then |B| = |X| and (because B ⊂ Y and so |B| ≤ |Y|), we have that |Y| ≥ |X|.

Exercise: Determine whether the relation R = {(x,y) | x ∈ Z, y ∈ Z, x | y} is an equivalence relation (check whether each of the three properties of an equivalence relation are satisfied).

Exercise: Determine whether the relation R = {(x,y) | x ∈ Z, y ∈ Z, x | y} is a partial order on Z (check whether each of the three properties of a partial order are satisfied).

---

Assignment #1: Prerequisite Review: Logic, Integers, Sets, and Relations

In this assignment you will define Python functions that represent various constructs. For this assignment, you will submit a single Python source file a1.py.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). Solutions to each of the programming problem parts below should fit on one or two lines. You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts.

1. 1. Define a Python function divides() that takes two positive integer arguments and returns True only if the first argument divides the second argument.
   2. Define a Python function prime() that takes a single argument and returns True only if the argument is a prime positive integer. You may use the range(), len(), and divides() functions.
2. In this problem, you will implement a small algorithm that can generate arbitrarily many prime numbers. This algorithm is very inefficient; its purpose is to serve as a programmatic argument that there are infinitely many distinct prime numbers.
   1. Implement a Python function factors that takes a single positive integer argument and returns the set of factors of that number.
   2. Implement a Python function primeFactors that takes a single positive integer argument and returns the set of prime factors of that number.
   3. Implement a Python function anotherPrime that takes a set of prime numbers and returns a new prime that is distinct from all the others in the list. To accomplish this, compute the product p of all the prime numbers in the set, then return a prime factor that belongs to the set of factors of p+1.
   4. Implement a Python function generatePrimes that takes a single input n and returns a set of n distinct prime numbers. Hint: use recursion and another function you have already implemented.
3. 1. Define a Python function implies() that takes two arguments and correctly implements the logical operator implies.
4. To receive credit for each part below, your solutions must employ forall, exists, and/or list comprehensions. Solutions that are more than one or two lines in length will receive no credit.
   1. Define a Python function product(X,Y) that takes two sets as arguments and returns the set product of the sets.

   2. Define a Python function relation(R,X,Y) that takes three arguments and returns True only if the first argument R is a relation between the second and third arguments X and Y.

   3. Define a Python function function(R,X,Y) that takes three arguments and returns True only if the first argument R is a function from X to Y.

   4. Define a Python function injection(R,X,Y) that takes three arguments and returns True only if the first argument R is an injection from X to Y.

   5. Define a Python function surjection(R,X,Y) that takes three arguments and returns True only if the first argument R is a surjection from X to Y.

   6. Define a Python function bijection(R,X,Y) that takes three arguments and returns True only if the first argument R is a bijection from X to Y.

   7. Define a Python function transitive(R,X) that takes two arguments and returns True only if the first argument R is a transitive relation on X.

   8. Define a Python function lte(R) that takes one argument and returns True only if the relation R is a subset of the relation represented by the relational operator <=.

---

Terms: set quotients and quotient maps

Given an equivalence relation on a set, we can partition that set into a collection of distinct subsets, called equivalence classes, such that all the elements of each subset are equivalent to one another.

Definition: For any set X and equivalence relation R on X, let the quotient set of X with respect to R, denoted X/R, be defined as:

X/R

=

{{y | (x,y) ∈ R} | x ∈ X}

Exercise: Implement a Python function that takes two inputs (a set X and an equivalence relation R on that set), and outputs the quotient set X/R.

Below, we evaluate the above function on an example input.

Definition: For a set X and a relation R over X, the relation that relates each x ∈ X to its equivalence class in X under R is called the quotient map. The function is typically denoted using [ ... ]. That is, [x] is the equivalence class of x under R.

Exercise: Why is the relation {(x,[x]) | x ∈ X} necessarily a map? Suppose it is not a map. What would this imply?

Exercise: Implement a Python function that takes two inputs (a set X and an equivalence relation R on that set), and outputs the quotient map taking each element x ∈ X to its corresponding equivalence class [x] ∈ X/R.

Exercise: Determine whether {(x,y) | x ∈ Z, y ∈ Z, x + y mod 2 = 0} is an equivalence relation.

Term operators and closure properties

We have names for several common properties that operators may possess for a given set. In the table below, We define them precisely using logical notation.

property	definition
S is closed under ⊕	∀ x,y ∈ S,     x ⊕ y ∈ S
⊕ is commutative on S	∀ x,y ∈ S,     x ⊕ y = y ⊕ x
⊕ is associative on S	∀ x,y,z ∈ S,     (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)
⊕ has a left identity 1 in S	∀ x ∈ S,     1 ⊕ x = x
⊕ has a right identity 1 in S	∀ x ∈ S,     x ⊕ 1 = x
⊕ has an identity 1 in S	∀ x ∈ S,     1 ⊕ x = x ⊕ 1 = x
⊗ distributes across ⊕ in S	∀ x,y,z ∈ S,     x ⊗ (y ⊕ z) = (x ⊗ y) ⊕ (x ⊗ z)

---

Modular Arithmetic

Modular arithmetic can be viewed as a variant of integer arithmetic in which we introduce a congruence (or equivalance) relation on the integers and redefine the integer term operators so that they are defined on these congruence (or equivalance) classes.

Terms: congruence classes in Z/mZ and term operators on congruence classes

Exercise: Show that the relation R = {(x,y) | x ∈ Z, y ∈ Z, x mod 17 = y mod 17} is an equivalence relation.

Informally and intuitively, we could think of the structure of the above set as a logical consequence of letting all multiples of m be equivalent to 0. That is, if 0 = m = 2m = ..., then 1 = m + 1 = 2m + 1 = ..., and so on.

term	what it represents
z z mod m z + mZ	{z + (a ⋅ m) | a ∈ Z}
c1 + c2	{(x + y) | x ∈ c1, y ∈ c2}
c1 - c2	{(x - y) | x ∈ c1, y ∈ c2}
c1 ⋅ c2	{(x ⋅ y) | x ∈ c1, y ∈ c2}
cz	c ⋅ ... ⋅ c
c!	c ⋅ (c-1) ⋅ (c-2) ⋅ ... ⋅ 1

Formulas: relational operators dealing with congruence classes in Z/mZ

formula	what it represents
c1 ≡ c2	true only if c1 = c2 where "=" is set equality applied to the congruence classes c1 and c2; false otherwise

Algebra of congruence classes

We use the familiar symbols 0, 1, +, -, and ⋅ to represent operations on congruence classes. When these symbols are used to represent operations on integers, they have certain algebraic properties. Do the operations on congruence classes also share the familiar algebraic properties of the corresponding operations on integers?

Example: Suppose we write the term 3 + 4 ≡ 2 where 2, 3, and 4 are congruence classes in Z/5Z. What is the meaning of this term? First, note the following equivalence.

{ x + y | x ∈ Z, y ∈ Z} = {z | z ∈ Z }

Now, we expand the definitions of congruence classes and the operation + on congruence classes below.

3 + 4	≡	(3 + 5Z) + (4 + 5Z)
	=	{3 + a ⋅ 5 | a ∈ Z} + {4 + b ⋅ 5 | b ∈ Z}
	=	{(x + y)   |   x ∈ {3 + a ⋅ 5 | a ∈ Z}, y ∈ {4 + b ⋅ 5 | b ∈ Z}}
	=	{(3 + a ⋅ 5) + (4 + b ⋅ 5)   |   a ∈ Z, b ∈ Z}
	=	{(3 + 4) + (a ⋅ 5) + (b ⋅ 5)   |   a ∈ Z, b ∈ Z}
	=	{2 + 5 + (a ⋅ 5) + (b ⋅ 5)   |   a ∈ Z, b ∈ Z}
	=	{2 + (1 + a + b) ⋅ 5   |   a ∈ Z, b ∈ Z}
	=	{2 + c ⋅ 5 | c ∈ Z}
	≡	2 + 5Z
	≡	2

Suppose that a and b are congruence classes in Z/mZ. We know that a + b and b + a are also congruence classes (they are sets). We want to show that:

a + b	≡	b + a
(a + mZ) + (b + mZ)	≡	(b + mZ) + (a + mZ)
{(x+y) mod m | x ∈ (a + mZ), y ∈ (b + mZ)}	=	{(y+x) mod m | y ∈ (b + mZ), x ∈ (a + mZ)}

Notice that the last line above is set equality. Thus, it is sufficient to show that:

{(x+y) mod m | x ∈ (a + mZ), y ∈ (b + mZ)}	⊂	{(y+x) mod m | y ∈ (b + mZ), x ∈ (a + mZ)}
{(y+x) mod m | y ∈ (b + mZ), x ∈ (a + mZ)}	⊂	{(x+y) mod m | x ∈ (a + mZ), y ∈ (b + mZ)}

To show the first relationship, we must show that for every integer in {(x+y) mod m | x ∈ (a + mZ), y ∈ (b + mZ)}, that integer is also in {(y+x) mod m | y ∈ (b + mZ), x ∈ (a + mZ)}. Because we know that x + y = y + x when x and y are integers, it must also be that for any x,y ∈ Z:

x + y	=	y + x
(x + y) mod m	=	(y + x) mod m

Thus, for every (x + y) mod m in the first set, there is a corresponding (y + x) mod m in the second set, so the subset relation holds. The argument also works in the other direction. Thus, the two sets are equivalent, so the congruence holds, and + defined on congruence classes is commutative.

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

To show this is true, consider any (x + z mod m) ∈ (a + c) and any (y + z mod m) ∈ (b + c). As in the previous proof, we have that:

x	=	y
x + z	=	y + x
(x + z) mod m	=	(y + z) mod m

Thus, the two congruence classes contain the same elements, so they are equivalent.

We can adjust the argument above in the following way:

x	=	y
x - z	=	y - x
(x - z) mod m	=	(y - z) mod m

We saw that we can add and subtract from both sides of an equation involving congruence classes. Can we also divide both sides by the same factor (or "cancel" that factor) in such an equation? We can do so under certain conditions. In order to show that we can do so, we need a few preliminary facts.

If a mod m = 0 then:

a - ⌊ a/m ⌋ ⋅ m	=	0
a	=	⌊ a/m ⌋ ⋅ m
a / m	=	⌊ a/m ⌋
a / m	∈	Z
m	|	a

If m | a then:

m	|	a
a / m	∈	Z
a / m	=	⌊ a/m ⌋
a	=	⌊ a/m ⌋ ⋅ m
a - ⌊ a/m ⌋ ⋅ m	=	0
a mod m	=	0

We observe that:

a ⋅ c	≡	b ⋅ c
(a ⋅ c) - (b ⋅ c)	≡	0
((a ⋅ c) - (b ⋅ c)) mod p	=	0
((a - b) ⋅ c) mod p	=	0
p	|	((a - b) ⋅ c)

By Euclid's lemma, the fact that c is not divisible by p requires that a - b must be divisible by p. Thus:

p	|	(a - b)
(a - b) mod p	=	0
a - b	≡	0
a	≡	b

Recall that R is a permutation if R is a bijection. In order to be a bijection, R must be both an injection and a surjection.

To show that R is an injection, suppose that it is not. We will derive a contradiction from this assumption, which will tell us that the assumption must be false.

If it is not injective, then there exist distinct non-zero i ∈ {1,...,p-1} and j ∈ {1,...,p-1} where without loss of generality j < i such that:

i	≠	j
(i ⋅ a) mod p	=	(j ⋅ a) mod p
((i ⋅ a) - (j ⋅ a)) mod p	=	0 mod p
((i - j) ⋅ a) mod p	=	0 mod p
p	|	(i - j) ⋅ a

But because a < p, p does not divide a, so the above implies that p | (i - j). But this is also impossible because p > i - j > 0. Also, notice that in the above, we could have simply divided both sides of the second line by a because p does not divide a.

Since assuming that distinct i and j can be related to the same element of the relation's codomain leads to a contradiction, it must be impossible. Thus, R is an injection.

Furthermore, R is an injection from {1,...,p-1} to Z/pZ - {0} and we have that:

|{1,...,p-1}|

=

|Z/pZ - {0}|

Thus, since R maps to at least p-1 distinct elements, and |Z/pZ - {0}| has at most p-1 elements, R must map to every element in Z/pZ - {0}, so it is also a surjection by the Pigeonhole principle.

Since R is both an injection and a surjection from {1,...,p-1} to Z/pZ - {0}, it must be a bijection, and thus a permutation.

Notice that if we extend R by adding (0,0), it is now a permutation from {0,...,p-1} to Z/pZ.

Example: Random Number Generation

Suppose we want to find a way to generate a "random" sequence v of positive integers. Assume we have only one requirement.

Requirement 1: The sequence v has m distinct positive integers between 0 and m-1, where v_i is the ith element in the sequence.

In this case, a relation R ⊂ N × Z/mZ that is a permutation would be sufficient. One such relation is:

v0	=	0 mod m
vi	=	(vi-1 + 1) mod m
R0	=	{(i, vi) | i ∈ {0,...,m-1}}

Notice that the second term in (x, x mod m) is in this case the congruence class modulo m that corresponds to x.

The relation R₀ is indeed a permutation, but it does not satisfy our intuitive notion of a random sequence, so we impose another requirement.

Requirement 2: The sequence v must not be the trivial sequence (0,...,m-1).

Suppose we propose the following relation:

v0	=	0
vi	=	(vi-1 + 2) mod m
R1	=	{(i, vi) | i ∈ {0,...,m-1}}

Notice that we can redefine R₁ above more concisely:

R1

=

{(i, (0 + 2 ⋅ i) mod m) | i ∈ {0,...,m-1}}

Does R₁ always satisfy both requirements? Suppose that m is even. Then we have that there exists j ∈ {0,...,m-1} such that 2 ⋅ j = m. But this means that 2 ⋅ j ≡ 0, so 2 ⋅ (j+1) ≡ 2 ⋅ j + 2 ⋅ 1 ≡ 2 ⋅ 1 ≡ 2 and so on. This means that R₁ is not injective, so the first requirement is not met when m is even.

Suppose we define R₂ to be a variant of R₁ parameterized by some b ∈ {0,...,m-1}:

R2

=

{(i, (0 + b ⋅ i) mod m) | i ∈ {0,...,m-1}}

What conditions can we impose on b and m so that they satisfy both requirements?

Fact: If m is prime and b ∈ {2,...,m-1}, then R₂ satisfies both requirements.

We know this is true because in this case, R is a permutation, so it satisfies Requirement 1. Furthermore, element v₁ = b, so v is never the trivial sequence. Thus, Requirement 2 is satisfied.

Exercise: What are some drawbacks (or unresolved issues) with building random sequences by choosing a prime m and some b ∈ {2,...,m-1}?

Generating and detecting prime numbers

Many applications require the generation of new primes. We saw a simple example above in which generating new random sequences required the generation of new primes. Another important class of applications with this requirement are cryptographic schemes and protocols. In this section, we consider the problem of generating prime numbers.

As you saw in Assignment 1, a straightforward algorithm that is guaranteed to generate new prime numbers is not necessarily efficient. In practice, most algorithms that need to generate large primes simply choose a range of of numbers and filter out non-primes using some efficient algorithm that does not provide an absolute guarantee that the numbers that remain are all prime. As long as it is not too likely that the generated number is not a prime, this may be sufficient.

Example: Suppose we want to generate a d-digit prime number (in decimal representation). The prime number theorem states that for a given N, the number of primes in the range {2,...,N} is about N/(ln(N)). We can roughly estimate the number of primes with d-digit decimal representations using the following formula:

(10d+1-1 / ln(10d+1-1)) - (10d / ln(10d))

For d = 8, this value is about 4,780,406, so we can roughly say that the chances that a chosen 8-digit number is prime are about:

4,780,406/((109 - 1) - 108) ≈ 5.5/100

Suppose we defined the following algorithm for generating a prime with a d-digit representation.

1. inputs: d ∈ N
2. do
   1. n := a number from {10^d, ..., 10^d+1-1}
   while n is not prime
3. return n

Assuming we were choosing numbers "well" with respect to their distribution (we are being imprecise here), we could optimistically hope that for d = 8, the above algorithm would only need to check for primality about 20 times (since roughly 1 out of every 20 numbers it tries should be a prime).

It remains to define an algorithm for checking whether an arbitrary input m ∈ N is prime. We could check every number k between 2 and ⌊ √(m) ⌋ to see if it is a factor of m. However, ⌊ √(m) ⌋ still grows exponentially in the representation size of m. For example, for an n-bit input, an integer m in {0,...,2ⁿ-1} which must have a representation size of at least n bits, we have the following exponential running time:

√(m)	=	√(2n)
	=	2n/2
	=	(21/2)n
	≈	1.42n

If we only consider primes and not any of their multiples (i.e., we apply the Sieve of Eratosthenes to the set {2,...,⌊ √(m) ⌋}), we can decrease the number of times we check the divisibility of m. However, we would need to do a lot of extra work to filter out the multiples of primes. Modern algorithms such as ECPP run in polynomial time, in practice it is currently difficult to implement a version of these algorithms that runs quickly enough for many applications. Thus, we instead modify our algorithm in the following way:

1. inputs: d ∈ N
2. do
   1. n := a number from {10^d, ..., 10^d+1-1}
   while n is not probably prime
3. return n

It remains to define a subroutine for checking whether a number is probably prime (for some appropriate definition of "probably") that is very efficient.

Greatest common divisor and related facts

To see why the recursive case works, consider two cases. If x < y, then the two inputs are simply reversed. This ensures that the first input x is eventually larger than the second input y. If x ≥ y and they share a greatest common divisor a, then we have for n = ⌊ x/y ⌋ that:

y	=	y' ⋅ a
x	=	x' ⋅ a
x mod y	=	x - (n ⋅ y)
	=	(x' ⋅ a) - (n ⋅ y)
	=	x' ⋅ a - ((n ⋅ y') ⋅ a)
	=	(x' - n ⋅ y') ⋅ a

Notice that (x' - n ⋅ y') ⋅ a < x' ⋅ a, but that the new smaller value is still a multiple of a, so the greatest common divisor of this value and y is still a.

The above can be proven by noticing that if gcd(a,m) = 1, then a does not divide m and m does not divide a. Notice that in the proof of this statement in which p was prime, the fact that it was prime was not used.

We prove the above by contradiction. Suppose there exists a factor z > 1 of m and m+1. In other words, gcd(m,m+1) > 1. Then we have that:

z ⋅ a	=	m
z ⋅ b	=	m+1
(z ⋅ b) - (z ⋅ a)	=	m+1-m
z ⋅ (b- a)	=	1
z ⋅ (b- a)	=	1/z

If z > 1 then 1/z ∉ Z, so (b - a) ∉ Z. Since b-a ∈ Z, this is a contradiction, so it must be that gcd(m,m+1) = z = 1.

Notice that the prime number generator in Assignment 1 relies on the above fact: for a product p of known prime numbers, it is guaranteed that p+1 shares no factors with p, so any prime factors it has must be new.

Testing whether a number is probably prime

In this section, we consider the problem of defining a very efficient algorithm to check whether a positive integer m ∈ N is prime. In fact, the algorithm we consider will be detectors of some, but not all, composite numbers.

That is, the algorithms we consider recognize prime numbers but with false positives. They only guarantee that there are no false negatives (i.e., if the algorithm outputs that its input is composite, then it is indeed composite; otherwise, the number may or may not be prime and we call it probably prime because we were not able to detect that it is composite). First, consider how an algorithm for checking primality that never has a "false" output behaves:

algorithm input	algorithm output	meaning	comment
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

Compare the above table to the following table describing three possible conditions (and one forbidden condition) for an algorithm that detects probably primes.

algorithm input	algorithm output	meaning	comment
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 such algorithms)

We now define our first algorithm for testing whether a number is probably prime.

1. inputs: m ∈ N, k ∈ N
2. repeat k times:
   1. a := a number from {2,...,m-1}
   2. if gcd(a,m) ≠ 1 then return composite
3. return probably prime

The above algorithm is somewhat problematic if we want to have a good idea of how to set k given our desired level of confidence in the output. For example, how high should k be so that the probability that we detect a composite is more than 1/2?

If we require that k ≈ √(m) to be sufficiently confident in the output, we might as well use the brute force method of checking every a ∈ {2,..., ⌊ √(m) ⌋}.

To define a more predictable testing approach for our algorithm, we derive a theorem that is frequently used in applications of modular arithmetic (in fact, this fact underlies the prime number generators found in many software applications).

We have already shown that if p is a prime then R defined as below is a permutation:

R	=	{ (1, (1 ⋅ a) mod p), (2, (2 ⋅ a) mod p), ..., (p-1, ((p-1) ⋅ a) mod p) }
	=	{ (i, (i ⋅ a) mod p) | i ∈ {1,...,p-1} }

Next, to make our notation more concise, note that:

1 ⋅ 2 ⋅ ... ⋅ p-1	=	(p - 1)!
(1 ⋅ a) ⋅ (2 ⋅ a) ⋅ ... ⋅ ((p-1) ⋅ a)	=	ap-1 (p - 1)!

Recall that p is prime, so p does not divide (p - 1)!. Thus, we can divide by (p - 1)! both sides of the following equation:

ap-1 (p - 1)!	≡	1 ⋅ (p - 1)!
ap-1	≡	1

We now have derived the statement of the theorem.

If we negate the statement above, we can define when a number is composite (i.e., when it is not prime) in a way that suggests a straightforward algorithm.

For any given candidate a in the above algorithm, if the first test fails and gcd(a,m) ≠ 1 then a is a factor of m. Thus, in the worst case, the first is gcd(a,m) = 1 for all k instances of a that we consider. How many of these k instances must pass the second test before we are confident that m is prime? In fact, for most composite numbers m, k can be very low.

Suppose that a is a Fermat witness and a₁,...,a_n are distinct Fermat liars. Then for every Fermat liar we have that:

(a ⋅ ai)n-1	≡	an-1 ⋅ ain-1
	≡	an-1

But a is a Fermat witness, so a^n-1 mod m ≠ 1. Thus, (a ⋅ a_i)^n-1 mod m ≠ 1, so a ⋅ a_i is also Fermat witness. Since there is a witness for every liar, there are at least as many witness as liars, so at least half the values are witnesses.

How many numbers m have at least one Fermat witness? Equivalently, how many numbers have no Fermat witnesses?

The distribuation of Carmichael numbers is high enough that the Fermat primality test is usually not used in favor of slightly more complex tests for probable primes. However, those tests follow a similar principle. The Fermat primality test is used in some deployed software applications (such as PGP).

for the chosen a we have...	what it means	probability of this occurring if m is a non-Carmichael composite
gcd(a,m) ≠ 1	m and a have a non-trivial factor, so m is composite	(# integers in {2,...,m-1} that share factors with m) / (m-2)
am-1 mod m ≠ 1	a is a Fermat witness that m is composite	at least 1/2

---

Assignment #2: Modular Arithmetic, Random Sequences, and Primes

For this assignment, you will submit a single Python source file a2.py.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts.

1. To receive credit for each part below, your solutions must employ forall, exists, and/or list comprehensions. Solutions that are more than 2-5 lines in length will receive no credit.
   1. Define a Python function commutative(op,S) that takes two arguments and returns True only if the first argument op, an operator that takes two arguments, is commutative on the finite set S.

      def commutative(op,S) :
        return forall(S, lambda x: forall(S, lambda y: op(x,y) == op(y,x)))

   2. Define a Python function associative(op,S) that takes two arguments and returns True only if the first argument op, an operator that takes two arguments, is associative on the finite set S.

      def associative(op,S) :
        return\
          forall(S, lambda x: forall(S, lambda y: forall(S, lambda z:\
            op(op(x,y),z) == op(x,op(y,z)))))

   3. Define a Python function identity(op,S) that takes two arguments and returns True only if the first argument op (which is itself a function that takes two arguments) has an identity element in S. Note that the identity must be both a left and right identity.

      # It is important to have the right order for the quantifiers.
      # There must exist at least one identity element that behaves
      # like the identity for /all/ the elements of S:
      #
      #   exists i in S s.t. for all x in S, op(x,i) == op(i,x) == x
      #
      # Notice that this is different from a statement such as the one
      # below:
      #
      #   for all x in S, exists i in S s.t. op(x,i) == op(i,x) == x # Incorrect.
      #
       
      def identity(op,S) :
        return exists(S, lambda i: forall(S, lambda x: op(x,i) == op(i,x) == x))

   4. Define a Python function inverses(op,S) that takes two arguments and returns True only if for every element in S, there is an inverse element with respect to op. Note that this is only possible if there is an identity with respect to op. You may want to write a few helper functions in order to avoid deeply-nested quantifiers.

      # The following is the correct formula:
      #
      #   there exists i in S s.t.
      #       i is an identity for S
      #     and
      #       for all x in S, exists y in S s.t. op(x,y) == i
      #
      # However, equivalents of the following will also be
      # accepted:
      #
      #   for all x in S, exists y in S s.t.
      #     op(x,y) == i and i is an identity for S
      #
      # For either of the above, "i is an identity for S" should
      # be a formula equivalent to:
      #
      #   for all x in S, op(x,i) == op(i,x) == x
      #
      # Since we did not explicitly specify whether the identity
      # must be left- or right-, "op(x,i) == x" or "x == op(x,i)"
      # alone would be sufficient.
       
      def inverses(op,S) :
        return\
          exists(S, lambda i:\
              #i is an identity
              forall(S, lambda x: op(i,x) == op(x,i) == x)\
            and\
              forall(S, lambda x: exists(S, lambda y: op(x,y) == i)))

2. 1. Define a Python function randFromPrime() that takes a single input p, a prime number, and generates a set of p distinct lists, each of length p, and each being a "random" reording of the list [ i for i in range(0,p) ].
      • Each list must contain p distinct integers from the set { i for i in range(0,p) }.
      • No individual list should be an ascending or descending sequence of the integers from { i for i in range(0,p) }.
   2. Define a Python function rand() that takes a single input n (which might not be prime) and generates a set of n distinct lists, each of length n, and each being a "random" reording of the list [ i for i in range(0,n) ].
      • Each list must contain n distinct integers from the set { i for i in range(0,n) }.
      • No individual list should be an ascending or descending sequence of the integers from { i for i in range(0,n) }.
      You may find the following points useful:
      • Implement the gcd function.
      • Recall the fact that if gcd(a,m) = 1, then {(i, (i ⋅ a) mod m) | i ∈ {0,...,m-1}} is a permutation. Implement an algorithm that finds a suitable a quickly for a given m (think about how you can use the gcd function to accomplish this).
      • Python provides a built-in function floor(). To use it, add from math import floor to the top of your file.
   3. Extra credit: Define a Python function randExtra() that takes a single input n (which might not be prime) and generates a set of n*n distinct lists, each of length n, and each being a "random" reording of the list [ i for i in range(0,n) ].
      • Each list must contain n distinct integers from the set { i for i in range(0,n) }.
      • No individual list should be an ascending or descending sequence of the integers from { i for i in range(0,n) }.
3. 1. Define a Python function randByIndex() that takes two inputs n and i. It should return the ith element in a "random" sequence of length n that contains every number in the set { k for k in range(0,n) }. You should not generate the whole list of length n in memory.
4. 1. Define a Python function generatePrime() that takes a single input d and generates a d-digit (in base 10) probable prime. Your algorithm should be efficient enough to fairly quickly generate a 1000-digit probable prime, and should not run out of memory (although it may take quite some time) when generating a 10000-digit probable prime.
      • Make use of your solution from Problem #3 above.
      • Define a separate helper function probablePrime() that checks if its input is a probable prime.
      • Python provides a built-in function pow(a,b,m) that efficiently computes a^b mod m.
      • For the purposes of this assignment, you need not handle Carmichael numbers in any special way that avoids the high likelihood that they are categorized as probably prime. Thus, you may use the Fermat primality test.

---

Chinese remainder theorem and applications

Example: Suppose we want to perform a large number of arithmetic operations in sequence (e.g., 2²⁰⁴⁸ operations). However, we know that the final result of the computation will be less than 2²⁵⁶. Since there are 2²⁰⁴⁸ operations, half of these may be addition by 1, and half may be subtraction by 1. In that case, the maximum value at any given moment will be 2²⁰⁴⁷. How many bits of working memory do we need to perform all the operations in sequence to obtain the final result?

Choose p₁,...,p₃₂ such that for all i ∈ {1,...,32}, 2⁸ < p_i < 2¹⁶. Notice that

p1 ⋅ ... ⋅ p32	>	28 ⋅ ... ⋅ 28
	>	28 ⋅ 32
	>	2256

However, since p_i < 2¹⁶ for all i, we only need 32 ⋅ 2¹⁶ = 2²¹ bits to represent any single point in the computation. Once we obtain the results a₁,...,a₃₂, we can apply the Chinese remainder theorem to obtain x. Since the product of the primes is greater than 2²⁵⁶, the value x will be the result of the computation.

Example (variant of range ambiguity resolution): Suppose we want to build a radar or other sensing device that sends signals out and listens for reflections of those signals in order to detect the distances of obstacles in the environment. The device has a clock that counts up from 0, one integer per second. If the device sends a single signal out that travels at 1 km per second at time 0 and receives a response in 12 seconds at time 12, it knows that the distance to the object and back is 12 km.

However, what if we cannot wait 12 seconds or more? For example, the obstacle may be moving quickly and we want to constantly update our best guess of the distance to that object. We would need to send signals more frequently (for example, every 5 seconds). But then if an object is 12 seconds away, we would have no way to tell when running in a steady state which of the signals we just received.

However, we can obtain some information in this scenario. Suppose we send a signal every 5 seconds, only when the clock's timer is at a multiple of 5. Equivalently, imagine the clock counts up modulo 5 (i.e., 0,1,2,3,4,0,1,2,3,4,0,...) and we only send signals when the clock is at 0. What information can we learn about the object's distance in this scenario? If the distance to the object and back is d, then we would learn d mod 5, because we would get the signal back when the clock is at 0, 1, 2, 3, or 4.

We can use multiple instances of the above device (each device using its own distinct frequency for sending signals) to build a device that can check for obstacles more frequently while not giving up too much accuracy. Pick a collection of primes p₁,..., p_n such that their product is greater than the distance to any possible obstacle (e.g., if this is a ship or plane, we could derive this by considering the line of sight and the Earth's curvature). Take n instances of the above devices, each with their own clock that counts in cycles through Z/p_iZ and sends out a signal when the clock is at 0. Running in a steady state, if at any point in time the known offsets are a₁,...,a_n, we would know the following about the distance d to an obstacle:

d	≡	a1 (mod p1)
	⋮
d	≡	an (mod pn)

We can then use the Chinese remainder theorem to derive the actual distance d < p₁ ⋅ ... ⋅ p_n.

Example (Shamir secret sharing): Suppose there are N participants and we want to divide some secret information among them into N parts so that any k or greater number of participants can reconstruct the secret information, but no subset of fewer than k participants can reconstruct it. Let s ∈ Z be the secret information.

Collect a set of randomly chosen relatively prime integers M = {m₁,...,m_N} such that:

• the product of any collection of at least k integers in M is greater than s;
• the product of any collection of k-1 integers in M is less than s.

Give each participant i ∈ {1,...,N} the value s mod m_i. Now, any number of participants n ≥ k can use the Chinese remainder theorem to solve for s.

Note: There are many alternative ways to implement Shamir secret sharing. Consider the following example using curve-fitting. We choose some large m ∈ Z, and then randomly select integers c₁,...,c_k ∈ Z/mZ. We then use these integers as coefficients in a polynomial:

f(x)

=

s + c1 x + c2 x2 + ... + ck xk

Each participant i ∈ {1,...,N} is given f(i). Any k participants can now use curve-fitting techniques or techniques for solving collections of equations (e.g., computing the reduced row echelon form of a matrix) to determine all the coefficients of f and, thus, solve for s.

We can check that the above is indeed a solution to x ≡ a (mod m). Consider the following:

u ⋅ m + v ⋅ n	=	1
v ⋅ n	=	1 - u ⋅ m
v ⋅ n	≡	1 (mod m)

Furthermore, we have that:

((u ⋅ m) ⋅ b) mod m

=

0

Then, we can conclude:

((u ⋅ m) ⋅ b + (v ⋅ n) ⋅ a) mod m	=	0 + ((v ⋅ n) ⋅ a) mod m
	=	0 + (1 ⋅ a) mod m
	=	a mod m

Using a similar argument, we can show that the solution is also equivalent to b (mod m).

Euler's totient function, multiplicative inverses in Z/mZ, and applications

Unfortunately, Euler's totient function does not in general have a better upper bound than f(m) = m.

Notice that if m is a prime number, then φ(m) = m-1. Then for any a ∈ Z/mZ, gcd(a,m) = 1 and a^m-1 mod m = 1. This is exactly the statement of Fermat's little theorem. Thus, Euler's theorem is a generalization of Fermat's little theorem.

We saw above that there is a simple closed formula for computing an additive inverse of an element a ∈ Z/mZ: m-a. In Q (the set of rational numbers), computing the multiplicative inverse a ^-1 is straightforward: the inverse of an integer a ∈ Q is 1/a. Is there a way to compute a ^-1 ∈ Z/mZ if it exists?

The above encryption-decryption process works because for some k ∈ Z:

e ⋅ d	≡	1 (mod φ(n))
	=	1 + φ(n) ⋅ k
(me)d mod n	=	(m1 + φ(n) ⋅ k) mod n
	=	(m ⋅ (mφ(n) ⋅ k)) mod n
	=	(m ⋅ (mφ(n) ⋅ k)) mod n
	=	(m ⋅ mφ(n)) mod n
	=	(m ⋅ 1) mod n
	=	m mod n

Besides the message m, there are three pieces of secret information that an eavesdropper cannot know in order for the encryption to provide any privacy:

• p and q
• φ(n)
• d = e ^-1

Notice that if an eavesdropper knows p and q where n = p ⋅ q, the eavesdropper can easily compute φ(n) (which was supposed to be private). If the eavesdropper can compute φ(n), then they can use the extended Euclidean algorithm to compute the inverse d = e ^-1 of the public key value e. They can then use d to decrypt messages.

Suppose the eavesdropper only knows φ(n). Then the eavesdropper can compute d and decrypt any message. Can the eavesdropper also recover p and q?

---

Assignment #3: CRT, Totient Function, Inverses, and Applications

For this assignment, you will submit a single Python source file a3.py.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts.

1. 1. Define a Python function egcd() that takes two integer inputs x and y and returns a tuple of two integers (s,t) that satisfies the following property:
      • s * x + t * y == gcd(x,y)
   2. Define a Python function inverse() that takes two integer inputs x and m and returns the multiplicative inverse of x in Z/mZ if it exists, or returns None if it does not.
2. 1. Define a Python function CRT2() that takes two inputs, each of which is a pair of integers. Each of the two pairs of integers, call them (a,m) and (b,n), represents one of the equations in the system of equations below:

      x	≡	a (mod m)
      x	≡	b (mod n)

      You should assume m and n are coprime. The function should return a single integer x ∈ Z/(m ⋅ n)Z that is the solution to the two equations above.
   2. Define a Python function CRTN() that takes one input, which is a list of pairs, each of which is of the form (a,m). Each of the pairs in the list represents a distinct equation in the system of equations below:

      x1	≡	a1 (mod m1)
      	⋮
      xk	≡	ak (mod mk)

      You should assume that for every i, j ∈ {1,...,k} where i ≠ j, m_i and m_j are coprime. The function should return a single integer x ∈ Z/(m₁ ⋅ ... ⋅ m_k)Z that is the solution to the system of equations above.
3. 1. Define a very efficient Python function pow2ModPrime() that takes four integer inputs x, y, z, and p. This function always assumes that p is prime (it need not return a correct output if p is not prime, and it should not check whether p is prime). The function should return the result of the computation:

      xyz mod p

      Your implementation may employ the built-in Python function pow(), which takes three inputs a, b, and m and returns a^b mod m. However, your function must be able to handle very large inputs. For example:

         pow2ModPrime(3,3,1000000000000000000000,84199) # Should return 42526 quickly.
         pow(3,pow(3,1000000000000000000000),84199)     # Should be much slower than the above.
      

      Hint: consider the way Euler's theorem and the totient function φ are used in the RSA cryptographic protocol.
   2. Define a very efficient Python function diffPows() that takes three inputs: two integer inputs x and y and a list of distinct primes ps. Let P be the product of the primes in ps. The function should return an output equivalent to:

      (33x - 22y) mod P

      Your function must be able to handle very large inputs. For example:

         primes =[\
               15481619,15481633,15481657,15481663,15481727,15481733,15481769,15481787 
              ,15481793,15481801,15481819,15481859,15481871,15481897,15481901,15481933 
              ,15481981,15481993,15481997,15482011,15482023,15482029,15482119,15482123 
              ,15482149,15482153,15482161,15482167,15482177,15482219,15482231,15482263 
              ,15482309,15482323,15482329,15482333,15482347,15482371,15482377,15482387 
              ,15482419,15482431,15482437,15482447,15482449,15482459,15482477,15482479 
              ,15482531,15482567,15482569,15482573,15482581,15482627,15482633,15482639 
              ,15482669,15482681,15482683,15482711,15482729,15482743,15482771,15482773 
              ,15482783,15482807,15482809,15482827,15482851,15482861,15482893,15482911 
              ,15482917,15482923,15482941,15482947,15482977,15482993,15483023,15483029 
              ,15483067,15483077,15483079,15483089,15483101,15483103,15483121,15483151 
              ,15483161,15483211,15483253,15483317,15483331,15483337,15483343,15483359 
              ,15483383,15483409,15483449,15483491,15483493,15483511,15483521,15483553 
              ,15483557,15483571,15483581,15483619,15483631,15483641,15483653,15483659 
              ,15483683,15483697,15483701,15483703,15483707,15483731,15483737,15483749 
              ,15483799,15483817,15483829,15483833,15483857,15483869,15483907,15483971 
              ,15483977,15483983,15483989,15483997,15484033,15484039,15484061,15484087 
              ,15484099,15484123,15484141,15484153,15484187,15484199,15484201,15484211 
              ,15484219,15484223,15484243,15484247,15484279,15484333,15484363,15484387 
              ,15484393,15484409,15484421,15484453,15484457,15484459,15484471,15484489 
              ,15484517,15484519,15484549,15484559,15484591,15484627,15484631,15484643 
              ,15484661,15484697,15484709,15484723,15484769,15484771,15484783,15484817 
              ,15484823,15484873,15484877,15484879,15484901,15484919,15484939,15484951 
              ,15484961,15484999,15485039,15485053,15485059,15485077,15485083,15485143 
              ,15485161,15485179,15485191,15485221,15485243,15485251,15485257,15485273 
              ,15485287,15485291,15485293,15485299,15485311,15485321,15485339,15485341 
              ,15485357,15485363,15485383,15485389,15485401,15485411,15485429,15485441 
              ,15485447,15485471,15485473,15485497,15485537,15485539,15485543,15485549 
              ,15485557,15485567,15485581,15485609,15485611,15485621,15485651,15485653 
              ,15485669,15485677,15485689,15485711,15485737,15485747,15485761,15485773 
              ,15485783,15485801,15485807,15485837,15485843,15485849,15485857,15485863]
              
         # The code below should take at most a second or two to evaluate.
         diffPows(100000000000000000000, 100000000000000000000, primes)
         
         # The output of the above should be:
         1014583418021155147669596086281029838529720782206361091583595823689719157476532284
         8987189887167799660866466205679182087923947730758196605113875528351517618438642265
         3581039473366623112437577201358820794341439719440271391920116932817847656116153368
         7265432104820323843042836554017993078689112459259244886127618081567160190817432495
         2143410149340178452973885327762236756547669499168330784109081344938468727993713195
         3169678339499877031537565519050932012817516387739533522394516718093516017690196562
         7101427207866265547550708480269630690614590278546972352636005909708527043821426318
         4521095281729009794902244831649627645067744531132354275086194660115820734317391275
         9128112857042672881445685539242864388276070829222553398880738035689262514826688173
         6913562704802954300877406726543052076808476120620371564427614984332631535660033277
         8189204900085569366429138226629079794533371458002969316578012640171885098224952913
         3491159071950682951158132515447103910101337602328824428482135061810959708064341298
         2041798901080878626343050467586243536238154444445605344046612862002597217912264786
         0824335665138449552625836001208039714421654922433127769977323976312559879889522757
         1709222772581924582016690799105293131715244224202006451140406716336817962814141853
         2115825675072522109019428377974687020928180075572057614974579410052738475293483072
         3761795114940096414122259399758778638409278794055719938284333607939097874832982043
         1353079076167862532446907487602733400201159484031421148157283172670287937374484685
         4508879443653756784061411297770071775372502147954692284657158826404250380999506744
         2785210787255712896681508731293497639546329245604994768139819393571953247354217371
         7900740573848181518094539324832238278064519569345203659830437641031472046598369915
         89585651957609932891856423136539428409811645597728586100980931
      

4. In this problem you will implement the three component algorithms of the RSA cryptographic protocol described in lecture.
   1. Define a Python function generate() 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).
      • Your algorithm does not need to be efficient, but it should always be correct.
   2. Define a Python function encrypt() that takes two inputs: an integer m and a tuple (n,e). It should return a single integer: the ciphertext c.
   3. Define a Python function decrypt() that takes two inputs: an integer c representing the ciphertext and a pair of integers (n,d) representing the private key. It should decrypt c and return the original message m.

---

Complexity of Modular Arithmetic Algorithms

Complexity of (probably) intractable problems

Below, we review a small set of definitions and facts from complexity theory. We will only use these facts as they relate to problems in modular arithmetic and abstract algebra. A course on computational complexity theory would go into more detail.

Informally, for some formula F, we call a statement of the following form a problem:

• "Given X, find Y such that F(X, Y) is true."

In the above, X can be viewed as the input describing the problem, and Y can be viewed as the solution to the problem.

The complexity of a problem refers to the running time of the most efficient algorithm that solves the problem.

The above fact (i.e., that if factoring n is not in P, then neither is computing φ(n)) holds for arbitrary n, not just a product of two primes. However, the proofs in those cases are more sophisticated [Shoup].

In fact, there may exist more than two roots of a value in Z/nZ.

Let us consider the problem of finding all of the square roots of a member of Z/nZ. Notice that this problem is analogous to computing all the square roots of y in Z/nZ:

√(y)

=

± x

This problem is believed to be computationally difficult.

Suppose that for a prime p, we can solve the congruent squares problem efficiently (in fact, we have such algorithms for p ≡ 3, p ≡ 5, and p ≡ 7 in Z/8Z, but for primes where p ≡ 1 (mod 8), no efficient algorithm is known). Then we can use the Chinese remainder theorem to solve the congruent squares problem for n = p ⋅ q where p and q are prime.

Above, we have shown that several problems are not in P. There is another complexity class to which they definitely belong.

It is not known whether the discrete logarithm problem is related to the factoring problem. Factoring can be reduced using a probabilistic approach to the discrete logarithm problem modulo p ⋅ q.

The following diagram summarizes the relationships between the problems that are conjectured to be intractable (i.e., not in P). Each directed edge represents that there exists a polynomial-time reduction from the source problem to the destination problem. All of the nodes in the graph are conjectured to be not in P.

Complexity of algorithms for solving tractable problems

In this subsection we consider the complexity of efficient algorithms for performing common arithmetic operations. We consider the complexity of arithmetic operations on each of the following domains:

• unbounded positive integers;
• integers modulo 2ⁿ;
• integers modulo k for some k ∈ N.

All of our arithmetic algorithms will operate on bit string representations of positive integers. A bit string representation such as

an-1...a0

is defined to represent the integer

20 ⋅ a0 + ... + 2n-1 ⋅ an-1

Since the operations we consider usually take two arguments, we will follow the following conventions:

• the first (left-hand side) input is x, an n-bit integer;
• the second (right-hand side) input is y, an m-bit integer.

Thus, x ≤ 2ⁿ - 1 and y ≤ 2^m - 1.

When we consider the operations above as operating on integers modulo 2ⁿ (with results also in 2ⁿ, this corresponds to simply dropping any bits beyond the n least-significant bits when performing the computation.

To see the above, consider the following fact: for any a ∈ N, b ∈ N, if b ≤ a then a mod b < (1/2) ⋅ a. Consider the two possibilities for a and b:

• if b ≤ (1/2) ⋅ a, then ⌊ a / b ⌋ > 1, so:

  (a mod b)

  <

  b

  ≤

  (1/2) ⋅ a

• if b > (1/2) ⋅ a, then ⌊ a / b ⌋ = 1, so:

  a mod b	=	a - ⌊ a/b ⌋ ⋅ b
  	=	a - 1 ⋅ b
  	=	a - b
  	<	a - ((1/2) ⋅ a)
  	<	(1/2) ⋅ a

Thus, every time a mod b is computed in the algorithms, size of the second paramter is halved. Since every other invocation switches the two parameters, both parameters are halved. Thus, the number of invocations or iterations for an input m is log(m).

---

Assignment #4: Reductions, Quadratic Residues, and Review

For this assignment, you will submit a single Python source file a4.py. You may include answers to the written problems inside a comment block at the beginning of the file (e.g., using ''' This is a comment. ''').

For the written problems #1-5, you may NOT use a programming language or calculator, and you must show your work. When making a claim in an argument, you should reference the fact you are applying.

For the programming problems #6-7, your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. You may reuse functions that you defined on previous assignments.

1. 1. Suppose the following set S and relation R on S are defined:

      S	=	{0,1,2,3,4,5,6,7}
      R	=	{(0,0),(1,1),(1,7),(7,1),(2,2),(2,4),(4,2),(3,3),(4,3),(3,4),(2,3),(3,2),(4,4),(5,5),(6,6),(7,7)}

      Define explicitly the quotient set S/R.
      Since R is reflexive, symmetric, and transitive, it is an equivalence relation. Thus, we can divide S into a collection of subsets of S so that the members of each subset of mutually equivalent according to R.
      
      Thus, we have S/R = {{0}, {1, 7}, {2, 3, 4}, {5}, {6}}.
   2. Let n ∈ N and a ∈ Z/nZ. Suppose that gcd(a,n) = 1. Determine the exact size of the following set:

      { a ⋅ i mod n | i ∈ {0,...,n-1} }

      We know that the above set is a permutation of {0,...,n-1}, so the size is n.
   3. Let n ∈ N and a ∈ Z/nZ. Suppose that gcd(a,n) = 1. Determine the exact size of the following set:

      { i ⋅ (aφ(n)) mod n | i ∈ {0,...,n-1} }

      We know by Euler's theorem that a^φ(n) mod n = 1 since a and n are coprime. Thus, the size of the set is n, since this is exactly the set {0,...,n-1}.
   4. Let p ∈ N be a prime number. Determine the exact size of the following set:

      { aφ(p) mod p | a ∈ {1,...,p-1} }

      We know by Euler's theorem that a^φ(p) mod p = 1 if a and p are coprime. Thus, the size of the set is 1.
2. Find the multiplicative inverse of each of the following if it exists, or explain why it does not exist (the solution may be a formula in terms of the variables in the expression).
   1. 2 ∈ Z/5Z
   2. 3 ∈ Z/10Z
   3. 5 ∈ Z/21Z
   4. (2 ⋅ 3) ∈ Z/11Z
   5. 6 ∈ Z/7Z
   6. (3 ⋅ b) ∈ Z/(a ⋅ b)Z
   7. a ∈ Z/(a+1)Z
   8. (a ⋅ b) ∈ Z/((a ⋅ b)-1)Z
   1. 2^φ(5)-1 mod 5   =   2³ mod 5   =   8 mod 5 = 3
   2. 3^φ(10)-1 mod 10   =   3^{((5-1)⋅(2-1))-1} mod 10   =   3³ mod 10 = 7
   3. Using the formula for inverses in terms of φ:

      5φ(21)-1 mod 21	=	5((7-1)⋅(3-1))-1 mod 21
      	=	511 mod 21
      	=	5 ⋅ (52)5 mod 21
      	=	5 ⋅ (4)5 mod 21
      	=	5 ⋅ 4 ⋅ (22)4 mod 21
      	=	20 ⋅ (28) mod 21
      	=	20 ⋅ 256 mod 21
      	=	20 ⋅ 4 mod 21
      	=	80 mod 21
      	=	17 mod 21

   4. For purposes of illustration, we solve this by finding the inverses of the components, then multiplying:

      2 ⋅ 6	≡	12	≡	1 mod 11
      3 ⋅ 4	≡	12	≡	1 mod 11

      (2 ⋅ 3) -1	≡	6 ⋅ 4
      	≡	24
      	≡	2 (mod 11)

   5. 6 ∈ Z/7Z, since 6 ⋅ 6 = 36 ≡ 1 (mod 7)
   6. If b > 1, then there is no inverse, since gcd(3 ⋅ b, a ⋅ b) ≥ b. If b = 1, then the inverse is (3 ⋅ b)^φ(a⋅b)-1 mod (a ⋅ b). Either or both of these answers are acceptable.
   7. We know that gcd(a, a+1) = 1. Thus, we can find s and t that satisfy Bézout's identity:

      s ⋅ a + t ⋅ (a + 1)	=	gcd(a, a+1)
      (-1) ⋅ a + (1) ⋅ (a + 1)	=	1
      s	=	-1
      t	=	1

      But (s,t) is the output of the extended Euclidean algorithm, and if the greatest common divisor is 1, then s is the multiplicative inverse of the first argument modulo the second argument, which is a in this case. Thus, -1 ∈ Z/(a+1)Z, or (a+1)-1 = a, is the multiplicative inverse of a in Z/(a+1)Z. Alternatively, a ^-1 ≡ a^φ(a+1)-1 mod (a+1). Either or both of these answers are acceptable.
   8. We know that (a ⋅ b) ≡ 1 (mod ((a ⋅ b) - 1)). Thus, the inverse is 1 ∈ Z/((a ⋅ b) - 1)Z.
3. Compute each of the following.
   1. 11¹⁰²⁵ mod 17
      Since 11 and 17 are coprime, we have that 11¹⁰²⁵ ≡ 11^{1025 mod φ(17)}. Then, we have that:

      1025 mod φ(17)	≡	1025 (mod 16)
      	≡	(210 + 1) (mod 24)
      	≡	1 (mod 24)
      111025	≡	111 (mod 17)
      	≡	11 (mod 17)

   2. 2^(2100000001) mod 7
      Since gcd(2,7) = 1, we can compute 2^100000001 mod φ(7) to make the exponent more manageable. We know that the powers of 2 modulo 6 are 2,4,2,4,2,4,2,4,... Thus, since 100000001 is odd, we have:

      2100000001	≡	21 (mod 6)
      2(2100000001)	≡	2(21) (mod 7)
      	≡	4 (mod 7)

   3. { x | x ∈ Z/17Z, x² ≡ 16 mod 17 }
      Since 17 is prime, we know there are at most two solutions. Since 16 < 17, we know that they are 4 and -4 = 17-4 = 13. Thus, this set is {4, 13}.
   4. { x | x ∈ Z/10Z, x² ≡ 9 mod 10 }
      The two obvious solutions to the equation x² ≡ 9 (mod 10) are 3 and -3 = 10-3 = 7. However, there may be as many as four solutions since 10 = 2 ⋅ 5.
      
      In Z/2Z, 9 ≡ 1. The two solutions in Z/2Z are thus 1 and -1. However, since -1 = 2-1 = 1, there is only one solution in Z/2Z.
      
      In Z/5Z, 9 ≡ 4, and the two solutions are 2 and -2 = 5-2 = 3. Thus, there are two distinct systems of equations that can be set up, so there are two distinct solutions x₁ and x₂:

      x1	≡	1 (mod 2)
      x1	≡	2 (mod 5)

      x2	≡	1 (mod 2)
      x2	≡	3 (mod 5)

      The two solutions are still 3 and 7. Thus, the set is {3,7}.
   5. |{ x | x² ≡ 4 mod (7 ⋅ 23 ⋅ 31 ⋅ 59) }|
      We know that 2 and -2 are solutions to x² ≡ 4 in Z/7Z, Z/23Z, Z/31Z, and Z/59Z because these moduli are greater than 4. Thus, there are 2⁴ possible distinct systems of equations for which we can use CRT to find solutions. Thus, there are 2⁴ = 16 solutions, so the size of this set is 16.
   6. (Z/6Z)*
      Using the definition, we have that:

      (Z/6Z)*	=	{x | x ∈ Z/6Z, x -1 ∈ Z/6Z}
      	=	{x | x ∈ Z/6Z, gcd(x,6) = 1}
      	=	{1, 5}

4. At some point in the past, Alice used Bob's public RSA key (n,e) to send him several encrypted messages. Bob stored the encrypted versions of these messages without decrypting them. Some time later, Bob decides to read the messages. However, he discovers he has misplaced his public key (n,e), his private key d, and one of his primes p; he only knows q and φ(n) (he cannot ask anyone else for the lost information). Can Bob find a way to recover some or all of the lost information and read Alice's old messages? Explain in detail.
   Bob can use q and φ(n) to recover p, since:

   φ(n)	=	(p-1) ⋅ (q-1)
   p	=	(φ(n)/(q-1)) + 1

   However, e was chosen at random from (Z/φ(n)Z)*, and p and q do not help in reproducing it. Thus, even though Bob could compute d for a given e, e cannot be recovered, so Bob cannot recover the lost information.
5. Suppose that an efficient algorithm has been discovered for computing discrete logarithms modulo primes. That is, given some value g^a mod p, it is now possible to efficiently compute a if g is known (i.e., log_g (g^a) ≡ a). Assuming that no other discoveries have been made, explain how Alice and Bob can (possibly using some other method, not necessarily D-H) still securely agree on a shared secret integer s ∈ Z without meeting in person. You must explain why this alternate method is still secure despite the new discovery.
   Because none of the other problems we considered (factoring, computing φ, congruent squares, and the RSA problem) have any known polynomial-time reductions to the discrete logarithm problem, the existence of an efficient algorithm for computing discrete logarithms does not imply an efficient solution for any of the other problems. Thus, it is no more risky than before to assume that cryptographic protocols such as RSA are secure.
   
   Bob and Alice could use the RSA or Rabin cryptographic protocol. For example, Alice chooses a secret, and Bob generates a public RSA key. Alice then encrypts and sends the secret value to Bob. Bob decrypts that secret value. At this point, Alice and Bob share a secret that no one else knows (assuming RSA is secure).
6. Consider the following problem (call it "φ-four"): "given an integer n that is the product of four distinct primes, find φ(n)." Notice that the four distinct primes are not known in the specification of the problem. It is only known that n is the product of some four distinct primes.
   1. Given our assumptions about the intractability of various problems (i.e., that certain problems are not in P), you must show that φ-four is also not in P. To do so, you must implement a solver for some existing intractable problem that uses a solver for φ-four (call it phi_four()) as a subroutine. The algorithm you implement must represent a polynomial-time reduction to φ-four from the intractable problem you choose. Note: remember that the four primes must be distinct; your reduction must work for all possible instances of the intractable problem.
   2. Suppose that we discover an efficient algorithm getFactor() that takes a single integer input and returns exactly one prime factor of its input. Implement a Python function that solves φ-four efficiently by calling getFactor() as a subroutine.
7. Implement a Python function roots() that takes two arguments: an integer y as its first argument, and a list of primes as its second argument. You may assume that all the primes p are such that p ≡ 3 mod 4. Let P be the product of all the primes in the list. The function should return a set of all the distinct square roots of y² in Z/PZ. Your implementation must be efficient (i.e., it may not iterate over all possible values in Z/PZ to look for square roots).

---

Review #1

This section contains a comprehensive collection of review problems going over the course material covered until this point. These problems are an accurate representation of the kinds of problems you may see on an exam.

---

Algebraic Structures

In this section we present the definitions for common algebraic structures frequently encountered in computer science. We identify what properties these structures do and do not share with Z/nZ, and generalize many of the definitions and results we have seen when studying modular arithmetic to these algebraic structures.

Algebraic Structures and Axioms

We define several common algebraic structures. These structures are all sets that are closed under a binary operator. They are distinguished by what other common axioms the set and operator satisfy.

Notice that if a set S is finite, there is a natural way to algorithmically list all elements in closure(S, ⊕) by starting with the elements in S and "building up" all the elements in each of the closure_i(S, ⊕) subsets.

Any of the above terms can be prefixed with free to indicate that no other axioms apply.

Any of the above terms can be prefixed with finite to indicate that A is finite. The set of generators of an algebraic structure may be finite or infinite.

Any of the above terms can be prefixed with commutative to indicate that the operator is commutative over the set.

Typically, we call a commutative group an abelian group.

Implementations of Algebraic Structures and Operations

The properties of an algebraic structure (i.e., associativity, identity, commutativity, and so on) influence how we can store individual elements in these structures, and how we can implement algorithms that perform operations over those elements.

The following table lists the correspondences between the parts of an algebraic structure and how they might correspond to a concrete data structure.

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

Suppose a concrete data structure corresponds to an algebraic structure with certain properties. The following table summarizes how those properties can inform or constrain implementations of algorithms or applications that operate on the concrete data sttructure.

	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	run-length 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

Group of all permutations (symmetric group)

Recall that a permutation on a set X is a bijective relation between X and X. Since a permutation is a map (i.e., a function), we can reason about composition of permutations (it is just the composition of functions). Thus, we can study sets of permutations as algebraic structures under the composition operation o.

Notice that for any set X of finite size n, we can relabel the elements of X to be {0,...,n-1} (that is, we can define a bijection between X and {0,...,n-1}). Thus, we can study permutations on {0,...,n-1} without loss of generality.

Groups of circular shift permutations (cyclic groups)

---

Assignment #5: Algebraic Structures and Permutations

For this assignment, you will submit a single Python source file a5.py.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts. You may reuse functions that you defined on previous assignments.

1. Suppose that we decide to represent permutations as lists of integers, such as [2,1,0]. For example, given some ordered list of elements such as ['a','b','c'], after the permutation [2,1,0] is applied:
   • the element 'a'with index 0 in ['a','b','c'] should move to the location with index 2 in the result;
   • the element 'b'with index 1 in ['a','b','c'] should move to the location with index 1 in the result;
   • the element 'c'with index 2 in ['a','b','c'] should move to the location with index 0.
   1. Implement a function permute() that takes two arguments: a list a of length n and a permutation p on n elements. It should return the permuted list. For example:

      permute(['a','b','c'], [2,1,0]) # Should evaluate to ['c','b','a'].

   2. Implement a function compose() that takes two permutations p1 and p2, both of the same length, and returns a single permutation that is the composition of those two permutations. That is, it returns a permutation p3 that, when applied to a list, will produce the same result as applying the first permutation to the second permutation:

      # Should be "True" for any inputs if they are all of the same length.
      permute(a, compose(p1,p2)) == permute(permute(a, p1), p2)

   3. Implement a function composeList() that takes as its one input a list of permutations, and returns a single permutation that is the result of composing the permutations in the list (according to the order they appear in the list).

   4. Recall that for the set of permutations on n elements, the generating set can be the set of permutations that swap only two elements. Implement a function generators() that takes a single positive integer argument n and returns the set of generators for the set of permutations on n elements. An example is provided below.

      generators(4) # Should return {[1,0,2,3], [0,2,1,3], [0,1,3,2]}.
      generators(5) # Should return {[1,0,2,3,4], [0,2,1,3,4], [0,1,3,2,4], [0,1,2,4,3]}.

   5. Implement a function factor() that takes a single permutation on n elements as an input and returns a list of generating permutations that can be composed to reconstruct it:

      # Should be "True" for any permutation "p".
      composeList(factor(p)) == p

      See this fact about sorting algorithms for one approach that can be used to implement factor().

      # Part (e).
      def factor(p):
          # If the permutation is the identity, return a list containing two
          # instances of the same transposition.
          if list(p) == list(range(len(p))):
              transposition = list(p)
              transposition[0:2] = [1, 0]
              return [transposition, transposition]
          factors = []
          for i in range(0, len(p)):
              if p[i] != i:
                  for j in range(0, len(p)):
                      if p[j] == i:
                          factors = factors + [swapTwo([x for x in range(0, len(p))], i, j)]
                          p[j] = p[i]
                          p[i] = i
          # Reverse the list because the :func:`composeList` function expects the
          # permutations to be applied from left to right (instead of right to left
          # as in the mathematical definition of function composition).
          return list(reversed(factors))

2. Suppose that we use Python classes to represent algebraic structures, so that objects of those classes correspond to elements of the algebraic structures. We define the following superclass; all algebraic structures will be subclasses of this superclass.

   class AlgebraicStructure():
       def __repr__(self):    return str(self)
       def __str__(self):     return str(self.elem)
       def __hash__(self):    return hash(self.elem)
    
       def generators(self):  return {}
       def associative(self): return False
       def identity(self):    return None
       def inverses(self):    return {}
       def commutative(self): return False
    
       def __eq__(x, y):
           return x.elem == y.elem
    
       def __init__(self, elem):
           self.elem = elem
    
       def __add__(x, y):
    
           # Complete this function for #2.
    
           # You may want to check wither either or both
           # of the inputs "x" and "y" are simply members
           # of the generating set, and transform them first
           # to make your code more uniform.
    
           return None

   It should be possible to define a new algebraic structure by defining a subclass and overloading a few of the member methods. For example, the following subclass represents a group with the generators 'a', 'b', and 'c':

   class G(AlgebraicStructure):
       def generators(self):  return {'a','b','c'}
       def associative(self): return True
       def identity(self):    return 'c'
       def inverses(self):    return {{'a','b'}, {'c','c'}}
       def commutative(self): return True

   Complete the definition of the __add__() method so that it works in at least the following cases. That is, the __add__() should behave differently in all of these cases, and it should decide how to behave by calling the member methods generators(), associative(), identity(), identity(), inverses(), and commutative().
   1. If the algebraic structure is a free magma, use nested lists to represent an element.
   2. If the algebraic structure is a commutative magma, use nested sets to represent an element.
   3. If the algebraic structure is a free semigroup, use a single list to represent an element.
   4. If the algebraic structure is a commutative semigroup, use a single set to represent an element.
   5. If the algebraic structure is a monoid, do not store the identity element unless it is necessary.
   6. If the algebraic structure is a group or commutative group, "cancel" as many elements with their inverses as possible in an element's representation.

       def __add__(x, y):
    
           # If the arguments are not from the same subclass,
           # do not return a result.
           if type(y) != type(x):
               return None
           constructor = type(x)
           c = x
    
           # Helper method for cancelling inverses in
           # non-commutative structures.
           def cancelNonCommutative(l):
               repeat = True
               while repeat:
                   repeat = False
                   for i in range(0,len(l)-1):
                       if frozenset([l[i],l[i+1]]) in c.inverses():
                           l = l[:i] + l[i+2:]
                           repeat = True
                           break
               return l
    
           # Helper methods for cancelling inverses in
           # non-commutative structures.
           def cancelCommutative(s):
               r = frozenset([])
               for (g1,q1) in s:
                   qNew = q1
                   for (g2,q2) in s:
                       if frozenset([g1,g2]) in c.inverses():
                           qNew = max(0, q1-q2)
                   if qNew > 0:
                       r = r.union({(g1, qNew)})
               return r
    
           # Free magmas.
           # Part (a).
           if not c.associative() and not c.commutative() and\
              c.identity() == None and len(c.inverses()) == 0:
    
               # We use lists because both order and hierarchization
               # matter.
               return constructor((x.elem,y.elem))
    
           # Commutative magmas.
           # Part (b).
           if not c.associative() and c.commutative() and\
              len(c.inverses()) == 0:
    
               # We use sets because order should not matter,
               # but they are nested since hierarchization
               # still matters.
               return constructor(frozenset([x.elem,y.elem]))
    
           # Free semigroups, free monoids, and free groups.
           # Parts (c), (e), and (f).
           if c.associative() and not c.commutative():
    
               # If either argument is the identity,
               # simply return the other argument.
               # This only applies to monoids.
               if x.elem == c.identity(): return y
               if y.elem == c.identity(): return x
    
               # We turn both argument representations into lists
               # so that we can operate on generators as single-item
               # lists.
               x = [x.elem] if not type(x.elem) is list else x.elem
               y = [y.elem] if not type(y.elem) is list else y.elem
    
               # We use list concatenation, which is associative.
               result = x + y
    
               # If inverses exist, we cancel as necessary.
               result = cancelNonCommutative(result)
    
               if len(result) == 0:
                   result = c.identity()
    
               # If the resulting list has length 1, then use the alternate
               # representation of the group element as just the element itself
               # instead of a singleton list.
               if isinstance(result, list) and len(result) == 1:
                   result = result[0]
    
               return constructor(result)
    
           # Commutative semigroups, commutative monoids, and commutative groups.
           # Parts (d), (e), and (f).
           if c.associative() and c.commutative():
    
               # If either argument is the identity,
               # simply return the other argument.
               # This only applies to monoids.
               if x.elem == c.identity(): return y
               if y.elem == c.identity(): return x
    
               # We use a relation mapping generators to counts
               # (which is just a set of pairs).
               x = [(x.elem,1)] if not type(x.elem) is frozenset else x.elem
               y = [(y.elem,1)] if not type(y.elem) is frozenset else y.elem
    
               # Collect all the generators found in "x" and "y".
               gs = set([g for (g,q) in x] + [g for (g,q) in y])
    
               def lookup(g,x):
                   d = dict(x)
                   if g in d: return d[g]
                   return 0
    
               # Add up the generator counts in "x" and "y" and
               # return the resulting relation.
               result = {(g, lookup(g,x) + lookup(g,y)) for g in gs}
               result = {(g,q) for (g,q) in result if q > 0}
    
               # If inverses exist, we cancel as necessary.
               result = cancelCommutative(result)
    
               if len(result) == 0:
                   result = c.identity()
    
               # If the resulting multiset has cardinality one, then use the
               # alternate representation of the group element as just the element
               # itself instead of a singleton multiset.
               if isinstance(result, frozenset) and len(result) == 1:
                   element, count = list(result)[0]
                   if count == 1:
                       result = element
    
               return constructor(result)
     
           return None

   Additional test cases are provided below.

   class M(AlgebraicStructure):
       def generators(self):  return {'A','B','C','D','E'}
    
   M('A') + M('B') == M('B') + M('A') # False.
   M('A') + M('C') + M('B') == M('A') + M('B') + M('B') # False.
   M('A') + (M('B') + M('C')) == M('A') + (M('B') + M('C')) # True.
    
   class CM(AlgebraicStructure):
       def generators(self):  return {'A','B','C'}
       def commutative(self): return True
    
   CM('A') + CM('B') == CM('B') + CM('A') # True.
   (CM('A') + CM('C')) + CM('B') == CM('B') + (CM('C') + CM('A')) # True.
   (CM('A') + CM('B')) + CM('C') == CM('A') + (CM('B') + CM('C')) # False.
    
   class S(AlgebraicStructure):
       def generators(self):  return {1,2,3}
       def associative(self): return True
    
   (S(1) + S(2)) + S(3) == S(1) + (S(2) + S(3)) # True.
   S(2) + S(1) + S(3) == S(3) + S(1) + S(2) # False.
    
   class CS(AlgebraicStructure):
       def generators(self):  return {1,2,3}
       def associative(self): return True
       def commutative(self): return True
    
   (CS(1) + CS(2)) + CS(3) == CS(1) + (CS(2) + CS(3)) # True.
   CS(2) + CS(1) + CS(3) == CS(3) + CS(1) + CS(2) # True.
    
   class N(AlgebraicStructure):
       def generators(self):  return {1,2,3}
       def associative(self): return True
       def identity(self):    return 1
    
   (N(3) + N(2)) + N(3) == N(3) + (N(2) + N(3)) # True.
   N(2) + N(1) + N(3) == N(3) + N(1) + N(2) # False.
   N(1) + N(2) == N(2) + N(1) == N(2) # True.
    
   class CG(AlgebraicStructure):
       def generators(self):  return {-1,0,1}
       def associative(self): return True
       def commutative(self): return True
       def identity(self):    return 0
       def inverses(self):    return frozenset([frozenset([-1,1]), frozenset([0,0])])
    
   CG(-1) + CG(1) == CG(0) # True.
   CG(1) + CG(1) + CG(-1) + CG(-1) + CG(1) == CG(0) + CG(1) # True.
   CG(-1) + CG(1) == CG(1) + CG(1) # False.

3. Implement a new member method enumerate() for the AlgebraicStructure class. This method should take a single positive integer argument n, and should return a set of all the elements in the algebraic structure the representations of which contain n or fewer generators. See the definition of closure for one approach that can be used to implement this method.

       # Any approach for accessing the subclass that works is
       # acceptable. Here, we assume that ".generate()" is always
       # invoked on an object of the subclass.
       def enumerate(self, n):
           def remove_duplicates(l):
               """Inefficiently returns a new list which contains the elements of
               `l` with duplicates removed.
    
               If `l` is a set of hashable objects, use ``set(l)`` instead. This
               is primarily intended for lists of unhashable objects, like other
               lists.
    
               """
               result = []
               for x in l:
                   if x not in result:
                       result.append(x)
               return result
           s = []
           if n == 1:
               for g in self.generators():
                   s.append(self.__class__(g))
           else:
               for i in range(1,n):
                   for x in self.enumerate(i):
                       for y in self.enumerate(n - i):
                           s.append(x + y)
           return remove_duplicates(s)

4. In this problem, you will implement methods for splitting an individual element from an algebraic structure (i.e., an object) into multiple parts that can later be reassembled back together to obtain an equivalent object.
   1. Implement a method split() for the AlgebraicStructure class that takes a single argument, a positive integer n (note that the definition will also have self as the first argument). This method should return a list; each entry in the list should be an ordered pair (a,e) such that e is an element in the algebraic structure that contains at most n generators, and a is an annotation for rebuilding the split-up element. You will need to decide what information, and how much of it, a must contain to solve part (b) below. For example, if the element is from a commutative semigroup (defined as a class CS) such that elements are represented using sets of generators, you may find that you do not need to store any information in a to reconstruct the object. Note the corrected example output below..

      x = CS('a') + CS('b') + CS('c') + CS('d') + CS('e')
       
      # Evaluates to [(None, CS('a') + CS('b')), (None, CS('c') + CS('e')), (None, CS('d'))]
      x.split(2)            
       
      # Evaluates to "True".
      join(x.split(2)) == x

   2. Implement a static method join() for the AlgebraicStructure class that takes a single argument, a list of pairs of the form (a,e), and restores the original element that was split using split(). In other words, we should have for any element x that M.join(x.split(n, p)) is equivalent to x for any positive n.

      You may not assume that the list given as input to join() has its elements in the same order as the list returned by split().

      Your join() implementation should be as efficient as possible given the properties of a particular algebraic structure.

      • A split-up element of a commutative semigroup should be reassembled in linear time (in terms of the number of generators).
      • A split-up element of a magma should be reassembled in at most quadratic time (in terms of the number of generators). Is it possible to reassemble the element in time O(n log n)?

---

Isomorphism: Equivalence of Algebraic Structures

Reasoning about Algebraic Structures using Induction

Suppose an algebraic structure A with operator ⊕ has a finite generating set. Since the generating set is finite and there is only a single binary operator ⊕, we are able to construct very short proofs about properties that apply to all elements in A.

Subgroups and the Direct Product of Groups

Algebraic Structures and Cosets

Generalizations of CRT and Applications

We present some properties of closures. These properties will allow us to prove that certain subsets of a group's elements can be used to generate the whole group. This will help us gain a deeper understanding of the Chinese remainder theorem, and how it can be generalized.

The above fact can be proven by induction for all elements x ∈ closure(closure(S, ⊕), ⊕). For purposes of legibility, let B = closure(S, ⊕), so that we can say closure(B, ⊕) = closure(closure(S, ⊕), ⊕). Given some generating set S, consider the following formula:

P(x)

=

x ∈ closure(S, ⊕)

The base cases are those x that are in B. Thus, we can state the axiom of induction for the algebra closure(B, ⊕):

1. for all predicates P,
2. 1. 1. 1. for all x ∈ B, P(x)
      2. and
      3. 1. for all a ∈ closure(B, ⊕), for all b ∈ closure(B, ⊕),
            1. P(a) and P(b)
            2. implies
            3. P(a ⊕ b)
   2. implies
   3. 1. for all x ∈ closure(B, ⊕), P(x)

The proof is then as follows. For the bases cases, B = closure(S, ⊕), so we have that:

x ∈ B implies x ∈ closure(S, ⊕)

Now, suppose that for some a ∈ closure(B, ⊕) and b ∈ closure(B, ⊕), we have that a ∈ closure(S, ⊕) and b ∈ closure(S, ⊕). Then by definition of the closure,

a ⊕ b ∈ closure(S, ⊕)

This concludes the proof.

n ∈ N, m ∈ N gcd(n,m) = 1 ⊕k represents integer addition modulo k
all groups in this column are isomorphic to each other	all groups in this column are isomorphic to each other
Z/nZ	Z/mZ
closure({1}, ⊕n)   =   {0,...,n-1}	closure({1}, ⊕m)   =   {0,...,m-1}
by Bézout's identity, ∃ s ∈ N, t ∈ N s.t. s ⋅ n + t ⋅ m = 1 t ⋅ m ≡ 1 mod n 1 ∈ closure({m}, ⊕n) closure({1}, ⊕n) ⊂ closure({m}, ⊕n) closure({m}, ⊕n) ⊂ closure({1}, ⊕n) closure({m}, ⊕n) = closure({1}, ⊕n) closure({m}, ⊕n) = Z/nZ	by Bézout's identity, ∃ s ∈ N, t ∈ N s.t. s ⋅ n + t ⋅ m = 1 s ⋅ n ≡ 1 mod m 1 ∈ closure({n}, ⊕m) closure({1}, ⊕m) ⊂ closure({n}, ⊕m) closure({n}, ⊕m) ⊂ closure({1}, ⊕m) closure({n}, ⊕m) = closure({1}, ⊕m) closure({n}, ⊕m) = Z/mZ
notice that t is the inverse of m in Z/nZ, and for a ∈ Z/nZ: t ⋅ m ≡ 1 (mod n) a ⋅ (t ⋅ m) ≡ a (mod n)	notice that s is the inverse of n in Z/mZ, and for b ∈ Z/mZ: s ⋅ n ≡ 1 (mod m) b ⋅ (s ⋅ n) ≡ b (mod m)
notice that for a ∈ Z/nZ, b ∈ Z/mZ: a ⋅ (t ⋅ m)   ⊕   b ⋅ (s ⋅ n)     ≡     a (mod n) a ⋅ (t ⋅ m)   ⊕   b ⋅ (s ⋅ n)     ≡     b (mod m) (a ⋅ t) ⋅ m   ⊕   (b ⋅ s) ⋅ n     ≡     x (mod (n ⋅ m)) notice that if n and m are fixed, so are t and s; then, x changes only based on a ∈ Z/nZ and b ∈ Z/mZ; there are n ⋅ m possible pairs (a,b); are there n ⋅ m distinct solutions, one for each pair?
closure({m}, ⊕n)   =   {0,...,n-1}	closure({n}, ⊕m)   =   {0,...,m-1}
closure({m}, ⊕n⋅m)   =   {0 ⋅ m,   1 ⋅ m,   2 ⋅ m, ... ,  (n-1) ⋅ m}	closure({n}, ⊕n⋅m)   =   {0 ⋅ n,   1 ⋅ n,   2 ⋅ n, ... ,  (m-1) ⋅ n}
take the product of the above two groups; all the following groups are isomorphic
Z/nZ   ×   Z/mZ
closure({m}, ⊕n)   ×   closure({n}, ⊕m)
closure({m}, ⊕m⋅n)   ×   closure({n}, ⊕n⋅m)
{0 ⋅ m,   1 ⋅ m,   2 ⋅ m, ... ,  (n-1) ⋅ m}   ×   {0 ⋅ n,   1 ⋅ n,   2 ⋅ n, ... ,  (m-1) ⋅ n}
{i ⋅ m | i ∈ {0,...,n-1}}   ×   {j ⋅ n | j ∈ {0,...,m-1}}
{(i ⋅ m,   j ⋅ n)  |  i ∈ {0,...,n-1}, j ∈ {0,...,m-1}}
{i ⋅ m ⊕   j ⋅ n  |  i ∈ {0,...,n-1}, j ∈ {0,...,m-1}}
closure({m,n}, ⊕n⋅m)
by Bézout's identity, ∃ s,t ∈ N s.t. s ⋅ n + t ⋅ m = 1 s ⋅ n + t ⋅ m ≡ 1 mod (n ⋅ m) 1 ∈ closure({n,m}, ⊕n⋅m) closure({1}, ⊕n⋅m) ⊂ closure({n,m}, ⊕n⋅m) closure({n,m}, ⊕n⋅m) ⊂ closure({1}, ⊕n⋅m) closure({n,m}, ⊕n⋅m) = closure({1}, ⊕n⋅m) closure({n,m}, ⊕n⋅m) = Z/(n ⋅ m)Z
Z/(n ⋅ m)Z

For purposes of illustration, we instantiate the above table using n = 3 and m = 5.

3 ∈ N, 5 ∈ N gcd(3,5) = 1 ⊕k represents integer addition modulo k
all groups in this column are isomorphic to each other	all groups in this column are isomorphic to each other
Z/3Z	Z/5Z
closure({1}, ⊕3)   =   {0,1,2}	closure({1}, ⊕5)   =   {0,1,2,3,4}
by Bézout's identity, (-1) ⋅ 5 + 2 ⋅ 3 = 1 (-1) ⋅ 5 ≡ 1 mod 3 2 ⋅ 5 ≡ 1 mod 3 1 ∈ closure({5}, ⊕3) closure({1}, ⊕3) ⊂ closure({5}, ⊕3) closure({5}, ⊕3) ⊂ closure({1}, ⊕3) closure({5}, ⊕3) = closure({1}, ⊕3) closure({5}, ⊕3) = Z/3Z	by Bézout's identity, 2 ⋅ 3 + (-1) ⋅ 5 = 1 2 ⋅ 3 ≡ 1 mod 5 1 ∈ closure({3}, ⊕5) closure({1}, ⊕5) ⊂ closure({3}, ⊕5) closure({3}, ⊕5) ⊂ closure({1}, ⊕5) closure({3}, ⊕5) = closure({1}, ⊕5) closure({3}, ⊕5) = Z/5Z
closure({5}, ⊕3)   =   {0,1,2}	closure({3}, ⊕5)   =   {0,1,2,3,4}
closure({5}, ⊕15)   =   {0, 5, 10}	closure({3}, ⊕15)   =   {0, 3, 6, 9, 12}
take the product of the above two groups; all the following groups are isomorphic
Z/3Z   ×   Z/5Z
closure({5}, ⊕3)   ×   closure({3}, ⊕5)
closure({5}, ⊕15)   ×   closure({3}, ⊕15)
{0, 5, 10}   ×   {0, 3, 6, 9, 12}
{(0,0),  (0,3),  (0,6),  (0,9),  (0,12),  (5,0),  (5,3),  (5,6),  (5,9),  (5,12),  (10,0),  (10,3),  (10,6),  (10,9),  (10,12) }
{0 ⊕ 0,  0 ⊕ 3,  0 ⊕ 6,  0 ⊕ 9,  0 ⊕ 12,  5 ⊕ 0,  5 ⊕ 3,  5 ⊕ 6,  5 ⊕ 9,  5 ⊕ 12,  10 ⊕ 0,  10 ⊕ 3,  10 ⊕ 6,  10 ⊕ 9,  10 ⊕ 12 }
{0,  3,  6,  9,  12,  5,  8,  11,  14,  2,  10,  13,  1,  4,  7 }
Z/15Z

We now generalize the above tables for CRT to include the case in which gcd(n,m) > 1.

n ∈ N, m ∈ N gcd(n,m) = g ⊕k represents integer addition modulo k
all groups in this column are isomorphic to each other	all groups in this column are isomorphic to each other
Z/(n/g)Z	Z/(m/g)Z
closure({g}, ⊕n)   =   {0 ⋅ g,  ...,   ((n/g)-1) ⋅ g}	closure({g}, ⊕m)   =   {0 ⋅ g,  ...,   ((m/g)-1) ⋅ g}
by Bézout's identity, ∃ s ∈ N, t ∈ N s.t. s ⋅ n + t ⋅ m = g t ⋅ m ≡ g mod n g ∈ closure({m}, ⊕n) closure({g}, ⊕n) ⊂ closure({m}, ⊕n) closure({m}, ⊕n) ⊂ closure({g}, ⊕n) closure({m}, ⊕n) ≅ closure({g}, ⊕n) ≅ closure({1}, ⊕n/g) ≅ Z/(n/g)Z	by Bézout's identity, ∃ s ∈ N, t ∈ N s.t. s ⋅ n + t ⋅ m = g s ⋅ n ≡ g mod m g ∈ closure({n}, ⊕m) closure({g}, ⊕m) ⊂ closure({n}, ⊕m) closure({n}, ⊕m) ⊂ closure({g}, ⊕m) closure({n}, ⊕m) ≅ closure({g}, ⊕m) ≅ closure({1}, ⊕m/g) ≅ Z/(m/g)Z
notice that t and m generate g in Z/nZ, and for a ∈ Z/(n/g)Z: t ⋅ m ≡ g (mod n) a ⋅ (t ⋅ m) ≡ (a ⋅ g) (mod n)	notice that s and n generaete g in Z/mZ, and for b ∈ Z/(m/g)Z: s ⋅ n ≡ g (mod m) b ⋅ (s ⋅ n) ≡ (b ⋅ g) (mod m)
notice that for a ∈ Z/(n/g)Z, b ∈ Z/(m/g)Z: a ⋅ (t ⋅ m)   ⊕   b ⋅ (s ⋅ n)     ≡     (a ⋅ g) (mod n) a ⋅ (t ⋅ m)   ⊕   b ⋅ (s ⋅ n)     ≡     (b ⋅ g) (mod m) (a ⋅ t) ⋅ m   ⊕   (b ⋅ s) ⋅ n     ≡     (x' ⋅ g) (mod (n ⋅ m)) (a ⋅ t) ⋅ m   ⊕   (b ⋅ s) ⋅ n     ≡     x (mod (n ⋅ m)) notice that if n and m are fixed, so are t and s; then, x = x' ⋅ g changes only based on a ∈ Z/(n/g)Z and b ∈ Z/(m/g)Z; there are (n/g) ⋅ (m/g) possible pairs (a,b); are there (n/g) ⋅ (m/g) distinct solutions, one for each pair?
closure({m}, ⊕n)   =   {0 ⋅ g,  ...,   ((n/g)-1) ⋅ g}	closure({n}, ⊕m)   =   {0 ⋅ g,  ...,   ((m/g)-1) ⋅ g}
take the product of the above two groups; all the following groups are isomorphic
Z/(n/g)Z   ×   Z/(m/g)Z
closure({m/g}, ⊕n/g)   ×   closure({n/g}, ⊕m/g)
closure({m/g}, ⊕n⋅m/g2)   ×   closure({n/g}, ⊕n⋅m/g2)
{i ⋅ m/g | i ∈ {0,...,n/g-1}}   ×   {j ⋅ n/g | j ∈ {0,...,m/g-1}}
{(i ⋅ m/g,   j ⋅ n/g)  |  i ∈ {0,...,n/g-1}, j ∈ {0,...,m/g-1}}
{i ⋅ m/g ⊕   j ⋅ n/g  |  i ∈ {0,...,n/g-1}, j ∈ {0,...,m/g-1}}
closure({m/g,n/g}, ⊕n⋅m/g2)
by Bézout's identity, ∃ s,t ∈ N s.t. s ⋅ n + t ⋅ m = g s ⋅ n/g + t ⋅ m/g = 1 s ⋅ n/g + t ⋅ m/g ≡ 1 mod ({n ⋅ m/g2) g ∈ closure({n,m}, ⊕n⋅m) 1 ∈ closure({n/g,m/g}, ⊕n⋅m/g2) closure({1}, ⊕n⋅m/g2) ⊂ closure({n/g,m/g}, ⊕n⋅m/g2) closure({n/g,m/g}, ⊕n⋅m/g2) ⊂ closure({1}, ⊕n⋅m/g2) closure({n/g,m/g}, ⊕n⋅m/g2) = closure({1}, ⊕n⋅m/g2) closure({n/g,m/g}, ⊕n⋅m/g2) = Z/(n ⋅ m/g2)Z
Z/(n ⋅ m/g2)Z
closure({g},⊕n⋅m/g)

Given the above, one might observe that, in fact, there are more multiple of g in Z/(n ⋅ m)Z than there are in Z/(n ⋅ m/g²)Z. In fact, there are g times as many multiples of g in Z/(n ⋅ m)Z. Thus, each unique pair in Z/(n/g)Z × Z/(m/g)Z determines not one element in Z/((n ⋅ m)/g)Z, but g different elements. So if it is not Z/(n ⋅ m/g²)Z, then which product group is isomorphic to the set Z/((n ⋅ m)/g)Z, the set of multiples of g modulo m ⋅ n?

For purposes of illustration, we instantiate the above table for g > 1 using n = 4, m = 6, and g = 2.

4 ∈ N, 6 ∈ N gcd(4,6) = 2 ⊕k represents integer addition modulo k
all groups in this column are isomorphic to each other	all groups in this column are isomorphic to each other
Z/4Z	Z/6Z
closure({2}, ⊕4)   =   {0,2}	closure({2}, ⊕6)   =   {0,2,4}
by Bézout's identity, (1) ⋅ 6 + (-1) ⋅ 4 = 2 (1) ⋅ 6 ≡ 2 mod 4 2 ∈ closure({6}, ⊕4) closure({2}, ⊕4) ⊂ closure({6}, ⊕4) closure({6}, ⊕4) ⊂ closure({2}, ⊕4) closure({6}, ⊕4) = closure({2}, ⊕4) closure({2}, ⊕4) ≅ {0,2} ≅ Z/(4/2)Z ≅ {0,1} ≅ Z/2Z	by Bézout's identity, (-1) ⋅ 4 + (1) ⋅ 6 = 2 (-1) ⋅ 4 ≡ 2 mod 6 (5) ⋅ 4 ≡ 2 mod 6 2 ∈ closure({4}, ⊕6) closure({2}, ⊕6) ⊂ closure({4}, ⊕6) closure({4}, ⊕6) ⊂ closure({2}, ⊕6) closure({4}, ⊕6) = closure({2}, ⊕6) closure({2}, ⊕6) ≅ {0,2,4} ≅ Z/(6/2)Z ≅ {0,1,2} ≅ Z/3Z
closure({6}, ⊕4)   =   {0,2}	closure({4}, ⊕6)   =   {0,2,4}
closure({6}, ⊕4)   ≅   {0,1}	closure({4}, ⊕6)   ≅   {0,1,2}
closure({6}, ⊕4)   ≅   Z/2Z	closure({4}, ⊕6)   ≅   Z/3Z
take the product of the above two groups; all the following groups are isomorphic
closure({6}, ⊕4)   ×   closure({4}, ⊕6)
{0, 2}   ×   {0, 2, 4}
{0, 1}   ×   {0, 1, 2}
Z/2Z   ×   Z/3Z
Z/((4 ⋅ 6)/22)Z
Z/6Z
{0,1,2,3,4,5}
{0,2,4,6,8,10}
closure({2}, ⊕(4⋅6)/2)

---

Assignment #6: Generalizing CRT

For this assignment, you will submit a single Python source file a6.py.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts. You may reuse functions that you defined on previous assignments.

1. Implement a function solve() that takes three integer arguments x, y, and z. The function should return a tuple containing two integers, (a,b), such that the following always holds:

   (a,b) = solve(x,y,z)
    
   (x * a + y * b) % (x*y) == z % (x*y) # True.
   a in range(0,y)                      # True.
   b in range(0,x)                      # True.

   If no such pair (a,b) exists, your method should return None.
2. Include the following class declaration in your file. An Eqn() object represents an equation of the form c ⋅ x ≡ a (mod n), where x is a variable.

   class Eqn():
       c = 1
       a = 0
       n = 1
       solvable = True
    
       def __init__(self,c,a,n):
           self.c = c
           self.a = a
           self.n = n
    
       def __repr__(self):
           return str(self)
    
       def __str__(self):
           if not self.solvable:
               return "unsolvable"
           else:
               return str(self.c) + "x = " + str(self.a) + " mod " + str(self.n)
    
       def unsolvable(self):
           self.solvable = False
           self.c = None
           self.a = None
           self.n = None
    
       def simplify(self):
           # Implement for #2, part (a).
           pass 
    
       def __add__(e1, e2):
           
           # Modify this method for #2, part (b).
           # This method should behave like CRT2(),
           # but it should be able to handle all possible
           # cases.
            
           # This function should return another Eqn() 
           # object that represents the solution (or
           # lack thereof) to the two equations e1 and e2.
    
           return None

   1. Implement a member method simplify() that converts an Eqn() object into an equivalent one in which c = 1, if possible (as determined by this fact). If this is not possible, the method should set the object's self.solvable field to False (use the member method unsolvable()). Some test cases are provided below.

      >>> x = Eqn(6,4,8)
      >>> x
      6x = 4 mod 8
      >>> x.simplify()
      >>> x
      1x = 2 mod 4
       
      >>> Eqn(1,2,7)
      1x = 2 mod 7
       
      >>> Eqn(3,4,5)
      3x = 4 mod 5
       
      >>> x = Eqn(5,5,100)
      >>> x.simplify()
      >>> x
      1x = 1 mod 20
       
      >>> x = Eqn(7,1,7)
      >>> x.simplify()
      >>> x
      unsolvable
       
      >>> x = Eqn(7,0,7)
      >>> x.simplify()
      >>> x
      1x = 0 mod 1
       
      >>> x = Eqn(15,5,25)
      >>> x.simplify()
      >>> x
      1x = 2 mod 5
       
      >>> x = Eqn(3,5,6)
      >>> x.simplify()
      >>> x
      unsolvable
              

   2. Implement a member method __add__(e1, e2). This method should take two Eqn() objects as arguments. It should return a new Eqn() object that represents a solution to the two equations, if one exists (otherwise, the returned object should have its self.solvable field set to False). That is, the input represents the following system of equations:

      c1 ⋅ x	≡	a1 (mod n1)
      c2 ⋅ x	≡	a2 (mod n2)

      The method should return the unique solution if it exists in the form of an equation object where c = 1, and where a and n are chosen appropriately:

      1 ⋅ x

      ≡

      a (mod n)

      If no solution exists, the returned Eqn() object should have its unsolvable field set to True. Your method should be similar to CRT2(), but it must handle all possible inputs correctly (i.e., the n values of the two equations are not necessarily coprime, and c may be any integer). Solutions that use an exhaustive search will receive no credit. Some test cases are provided below.

      >>> Eqn(1,3,15) + Eqn(1,6,21)
      1x = 48 mod 105
       
      >>> Eqn(1,3,15) + Eqn(1,6,21) + Eqn(2,12,18)
      1x = 258 mod 315
       
      >>> Eqn(1,2,15) + Eqn(1,4,21)
      unsolvable
       
      >>> Eqn(1,7,8) + Eqn(1,0,1)
      1x = 7 mod 8
              

3. Consider the algebraic structure consisting of all possible equations of the form Eqn(c,a,n) where c, a, and n are integers. The operator for this algebraic structure is the + operator (defined by __add__()). Determine all the algebraic properties of this algebraic structure, and determine which algebraic structure it is. If an identity and/or inverses exist, you must describe which elements they are or how to find them.
4. Define a Python function GCRTN() (not a member method of Eqn()) that takes one input, which is a list of one or more Eqn() objects. This list represents a system of equations of the following form:

   c1 ⋅ x	≡	a1 (mod n1)
   	⋮
   ck ⋅ x	≡	ak (mod nk)

   The method should return the unique solution in the form of a single Eqn() object where c = 1, and where a and n are chosen appropriately:

   1 ⋅ x

   ≡

   a (mod n)

   If there is no solution, the return Eqn() object should indicate this. You may not violate the encapsulation of the Eqn() objects. You may only use member methods to create, modify, or combine Eqn() objects.

---

Review #2

This section contains a comprehensive collection of review problems going over all the course material. These problems are an accurate representation of the kinds of problems you may see on an exam.

The following is a breakdown of what you should be able to do at the end of the course (and of what you may be tested on in the final exam). Notice that many of the tasks below can be composed. This also means that many problems can be solved in more than one way.

• problems that can be solved
  • generate a "random" number using permutations
  • check if a number is prime
    • using an exhaustive search
    • using the Fermat primality test
  • generate a random number in a certain range
  • generate a random prime in a certain range
  • use random primes
    • to encrypt information and transmit it safely using RSA
    • to share information requiring cooperation using Shamir secret sharing
    • to store information on unreliable storage devices (using Shamir secret sharing)
    • to perform many arithmetic operations x₁ ⊕ ... ⊕ x_n for some operator ⊕ in sequence more efficiently (using CRT)
      • if the range of the final output is known
      • if working in parallel along multiple distinct p_i in Z/p_iZ, and then performing CRT once is less expensive than working in Z/nZ the whole time
  • solving equations and performing computations
    • solve a system of equations where each equation is modulo some n_i
      • derive a system of equations from a word problem via group isomorphisms
        • rotating objects
        • objects of different sizes
        • containers of different sizes
        • permutations in the cyclic groups C_n
      • solve a system with additive and multiplicative inverses
      • solve generalized cases (gcd(n,m) > 1 and/or c > 1 in c ⋅ x ≡ a (mod n))
      • solve a system of three or four equations
    • compute exponents modulo n efficiently
      • using Euler's theorem and φ (when possible)
      • using the efficient repeated-squaring method
    • compute multiplicative inverses Z/nZ
      • using φ(n)
      • using the extended Euclidean algorithms
    • counting and computing square roots of quadratic residues in Z/nZ
      • using the explicit formula for prime moduli p where p mod 4 = 3
      • determine the upper bound on, or the exact number of, square roots of some x ∈ Z/nZ if the factors of n are known
      • if the prime factors of n are known, using CRT to find all roots in Z/nZ
  • recognize when you cannot solve problems efficiently
    • computing φ(n) for an arbitrary n
    • factoring n for an arbitrary n
    • computing discrete logarithms
    • decrypting RSA messages without any knowledge of private keys
  • permutations
    • identify when a relation is a permutation
    • decompose a permutation into adjacent swaps or swaps
    • determine the number of permutations of n elements
  • algebraic properties
    • what are the algebraic properties of common operators and algebraic structures
    • what are the algebraic properties of common data structures
      • binary trees are a magma if order of children matters, or a commutative magma if order of children does not matter
        • the generators {g₁, g₂, ...} are leaves
        • given two trees, (e.g., g₁ and (g₂ ⊕ g₃)), larger trees are constructed using the binary operator (e.g., g₁ ⊕ (g₂ ⊕ g₃))
      • lists are a monoid (list concatenation is the associative operation, and the empty list is the identity)
      • strings are a monoid (string concatenation is the associative operation, and the empty string is the identity)
      • the integers are a group
    • what are the generators of an algebraic structure
  • induction
    • given a generating set, operator, and algebraic properties of closure(S,⊕), state the axiom of induction
    • use induction to prove that P(x) for all x ∈ closure(S,⊕)
    • use induction to prove that P(n) for all n ∈ closure({0,1},+) where closure({0,1},+) = N

---

Bonus Assignment

For this assignment, you will submit a single Python source file aX.py.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts. You may reuse functions that you defined on previous assignments.

Suppose that you are given a black box quantum() that can compute the following Python function on any three inputs f, g, and n in the same amount of time that it takes to run f(n) and g(n):

def quantum(f, g, n):
    for i in range(0,n):
        if f(i) != g(i):
            return False
    return True

In other words, if f(n) and g(n) both run in polynomial time, then quantum(f,g,n) also runs in polynomial time (the above inefficient implementation is just for purposes of illustration and testing).

1. Implement an efficient, polynomial-time algorithm factor() that takes a single positive integer input n and returns a non-trivial factor x of n (i.e., 1 < x < n) if it exists. Your implementation must invoke quantum() (it may invoke it multiple times, but no more than polynomially many times). That is, factor() must be a polynomial-time reduction from the factoring problem to quantum(). Hint: to better understand how quantum() might be able to help, try writing a function that can efficiently check if its input is a Carmichael number by using quantum().
2. Modify your solution to part (a) so that it returns all the factors of the input n. Explain in detail why your algorithm still runs in polynomial time.
3. Modify your solution from part (a) or part (b) so that it works with the following (slightly more realistic) version of quantum() (pseudocode provided; implement an inefficient test version of quantum() for more points):

   def quantum(f, g, n):
       if [f(i) for i in range(0,n)] is a permutation of [g(i) for i in range(0,n)]:
           return True
       return False

4. Implement an efficient solver for the discrete logarithm problem using quantum().

---