The lecture notes below are presented for archival purposes as they appeared at the time that this course was originally offered. The latest version of these notes is available at https://lapets.io/course-abstract-algebra.
NOTE: This page contains all the 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.

[link]  1. Introduction, Background, and Motivation

[link]  1.1. Overview

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, residues, and several others. We will see how these structures and their properties can be used for implementing random number generators, error correcting codes, defining simple cryptographic protocols, approximating and interpolating numerical functions, and other applications.

In covering the material for this course, we will use the standard language and conventions for discussing these mathematical structures that have been developed by the community of mathematicians. You will need to become familiar with these conventions in order to find, identify, and use the structures and techniques that have already been developed for solving certain computational problems. At the same time, we will also learn how modern programming languages and programming paradigms can be used to implement these structures and algorithms both accessibly and efficiently.

The development and application of mathematics involves abstraction. A problem can be viewed at multiple levels of abstraction, and in developing mathematics humans have adopted a variety of techniques that allow them to successfully employ abstraction to study natural phenomena and solve problems.
symbolic abstract meaning concrete meaning in
application domain
2 + 3 5 five objects
{(1, 2), (1, 3)} acyclic graph file system
{(1, 2), (2, 3), (3, 1)} graph with cycle network

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.

In this course, we will begin to reviewing the terminology and concepts of logic, integer arithmetic, and set theory, which we will use throughout the course. We will then show that the algebraic properties of the integers also apply to congruence classes of integers (i.e., the properties of modular arithmetic operations), and we will derive and utilize theorems that have useful computer science applications (such as for generating random numbers and creating cryptographic protocols). We will then go further and show that some of the algebraic properties that hold in integer and modular arithmetic can also apply to any data structure, and we will study how to recognize and take advantage of these properties.

[link]  1.2. 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:
  • n0 = a number in the range (inclusive) 0 to 5;
  • ni = (2 ⋅ ni-1 + 1) mod 6.
We can consider another method:
  • n0 = an initial seed integer 104 > n ≥ 103;
  • ni = only the last four digits of ni-12.
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.

[link]  2. 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.

[link]  2.1. Formulas without quantifiers

[link]  
Definition: 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

[link]  2.2. Terms: integers and term operators that take integer inputs

[link]  
Definition: 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 2**3
pow(2,3)

[link]  2.3. Formulas: relational operators and predicates dealing with integers

[link]  
Definition: 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
[link]  
Example: 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)
We will use the following predicates throughout the course.
[link]  
Definition: For any x,y ∈ ℤ, x | y    iff   y/x ∈ ℤ. If x | y, we then say that x is a factor of y.
[link]  
Definition: For any y ∈ ℤ, y is prime    iff    for any integer x where 2 ≤ x < y, it is not true that x | y. In other words, y is prime if its only factors are 1 and y (itself).
formula what it represents
x | y y / x ∈ ℤ
x divides y
y is divisible by x
y is an integer multiple of x
y mod x = 0
x is a factor of y
y is prime y > 1 and
x | y implies x = 1 or x = y

y > 1 and
y is divisibly only by 1 and itself

[link]  2.4. Terms: finite sets of integers, term operators that take set inputs, and set comprehensions

[link]  
Definition: A finite set of integers is an unordered, finite collection of zero or more integers with no duplicates. 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} {1,2,3}
{2,..,5} {2,3,4,5} set(range(2,6))
{ x | x ∈ {1,2,3,4,5,6}, x > 3 } {4,5,6} {x for x in {1,2,3,4,5,6} if x > 3}
|{1,2,3,4}| 4 len({1,2,3,4})


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 ∈ S1 or z ∈ S2} {1,2,3}.union({4,5})
S1 ∩ S2 {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 the terms below do not represent finite sets of integers, we introduce the following two set terms in order to reference them throughout the notes.
[link]  
Definition: Let ℤ be the set of all integers.
[link]  
Definition: Let ℕ be the set of all positive integers, including 0.
term what it represents
ℕ {0, 1, 2, ...}
ℤ {..., -2, -1, 0, 1, 2, ...}

[link]  2.5. Formulas: quantifiers over finite sets of integers

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

def forall(X, P):
  S = {x for x in X if P(x)}
  return len(S) == len(X)

def exists(X, P):
  S = {x for x in X if P(x)}
  return len(S) > 0

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 {1,2,3}
4 ∈ {1,2,3} false 4 in {1,2,3}
∀ x ∈ {1,2,3}, x > 0 and x < 4 true forall({1,2,3}, lambda x: x > 0 and x < 4)
∃ x ∈ {1,2,3}, x < 1 and x > 3 false exists({1,2,3}, lambda x: x < 1 or x > 3)
∀ x ∈ ∅, f true
∃ x ∈ ∅, f false
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 if no elements exist at all). We can see that the Python functions for these quantifiers are consistent with this interpretation.
[link]  
Fact: Let X = {x1 , ..., xn} be a finite set and let P be a predicate that applies to a single integer argument. Then we have the following correspondences between quantifiers and logical operators:
∀ x ∈ X, P(x)     
iff
     P(x1) and P(x2) and P(x3) and ... and P(xn)
∃ x ∈ X, P(x)     
iff
     P(x1) or P(x2) or P(x3) or ... or P(xn)
[link]  
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.

    # We provide two equivalent implementations.
                
    def all(X, P):
        return  forall(X, P)
        
    def all(X, P):
      S = {x for x in X if P(x)}
      return len(S) == len(X)
                
  • None of the elements of a set X satisfy the predicate P.

    # We provide two equivalent implementations.

    def none(X, P):
        return  forall(X, lambda x: not P(x))
        
    def none(X, P):
      S = {x for x in X if P(x)}
      return len(S) == 0
                
  • At most one of the elements of a set X satisfy the predicate P.

    def atMostOne(X, P):
      S = {x for x in X if P(x)}
      return len(S) <= 1
                
  • At least one of the elements of a set X satisfy the predicate P.

    # We provide two equivalent implementations.

    def atLeastOne(X, P):
      return exists(X, P)

    def atLeastOne(X, P):
      S = {x for x in X if P(x)}
      return len(S) >= 1
                
[link]  
Exercise: Implement a Python function corresponding to the predicate "p is prime" for any integer p.

def prime(p):
    return  p > 1 and forall(set(range(2, p)), lambda n: p % n != 0)
        

[link]  2.6. Formulas: predicates dealing with finite sets of integers

[link]  
Definition: 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 {1,2,3}
{1,2} ⊂ {1,2,3} true subset({1,2}, {1,2,3})
{4,5} ⊂ {1,2,3} false subset({4,5}, {1,2,3})

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

[link]  2.7. Terms: set products and binary relations

[link]  
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.
[link]  
Example:
term what it represents example of one possible
Python representation
{1,2} × {5,6,7} {(1,5),(1,6),(1,7),(2,5),(2,6),(2,7)} { (x,y) for x in {1,2} for y in {4,5,6,7} }
[link]  
Definition: A set R is a relation between the sets X and Y if R ⊂ X × Y.

[link]  2.8. 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 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


Exercise: Write a Python function that takes a finite set of integers and builds the relation on that set corresponding to the operator relational 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.

[link]  2.9. 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.
[link]  
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 | y ∈ X, (x,y) ∈ R} | x ∈ X}
[link]  
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.

def quotient(X,R):
    return {frozenset({y for y in X if (x,y) in R}) for x in X}
        
Below, we evaluate the above function on an example input.

>>> quotient({1,2,3,4}, {(1,1),(2,2),(3,3),(2,3),(3,2),(4,4)})

{frozenset({4}), frozenset({2, 3}), frozenset({1})}
        
[link]  
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.
[link]  
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.

def quotientMap(X,R):
  return {(x, frozenset({y for y in X if (x,y) in R})) for x in X}
        
[link]  
Exercise: Determine whether {(x,y) | x ∈ ℤ, y ∈ ℤ, x + y mod 2 = 0} is an equivalence relation.
[link]  
Example: Let X be a set of humans. Let R be the following relation R ⊂ X × X:
R
=
{ (x, y) | x ∈ X, y ∈ X, x is y or x is a relative of y }
Then R is an equivalence relation. Furthermore, the quotient set X/R is a separation of the humans in X into families of relatives. No one in any equivalence class (a.k.a., a family) in X/R is related to anyone in any other equivalence class, and everyone in each equivalence class in X/R is related to everyone else in that equivalence class.

More generally, we can view the quotient set X/R as the separation of X into the largest number of groups such that no two relatives are separated into separate groups. Thus, |X/R| is the number of distinct families of humans in the set X.

[link]  2.10. Assignment #1: Logic, Integers, Sets, and Relations

In this assignment you will define Python functions that represent various constructs. You must submit a single Python source file named a1.py. Please follow the gsubmit directions.

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 1-3 lines. You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on the lecture notes and on each other; carefully consider whether you can use functions from the lecture notes, or functions you define in one part within subsequent parts.
  1. Use Python set comprehensions and the quantifier functions defined during lecture to solve the following problems (you may use any Python function we defined in the lecture notes).
    1. Implement a function primes(n) that takes a single integer argument n and returns the total number of primes less than or equal to n.

      >>> primes(2)
      1

      >>> primes(5)
      3

      >>> primes(11)
      5
                    
    2. Implement a Python function composites(ns) that takes a finite set of integers ns as its one argument and returns True if none of the integers in the set are prime, and False otherwise.

      >>> composites({1,2,3,4})
      False

      >>> composites({4,6,12})
      True
                    
  2. Solve the following problems involing relations. Recall that using Python, we are representing relations as sets of tuples (i.e., pairs such as (1,2)). You should include the following definition in your code:

    def quotient(X,R):
        return {frozenset({y for y in X if (x,y) in R}) for x in X}
              
    1. Implement a function isReflexive() that takes as its input two arguments: a set X and a relation R. The function should return True if the relation R is a reflexive relation on X, and it should return False otherwise.

      isReflexive({1,2}, {(1,1), (2,2)}) == True
      isReflexive({1,2,3}, {(1,2), (2,1), (3,3)}) == False
                    
    2. Include the following definitions in your code:

      X1 = {"a","b","c"}
      R1 = ?
                    
      Define the variable R1 above so that R1 is an equivalence relation over X1, and so that the following will evaluate to True:

      >>> quotient(X1,R1) == {frozenset({"a"}),frozenset({"b"}),frozenset({"c"})}
      True
                    
    3. Include the following definitions in your code:

      X2 = {1,2,3,4,5,6}
      R2 = ?
                    
      Define the variable R2 above so that R2 is an equivalence relation over X2, and so that the following will evaluate to True:

      >>> quotient(X2,R2) == {frozenset({1,2,3}),frozenset({4,5}),frozenset({6})}
      True
                    
    4. Include the following definitions in your code:

      X3 = set(range(0,3))
      R3 = ?
                    
      Define the variable R3 above so that R3 is an equivalence relation over X3, and so that the following will evaluate to True:

      >>> quotient(X3,R3) == {frozenset({0,1,2})}
      True
                    
    1. Implement a Python function factors(n) that takes a single positive integer argument n and returns a finite set of integers containing all the factors k of that number (i.e., all numbers k such that k | n).

      >>> factors(9)
      {1,3,9}

      >>> factors(14)
      {1,2,7,14}
                    
    2. Implement a Python function shared(S) that takes any finite set of positive integers S and returns a relation over S in which any two numbers in S that share at least one factor greater than 1 are related.

      >>> shared({2,3,4,5,6})
      {(2,2), (2,4), (2,6), (3,3), (3,6), (4,2), (4,4), 
       (4,6), (5,5), (6,2), (6,3), (6,4), (6,6)}

      >>> shared({2,3,7})
      {(2,2), (3,3), (7,7)}
                    
    3. Determine which of the three properties of an equivalence relation (reflexivity, symmetry, and transitivity) always apply to any result of shared() (assuming its input is a finite set of positive integers). If all three properties hold, indicate this in a code comment. Define three veriables in your code:

      reflexive = ?
      symmetric = ?
      transitive = ?
                    
      If a property always applies to any output, simply assign None to the corresponding variable. If a property does not apply to all outputs of shared(), assign an input set to the corresponding variable that returns an output relation that does not satisfy that property.
  4. Implement a function classes(S, n) that takes two arguments: any finite set of integers S and a single integer argument n. The function should then break up the set of integers S into a set of equivalence classes (i.e., a set of sets) corresponding to the congruence classes modulo n. See the examples below. Hint: build a relation over the set S using a set comprehension and the modulus operator, and then use quotient().

    >>> classes({-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6}, 3)
    {frozenset({-6, -3, 0, 3, 6}), frozenset({-5, -2, 1, 4}), frozenset({-4, -1, 2, 5})}

    >>> classes(set(range(0,10)), 2)
    {frozenset({0,2,4,6,8}), frozenset({1,3,5,7,9})}
              

[link]  3. 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.

[link]  3.1. Terms: congruence classes in ℤ/mℤ, term operators, and relations

[link]  
Definition: For any m ∈ ℤ, define:
mℤ
=
{x ⋅ m | x ∈ ℤ}
[link]  
Definition: For any m ∈ ℤ, define:
k + mℤ
=
{k + (x ⋅ m) | x ∈ ℤ}
[link]  
Exercise: Show that the relation R = {(x,y) | x ∈ ℤ, y ∈ ℤ, x mod 17 = y mod 17} is an equivalence relation.
[link]  
Definition: For any given m ∈ ℤ, define:
ℤ/mℤ
=
ℤ/{(x,y) | x ∈ ℤ, y ∈ ℤ, x mod m = y mod m}
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 + mℤ		 {z + (a ⋅ m) | a ∈ ℤ}
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


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

[link]  3.2. Algebra of congruence classes

We use the familiar symbols +, -, ⋅, and 0, 1, 2, 3, 4, ... to represent operations on congruence classes. When these symbols are used to represent operations on integers, they have certain algebraic properties. This allows us, for example, to solve equations involving integers and variables, such as in the example below (in which we add the same integer to both sides, use associativity of + and commutativity of ⋅, and cancel 2 on both sides of the equation):
2 ⋅ x - 3
=
1
(2 ⋅ x - 3) + 3
=
1 + 3
2 ⋅ x
=
4
2 ⋅ x
=
2 ⋅ 2
x ⋅ 2
=
2 ⋅ 2
x
=
2
Do the operations on congruence classes, represented by the operators +, -, and ⋅, also share the familiar algebraic properties of the corresponding operations on integers? In many cases they do, but in some cases these properties only apply under specific circumstances.
[link]  
Example: Suppose we write the term 3 + 4 ≡ 2 where 2, 3, and 4 are congruence classes in ℤ/5ℤ. What is the meaning of this term? First, note the following equivalence.
{ x + y | x ∈ ℤ, y ∈ ℤ} = {z | z ∈ ℤ }
Now, we expand the definitions of congruence classes and the operation + on congruence classes below.
3 + 4
≡
(3 + 5ℤ) + (4 + 5ℤ)
=
{3 + a ⋅ 5 | a ∈ ℤ} + {4 + b ⋅ 5 | b ∈ ℤ}
=
{(x + y)   |   x ∈ {3 + a ⋅ 5 | a ∈ ℤ}, y ∈ {4 + b ⋅ 5 | b ∈ ℤ}}
=
{(3 + a ⋅ 5) + (4 + b ⋅ 5)   |   a ∈ ℤ, b ∈ ℤ}
=
{(3 + 4) + (a ⋅ 5) + (b ⋅ 5)   |   a ∈ ℤ, b ∈ ℤ}
=
{2 + 5 + (a ⋅ 5) + (b ⋅ 5)   |   a ∈ ℤ, b ∈ ℤ}
=
{2 + (1 + a + b) ⋅ 5   |   a ∈ ℤ, b ∈ ℤ}
=
{2 + c ⋅ 5 | c ∈ ℤ}
≡
2 + 5ℤ
≡
2
[link]  
Fact: The set ℤ/mℤ is closed under the operation represented by +.
[link]  
Fact: It is the case that ℤ/mℤ = {0,...,m-1} where 0,...,m-1 are congruence classes, and thus, |ℤ/mℤ| = m.
[link]  
Fact: The addition operation on congruence classes in ℤ/mℤ represented by + is commutative, associative, and has the additive identity 0 + mℤ (a.k.a., mℤ, or simply 0).
[link]  
Fact: The multiplication operation on congruence classes in ℤ/mℤ represented by ⋅ is commutative, associative, and has the multiplicative identity 1 + mℤ (a.k.a., 1).
property definition
ℤ/mℤ is closed under + ∀ x,y ∈ ℤ/mℤ,
    x + y ∈ ℤ/mℤ
+ is commutative on ℤ/mℤ ∀ x,y ∈ ℤ/mℤ,
    x + y ≡ y + x
+ is associative on ℤ/mℤ ∀ x,y,z ∈ ℤ/mℤ,
    (x + y) + z ≡ x + (y + z)
+ has a (left and right) identity 0 in ℤ/mℤ ∀ x ∈ ℤ/mℤ,
    0 + x ≡ x and x + 0 ≡ x
ℤ/mℤ has inverses with respect to + ∀ x ∈ ℤ/mℤ,
    (m - x) + x ≡ 0
ℤ/mℤ is closed under ⋅ ∀ x,y ∈ ℤ/mℤ,
    x ⋅ y ∈ ℤ/mℤ
⋅ is commutative on ℤ/mℤ ∀ x,y ∈ ℤ/mℤ,
    x ⋅ y ≡ y ⋅ x
+ is associative on ℤ/mℤ ∀ x,y,z ∈ ℤ/mℤ,
    (x ⋅ y) ⋅ z ≡ x ⋅ (y ⋅ z)
+ has a (left and right) identity 1 in ℤ/mℤ ∀ x ∈ ℤ/mℤ,
    1 ⋅ x ≡ x and x ⋅ 1 ≡ x
⋅ distributes across + in ℤ/mℤ ∀ x,y,z ∈ ℤ/mℤ,
    x ⋅ (y + z) ≡ (x ⋅ y) + (x ⋅ z)

In the rest of this subsection, we derive some familiar algebraic properties for congruence classes. We derive some of these properties from the properties of the divisibility predicate (i.e., for any x, y ∈ ℤ, x | y iff y/x ∈ ℤ). These properties will allow us to use algebra to solve equations involving congruence classes in ℤ/mℤ.
[link]  
Fact: Given an equation involving congruence classes, we are allowed to add the same value to both sides. In other words, for any congruence classes a, b, c ∈ ℤ/mℤ, a ≡ b implies a + c ≡ b + c:
a
≡
b (mod m)
a + c
≡
a + c
To see that this is true, we can simply appeal to algebraic facts about integers:
a
=
b
a + c
=
b + c
(a + c) mod m
=
(b + c) mod m
a + c
≡
b + c (mod m)
Thus, the two congruence classes contain the same elements, so they are equivalent.
[link]  
Fact: For any congruence classes a, b, c ∈ ℤ/mℤ, a ≡ b implies a - c ≡ b - c. We can adjust the argument for + in the following way:
a
=
b
a - c
=
b - c
(a - c) mod m
=
(b - c) mod m
a - c
≡
b - c (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.
[link]  
Fact: For any a, m ∈ ℤ, a mod m = 0 iff we have that m | a. Thus, the following are all equivalent (i.e., all three are true at the same time):
m
|
a
a mod m
=
0
a
≡
0 (mod m)
0
≡
a (mod m)
We can derive the fact that m | a iff a mod m = 0 as follows. If a mod m = 0 then by definition of mod we have:
a - ⌊ a/m ⌋ ⋅ m
=
0
a
=
⌊ a/m ⌋ ⋅ m
a / m
=
⌊ a/m ⌋
a / m
∈
ℤ
m
|
a
If m | a then by definition of m | a we have:
m
|
a
a / m
∈
ℤ
a / m
=
⌊ a/m ⌋
a
=
⌊ a/m ⌋ ⋅ m
a - ⌊ a/m ⌋ ⋅ m
=
0
a mod m
=
0
[link]  
Fact: For any a, b, c ∈ ℕ, if c|a then c|(a ⋅ b).

Because c|a, it must be that a/c ∈ ℤ. But then we have that:
(a ⋅ b) / c = (a / c) ⋅ b
Since (a / c) ∈ ℤ and b ∈ ℤ, (a / c) ⋅ b ∈ ℤ and (a ⋅ b) / c ∈ ℤ. Thus, c|(a ⋅ b).
[link]  
Fact: In ℤ/mℤ, Multiplying by the 0 + mℤ congruence class yields the 0 + mℤ congruence class. For any a, b, m ∈ ℕ, if a ≡ 0 (mod m) then a ⋅ b ≡ 0 (mod m).

We can show this as follows:
a
≡
0 (mod m)
m
|
a
m
|
(a ⋅ b)
a ⋅ b
≡
0 (mod m)
Thus, 0 ∈ ℤ/mℤ behaves with respect to multiplication over ℤ/mℤ much the same way that 0 ∈ ℤ behaves with respect to multiplication over ℤ.
[link]  
Example: For any a, b, m ∈ ℕ, it is not necessarily the case that just because a ⋅ b ≡ 0 (mod m), either a or b must be the congruence class 0 ∈ ℤ/mℤ. For example, let m = 6, a = 4, and b = 9. Then we have:
4 ⋅ 9
≡
0 (mod 6)
(2 ⋅ 2) ⋅ (3 ⋅ 3)
≡
0 (mod 6)
2 ⋅ (2 ⋅ 3) ⋅ 3
≡
0 (mod 6)
2 ⋅ 6 ⋅ 3
≡
0 (mod 6)
However, we have that:
6
∤
4
4
≢
0 (mod 6)
6
∤
9
9
≢
0 (mod 6)
Thus, the congruence class 0 ∈ ℤ/mℤ does not always behave the same way that 0 ∈ ℤ behaves.
[link]  
Fact (Euclid's lemma): For any a, b, p ∈ ℤ, if p is prime and p | (a ⋅ b), then it must be that p|a or p|b (or both).
[link]  
Fact: For any congruence classes a, b, c ∈ ℤ/pℤ, if c is not divisible by p then a ⋅ c ≡ b ⋅ c implies a ≡ b.

We can derive the above fact by using the following steps:
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
[link]  
Example: Solve the following equation for all possible congruence classes x ∈ ℤ/3ℤ:
6 ⋅ x
≡
0 (mod 3)
Since 6 ≡ 0 mod 3, we can rewrite the equation as follows:
0 ⋅ x
≡
0 (mod 3)
Thus, any congruence class x ∈ {0 + 3ℤ, 1 + 3ℤ, 2 + 3ℤ} is a solution to the equation.
[link]  
Example: Solve the following equation for all possible congruence classes x ∈ ℤ/5ℤ:
2 ⋅ x
≡
0 (mod 5)
We know that 2 ⋅ 0 ≡ 0 (mod 5), so we can rewrite the above by substituting the right-hand side of the equation:
2 ⋅ x
≡
2 ⋅ 0 (mod 5)
We can now cancel 2 on both sides of the equation using the cancellation law because 5 is prime and 2 ≢ 0 (mod 5):
x
≡
0 (mod 5)
Thus, the only solution is the single congruence class x = 0 + 5ℤ.
[link]  
Example: Solve the following equation for all possible congruence classes x ∈ ℤ/11ℤ:
3 ⋅ x + 5
≡
6 (mod 11)
We can begin by subtracting 5 from both sides:
3 ⋅ x
≡
1 (mod 11)
We can then see that 12 ≡ 1 (mod 11), so we can substitute 1 with 12 on the right-hand side:
3 ⋅ x
≡
12 (mod 11)
We can then rewrite 12 as 3 ⋅ 4:
3 ⋅ x
≡
3 ⋅ 4 (mod 11)
Since 11 is prime and 3 ≢ 0 (mod 11), we can cancel the 3 on both sides to solve the problem:
x
≡
4 (mod 11)
Thus, the only solution is the single congruence class x = 4 + 11ℤ.
[link]  
Example: Let a ∈ ℤ be any integer. Solve the following equation for all possible congruence classes x ∈ ℤ/7ℤ:
a + 3 ⋅ x
≡
6 - 6 ⋅ a (mod 7)
We can begin by adding 6 ⋅ a to both sides:
(a + 6 ⋅ a) + 3 ⋅ x
≡
6 (mod 7)
Now we can add a + 6 a to obtain 7 ⋅ a:
7 ⋅ a + 3 ⋅ x
≡
6 (mod 7)
We know that 7 ≡ 0 (mod 7), so we know that for any a ∈ ℤ, 7 ⋅ a ≡ 0 (mod 7). Thus, we can substitute the term 7 ⋅ a with 0:
0 + 3 ⋅ x
≡
6 (mod 7)
3 ⋅ x
≡
6 (mod 7)
3 ⋅ x
≡
3 ⋅ 2 (mod 7)
Since 7 is prime and 3 ≢ 0 (mod 7), we can cancel 3 on both sides:
x
≡
2 (mod 7)
Thus, the only solution is the single congruence class x = 2 + 7ℤ.
[link]  
Exercise: Solve the following equation for all possible congruence classes x ∈ ℤ/13ℤ:
4 ⋅ x − 2
≡
10 (mod 13)
[link]  
Exercise: Let a ∈ ℤ be any integer. Solve the following equation for all possible congruence classes x ∈ ℤ/19ℤ. Hint: notice that 17 + 19 = 36.
6 ⋅ x − 11
≡
6 (mod 19)

[link]  3.3. Congruence classes as permutations

For a prime p, the set of congruence classes ℤ/pℤ corresponds to a set of permutations.
[link]  
Fact: For any p ∈ ℕ, for any a ∈ {1,...,p-1}, if p is prime then the following is a permutation from {1,...,p-1} to ℤ/pℤ - {0} (the non-zero congruence classes in ℤ/pℤ):
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} }
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 ℤ/pℤ - {0} and we have that:
|{1,...,p-1}|
=
|ℤ/pℤ - {0}|
Thus, since R maps to at least p-1 distinct elements, and |ℤ/pℤ - {0}| has at most p-1 elements, R must map to every element in ℤ/pℤ - {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 ℤ/pℤ - {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 ℤ/pℤ.

[link]  3.4. Generating random numbers

[link]  
Example: 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 vi is the ith element in the sequence.

In this case, a relation R ⊂ ℕ × ℤ/mℤ 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 R0 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 R1 above more concisely:
R1
=
{(i, (0 + 2 ⋅ i) mod m) | i ∈ {0,...,m-1}}
Does R1 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 R1 is not injective, so the first requirement is not met when m is even.

Suppose we define R2 to be a variant of R1 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?
[link]  
Fact: If m is prime and b ∈ {2,...,m-1}, then R2 satisfies both requirements.

We know this is true because in this case, R is a permutation, so it satisfies Requirement 1. Furthermore, element v1 = b, so v is never the trivial sequence. Thus, Requirement 2 is satisfied.
[link]  
Algorithm: The following is one possible implementation of a simple random number generation algorithm.
  1. inputs: seed a ∈ ℕ and index i ∈ ℕ
    1. p := a prime number greater than i and a
    2. return a ⋅ i mod p
[link]  
Exercise: What are some drawbacks (or unresolved issues) with building random sequences by choosing a prime m and some a ∈ {2,...,m-1}?

[link]  3.5. Greatest common divisor and related facts

[link]  
Definition: For any two x, y ∈ ℤ, we define the greatest common divisor, denoted gcd(x,y), as the greatest integer z ∈ ℤ such that z|x and z|y. Equivalently, we can define it as the maximum of a set:
gcd(x,y)
=
max{ z | z ∈ ℤ, z|x, z|y}
We can also define it recursively (not that z|0 for all z ∈ ℤ because 0/z ∈ ℤ):
gcd(x,0)
=
x
gcd(x,y)
=
gcd(y, x mod y)
To see why the recursive definition of gcd 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.
[link]  
Fact: For any x ∈ ℤ, y ∈ ℤ, x|y iff gcd(x,y) = x.
[link]  
Definition: For any x ∈ ℤ, y ∈ ℤ, x and y are relatively prime, relative primes, and coprime iff gcd(x,y) = 1.
[link]  
Fact (Euclid's lemma generalization): For any a, b, c ∈ ℕ, if a | (b ⋅ c) and a and b are relatively prime, then it must be that a|c.
[link]  
Fact: For any a ∈ ℕ and m ∈ ℕ, if gcd(a,m) = 1, then {(i, (i ⋅ a) mod m) | i ∈ {0,...,m-1}} is a permutation.

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 this fact in which p was required to be prime, the fact that p is prime was not used in isolation; only the coprime relationship between p and a was required.
[link]  
Fact: If m, a ∈ ℕ and x, y ∈ ℤ/mℤ where gcd(a, m) = 1 (i.e., a and m are coprime), and suppose we have that:
x
≢
y (mod m)
Then it must be that:
a ⋅ x
≢
a ⋅ y (mod m)
Notice that we can prove the above by contradiction. If we instead suppose that a ⋅ x ≡ a ⋅ y (mod m), then because a and m are coprime, by Euclid's generalized theorem, we can canel a on both sides of the equation to obtain x ≡ y (mod m).
The generalization of Euclid's lemma and the above fact allows us to slightly improve the random number generating algorithm we introduced above by introducing an explicit upper bound on our random numbers that can be any integer, and by introducing a second component that makes the permutation appear more "random".
[link]  
Algorithm: The following is another variant of a simple random number generation algorithm.
  1. inputs: upper bound m ∈ ℕ, a seed k, and an index i ∈ {1,...,m-1}
    1. a := coprime a ∈ ℤ/mℤ s.t. a and m are coprime
    2. b := coprime b ∈ ℤ/mℤ s.t. b and m are coprime and a ≢ b
    3. return (a ⋅ i ⋅ bk) mod m
[link]  
Fact: For any m ∈ ℤ where m ≥ 2, gcd(m,m+1) = 1.

We can prove this fact 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 ∉ ℤ, so (b - a) ∉ ℤ. Since b-a ∈ ℤ, this is a contradiction, so it must be that gcd(m,m+1) = z = 1.
Notice that the above fact suggests one possible way to build a prime number generator: 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.
[link]  
Example: Solve the following problems using the algebraic facts you know about the gcd operation.
  • Find gcd(18,42).
  • Find gcd(21000, 2100).
  • For a positive even integer a ∈ ℤ, find gcd(a/2, a - 1).
  • Suppose that for some a ∈ ℤ/mℤ, the set {i ⋅ a mod m | i ∈ {1,...,m-1}} contains every number in the set {1,...,m-1}. What is gcd(a, m)?

[link]  3.6. Generating prime numbers

Many applications require the generation of new primes. We have already seen a simple example in which generating new random sequences required prime numbers. Another important class of applications with this requirement are cryptographic schemes and protocols. In this section, we consider the problem of generating prime numbers.
[link]  
Algorithm: There exists a simple algorithm that is guaranteed to generate a new prime number distinct from any of its inputs, but it is not efficient.
  1. inputs: set of primes {p1 ,... , pn}
    1. n := p1 ⋅ ... ⋅ pn + 1
    2. F := factors of n
    3. return any element in F
The above algorithm must return a new prime distinct from any of the primes p1 ,... , pn. To see why, consider the following:
P
=
p1 ⋅ ... ⋅ pn
gcd(P, P + 1)
=
1
There are two possibilities: P+1 is prime, or P+1 is not prime.
  • If P+1 is prime, then P > pi for all i ∈ {1,...,n}, so P+1 is a new prime.
  • If P+1 is not prime, it cannot share any factors with P since gcd(P, P + 1) = 1, so no factors of P+1 are in the set {p1 ,... , pn}. But it must have factors, so any of these factors will be different from the primes in the input set {p1 ,... , pn}.
Thus, the algorithm is a guaranteed method for generating new primes. It also constitutes a proof that there are infinitely many primes. Unfortunately, this algorithm is impractical because the new primes produced by it grow exponentially as the set of primes {p1 ,... , pn} is extended with new primes returned by the algorithm.
In practice, most algorithms that need to generate large primes for commercial applications simply choose a range 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.
[link]  
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 an 8-digit number chosen at random (here we are ignoring the details of what distribution is used) is prime are about:
4,780,406/((109 - 1) - 108) ≈ 5.5/100
[link]  
Algorithm: Suppose we defined the following algorithm for generating a prime with a d-digit representation.
  1. inputs: d ∈ ℕ
    1. do
      1. n := any number from {10d, ..., 10d+1-1}
      while n is not prime
    2. 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 ∈ ℕ 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,...,2n-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.
[link]  
Algorithm: Given the above considerations, we introduce a modified algorithm.
  1. inputs: d ∈ ℕ
    1. do
      1. n := any number from {10d, ..., 10d+1-1}
      while n is not probably prime
    2. 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.

[link]  3.7. Detecting probable prime numbers

In this subsection, we consider the problem of defining a very efficient algorithm to check whether a positive integer m ∈ ℕ is prime. In fact, the algorithm we consider will be detectors of some, but not all, composite numbers.
[link]  
Fact: For any n ∈ ℕ, n is composite iff n > 1 and it is not the case that n is prime.
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 description
actually a composite number
(this is not known at time of input)		 composite the input is composite true negative
actually a prime number
(this is not known at time of input)		 prime the input is prime true positive

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

algorithm input algorithm output meaning description
actually a composite number
(this is not known at time of input)		 composite the input is
definitely composite		 true negative
actually a composite number
(this is not known at time of input)		 probably prime the input is either
composite or prime		 false positive
actually a prime number
(this is not known at time of input)		 probably prime the input is either
composite or prime		 true positive
actually a prime number
(this is not known at time of input)		 composite impossible false negative
(we will not consider algorithms
that return such outputs)

Below is a comparison of the outputs of four possible probable prime algorithms on inputs in the range {2,...,10} ⊂ ℕ.

input
number		 perfect
algorithm		 perfect probable
prime algorithm		 less accurate
probable prime
algorithm		 very inaccurate
probable prime
algorithm
2 prime probably
prime		 probably
prime		 probably
prime
3 prime probably
prime		 probably
prime		 probably
prime
4 composite composite probably
prime		 probably
prime
5 prime probably
prime		 probably
prime		 probably
prime
6 composite composite composite probably
prime
7 prime probably
prime		 probably
prime		 probably
prime
8 composite composite probably
prime		 probably
prime
9 composite composite composite probably
prime
10 composite composite probably
prime		 probably
prime

[link]  
Algorithm: We now define our first algorithm for testing whether a number is probably prime.
  1. inputs: m ∈ ℕ, k ∈ ℕ
  2. repeat k times:
    1. a := a random number from {2,...,m-1}
    2. if a | m then return composite
  3. return probably prime
Notice that the above algorithm will never say that a prime number is actually composite. If it does not find a factor of m because it did not run for sufficiently many iterations, then it will indicate that m is probably prime. Thus, it will have no false negatives (i.e., an incorrect output indicating a prime number is composite).
[link]  
Algorithm: We now define another algorithm for testing whether a number is probably prime.
  1. inputs: m ∈ ℕ, k ∈ ℕ
  2. repeat k times:
    1. a := a random number from {2,...,m-1}
    2. if a | m then return composite
    3. if gcd(a,m) ≠ 1 then return composite
  3. return probably prime
The above algorithm is interesting because by using the gcd operation, we get more value out of each random number we try. In fact, the gcd operation runs in polynomial time but tells us if the intersection between the two sets of factors (the factors of a and the factors of m) contains any numbers. Checking this intersection using the naive approach would take exponential time.

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).
[link]  
Fact (Fermat's little theorem): For any p ∈ ℕ, for any a ∈ {0,...,p-1}, if p is prime then it is true that:
ap-1
≡
1 (mod p)
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 Fermat's little theorem.
[link]  
Fact: A number p ∈ ℕ is prime iff p > 1 and for all a ∈ {1,...,p-1}, ap-1 mod p = 1.
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.
[link]  
Definition: A number m ∈ ℕ is composite iff m > 1 and there exists a ∈ {1,...,m-1} such that am-1 mod m ≠ 1. In this case, a is a Fermat witness to the compositeness of m.
[link]  
Definition: If for composite m ∈ ℕ and a ∈ {1,...,m-1}, we have that am-1 mod m = 1, then a is a Fermat liar and m is a pseudoprime with respect to a.
[link]  
Algorithm (Fermat primality test): We now extend our algorithm. The following algorithm can be used to test whether a number is probably prime.
  1. inputs: m ∈ ℕ, k ∈ ℕ
  2. repeat k times:
    1. a := a number from {2,...,m-1}
    2. if a | m then return composite
    3. if gcd(a,m) ≠ 1 then return composite
    4. else if am-1 mod m ≠ 1 then return composite
  3. return probably prime
If m is a prime, the above algorithm will always return probably prime.
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.
[link]  
Fact: If for a composite m ∈ ℤ there is at least one Fermat witness a ∈ {2,...,m-1} such that gcd(a,m) = 1, then at least half of all a such that gcd(a,m) = 1 are Fermat witnesses.
Suppose that a is a Fermat witness and a1,...,an 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 an-1 mod m ≠ 1. Thus, (a ⋅ ai)n-1 mod m ≠ 1, so a ⋅ ai 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?
[link]  
Definition: For any m ∈ ℤ, if m has no coprime Fermat witnesses, then m is a Carmichael number, also known as a Fermat pseudoprime.
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
a | m a is a non-trivial factor of m,
so m is composite		 (# integers in {2,...,m-1} that are factors with m) / (m-2)
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

We can consider a particular example input for the primality test to see how each successive check in the algorithm can extract valuable information about whether the input is composite. The following table is for m = 15.

m = 15 and a = ... 2 3 4 5 6 7 8 9 10 11 12 13 14
a | m PP C PP C PP PP PP PP PP PP PP PP PP
gcd(a,m) ≠ 1 PP C PP C C PP PP C C PP C PP PP
am-1 mod m = ... 4 9 1 10 6 4 4 6 10 1 9 4 1

We can now summarize all the facts and algorithms we have introduced and how their relationships allow us to construct a prime number generator.
Euclid's
lemma
generalization		 ⇐ multiples of coprime
a in ℤ/mℤ are a
permutation
⇑
Fermat's
little
theorem		 random
number
generator		 ⇒ gcd(m,m+1) = 1
⇑ ⇑
greatest
common
divisor
algorithm		 ⇐ Fermat
primality
test		 ⇐ probable
prime
detector
⇑
probable
prime
generator

[link]  3.8. Assignment #2: Modular Arithmetic, Random Sequences, and Primes

In this assignment you will solve several equations, and you will define a collection of Python functions that will allow you to generate probable prime numbers of any size. You must submit a single Python source file named a2.py (submitted to the location hw2/a2.py). Please follow the gsubmit directions.

You may import the following library functions in your module (you may not need all these functions for this assignment depending on how you approach the problems, but they may be used):

from math import log, floor
from fractions import gcd
        
You may also use the built-in pow() function, which can compute modular exponents efficiently (as in, ak mod n can be written in Python as pow(a,k,n)). Your file may not import any other modules or employ any external library functions associated with integers and sets unless explicitly permitted to do so in a particular problem. Solutions to each of the programming problem parts below should be fairly concise. You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on the lecture notes and on each other; carefully consider whether you can use functions from the lecture notes, or functions you define in one part within subsequent parts.
  1. Solve the following equations using step-by-step equational reasoning, and list each step. You must list all solutions (zero or more) for x. You may need to use some automation to perform some of the steps. Your solutions for this problem should appear as comments, delimited using '''...''', in a2.py. You may use the = ascii character to represent the ≡ relational operator on congruence classes.
    1. 5 ⋅ x + 3 ≡ 6 (mod 11)
    2. 5 + 2 ⋅ x ≡ 8 (mod 10)
    3. 12 ⋅ x ≡ 3 (mod 4)
    4. 9 ⋅ x ≡ 81 (mod 587)
    5. 324637 ⋅ x ≡ 65109355834657447 (mod 1111111111111111111)
    6. 2213718098378353198 ⋅ x ≡ 1 (mod 65109355834657447)
  2. Implement the following Python functions. These will serve as helper functions for subsequent problems in this assignment.
    1. Implement a function digits() that takes a single positive integer argument n where n >= 0 and returns the number of digits in the decimal (base 10) representation of n.

      >>> digits(10)
      2
      >>> digits(10738019798475862873464857984759825354679201872)
      47
                    
    2. Implement a function changeRandomRange(r, n, min, max) that takes four positive integer arguments: r is a number in the range 1 to n (inclusive) that may have been generated by a random number generator; n is a positive integer; and min and max are two integer arguments (where min < max and max - min < n). Assuming r was generated randomly, the changeRandomRange() function should use r to return a random number in the range between min and max (inclusive).

      >>> changeRandomRange(43, 100, 20, 30)
      24
      >>> changeRandomRange(213, 1000, 400, 500)
      421
                    
  3. Implement the following Python functions. These functions take advantage of the generalized Euclid's lemma to make it possible to generate a random number that has a specified number of digits.
    1. Implement a function twoUnequalCoprimes() that takes a single positive integer argument d where d >= 1 and returns a pair containing two unequal numbers which are both coprime with each other, and which are both coprime with the number 10d + 1. Hint: use facts about coprime numbers and the fact that 10 = 2 ⋅ 5. Your implementation does not need to return exactly the same answers as you see in the example outputs. However, the output generated by your implementation must have the required properties.

      >>> twoUnequalCoprimes(10)
      (9765625, 1024)
      >>> twoUnequalCoprimes(100)
      (7888609052210118054117285652827862296732064351090230047702789306640625, 1267650600228229401496703205376)
                    
    2. Implement a function randByIndex() that takes two positive integer arguments: d represents the number of digits of the result, and i represents an index. You may assume d ≥ 1 and that 1 ≤ i ≤ 10d. The function must return the ith "random" number in a permutation of the numbers {1,...,10d}. Your implementation does not need to return exactly the same answers as you see in the example outputs. However, the output generated by your implementation must produce a permutation when used in a comprehension, as in the example below.

      >>> [randByIndex(1, i) for i in {1,2,3,4,5,6,7,8,9,10}]
      [8, 5, 2, 10, 7, 4, 1, 9, 6, 3]
      >>> [randByIndex(2, i) for i in range(1,101)]
      [47, 94, 40, 87, 33, 80, 26, 73, 19, 66,  12, 59, 5,  52, 99, 45, 
       92, 38, 85, 31, 78, 24, 71, 17, 64, 10,  57, 3,  50, 97, 43, 90, 
       36, 83, 29, 76, 22, 69, 15, 62, 8,  55,  1,  48, 95, 41, 88, 34, 
       81, 27, 74, 20, 67, 13, 60, 6,  53, 100, 46, 93, 39, 86, 32, 79,
       25, 72, 18, 65, 11, 58, 4,  51, 98, 44,  91, 37, 84, 30, 77, 23, 
       70, 16, 63, 9,  56, 2,  49, 96, 42, 89,  35, 82, 28, 75, 21, 68,
       14, 61, 7, 54]
                    
      The results returned by randByIndex() must represent a permutation as in the above examples. You should approach this problem by first determining an appropriate modulus m in terms of d, generating two distinct coprimes in ℤ/mℤ, and then using these two seeds along with facts about permutations to generate a "random" integer corresponding to one of the congruence classes in ℤ/mℤ.
  4. Implement a function probablePrime() that takes a single integer argument m where m >= 1. The function should return True if m is probably prime, and False otherwise. Your code should employ the Fermat primality test by generating some number of random witnesses in the appropriate range and using them to test the primality of m. You will need to determine what is a reasonable number of potential witnesses to test. Note that implementations that perform an exponentially large exhaustive search, even if the algorithm is mathematically correct, will not earn full credit.

    >>> probablePrime(31)
    True
    >>> probablePrime(107)
    True
    >>> probablePrime(230204771)
    True
    >>> probablePrime(10738019798475862873464857984759825354679201872)
    False
              
  5. Implement a function makePrime() that takes a single integer argument d where d >= 1 and returns a probably prime number that has d digits. Your implementation should be sufficiently efficient to produce an output for d = 100 in a reasonably short amount of time. Note that implementations that perform an exponentially large exhaustive search, even if the algorithm is mathematically correct, will not earn full credit.

    >>> makePrime(2)
    47
    >>> makePrime(100)
    3908330587430939367983163094172482420761782436265274101479718696329311615357177668931627057438461519
              

[link]  3.9. Chinese remainder theorem (CRT) and applications

In previous sections we presented facts that allowed us to solve certain individual equations with solution spaces corresponding to sets of congruence classes such as ℤ/mℤ. It is also possible to solve systems of equations over sets of congruence classes.
[link]  
Theorem (Chinese remainder theorem): The Chinese remainder theorem (CRT) states that given primes p1,...,pk ∈ ℕ, for any a1,...,ak ∈ ℤ there exists a solution x ∈ ℤ to the system of equations:
x mod p1
=
a1
⋮
x mod pk
=
ak
We can also state the theorem in terms of congruences. Given primes p1,...,pk ∈ ℕ, for any a1 ∈ ℤ/p1ℤ, ..., ak ∈ ℤ/pkℤ there exists a unique solution x ∈ ℤ/(p1 ⋅ ... ⋅ pk)ℤ to the system of equations:
x
≡
a1 (mod p1)
 ⋮
x
≡
ak (mod pk)
In other words, all the solutions to the first system above are from the same congruence class of ℤ/(p1 ⋅ ... ⋅ pk)ℤ. The theorem applies even if p1,...,pk are only relatively prime or coprime.
[link]  
Example: Solve the following system of equations for the unique solution x ∈ ℤ/10ℤ:
x
≡
3 (mod 5)
x
≡
0 (mod 2)
We can list the integers corresponding to each congruence class and find the unique integer in {0, ..., 2 ⋅ 5 - 1} that is in both lists:
3 + 5ℤ
=
{..., 3, 8, ...}
0 + 2ℤ
=
{..., 0, 2, 4, 6, 8, ...}
Since 8 is in both of the above congruence classes, we have that:
x
≡
8 (mod 10)
The Chinese remainder theorem has many applications in a variety of contexts. In this section we present the following algorithms, which all rely on the ability to solve systems of equations involving congruence classes.
efficient
modular
arithmetic
⇓
Chinese
remainder
theorem		 ⇐ CRT solver ⇐ range
ambiguity
resolution
⇑
Shamir secret
sharing protocol
[link]  
Fact: Given a, a ∈ ℤ, if a + b ∈ {0,...,m-1}, then it is true that
(a mod m) + (b mod m)
=
(a + b) mod m
Likewise, if a ⋅ b ∈ {0,...,m-1}, then it is true that
(a mod m) ⋅ (b mod m)
=
(a ⋅ b) mod m
[link]  
Example (efficient modular arithmetic): Suppose we want to perform a large number of arithmetic operations in sequence. The operations could be specified as a program that operates on a single variable and performs a sequence of variable updates that correspond to arithmetic operations, such as the example below.
x
:=
3
x
:=
x + 6
x
:=
x ⋅ 2
x
:=
x − 17
x
:=
x + 1
⋮
Suppose that over the course of the computation, x might become very large (e.g., 0 ≤ x ≤ 21000000000). However, we have an additional piece of information: once the sequence of operations ends, we know that 0 ≤ x < 1024.

Given our additional information about the range of the final output, we do not need to store 1000000000 bit numbers in order to perform the computation and get a correct result. It is sufficient to instead perform all the operations in ℤ/1024ℤ:
x
:=
3 mod 1024
x
:=
(x + 6) mod 1024
x
:=
(x ⋅ 2) mod 1024
x
:=
(x − 17) mod 1024
x
:=
(x + 1) mod 1024
⋮
The above will produce the same result in ℤ/1024ℤ, and we will only need 1024 bits at any single point in the computation to store each intermediate result.
[link]  
Example (efficient distributed modular arithmetic): Suppose that, as in the previous example, we want to perform a large number of arithmetic operations in sequence on large integers (e.g., in ℤ/270ℤ). However, our resources may be limited. For example, we may only have a collection of processors that can each perform arithmetic on relatively small integers (e.g., in ℤ/28ℤ). Is it possible for us to perform this computation using these processors, and is it possible for us to speed up the computation by running the processors in parallel? We may assume that a single arithmetic computation in ℤ/2nℤ running on a single processor takes n time steps to perform.

Suppose we have ten processors that can perform arithmetic computations in ℤ/28ℤ or any smaller space (such as ℤ/27ℤ). We can approach this problem by choosing a collection of primes p1,...,p10 such that 27 < pi < 28, which implies that:
p1 ⋅ ... ⋅ p10
>
27 ⋅ ... ⋅ 27
≥
270
We can then perform the sequence of computations modulo each of the primes pi to obtain ten results a1, ..., a10. Once we obtain the results, we can apply the Chinese remainder theorem to obtain x:
x
=
a1 mod p1
⋮
x
=
a10 mod p10
Since the product of the primes is greater than 270, the unique solution x to the above system of equations will be the correct result of the computation. Since the processors were running in parallel, the computation was about 10 times faster than it would have been if we had performed the computation in ℤ/270ℤ (or in sequence using a single processor that can perform computations in ℤ/28ℤ).
[link]  
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 p1,..., pn 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 ℤ/piℤ 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 a1,...,an, 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 < p1 ⋅ ... ⋅ pn.
[link]  
Protocol (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 ∈ ℤ be the secret information. Collect a set of randomly chosen relatively prime integers M = {m1,...,mN} 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 mi. 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 ∈ ℤ, and then randomly select integers c1,...,ck ∈ ℤ/mℤ. 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.

[link]  3.10. Solving systems of equations with CRT solutions using multiplicative inverses

The Chinese remainder theorem guarantees that a unique solution exists to particular systems of equations involving congruence classes. But can these solutions be computed automatically and efficiently? In fact, they can. However, computing such solutions requires the ability to compute multiplicative inverses in ℤ/mℤ.
greatest
common
divisor
algorithm		 Fermat's
little
theorem		 Euler's
theorem
⇑ ⇑ ⇑
Bézout's
identity		 ⇐ extended
Euclidean
algorithm		 ⇐ algorithm for
finding
multiplicative
inverses		 ⇒ Euler's
totient
function φ
⇑
Chinese
remainder
theorem		 ⇐ CRT solver
for two
equations
⇑
induction ⇐ CRT solver
for n
equations
To better understand multiplicative inverses, we first review the definition of an additive inverse.
[link]  
Fact: For any m ∈ ℕ, every element in the set ℤ/mℤ has an inverse with respect to addition defined over ℤ/mℤ (i.e., an additive inverse). Consider any x ∈ ℤ/mℤ. Then p − x ∈ ℤ/mℤ and
x + (p − x)
≡
p (mod p)
 ≡
0
We denote by −x the additive inverse of x.
[link]  
Example: What is the additive inverse of 2 ∈ ℤ/5ℤ?

The additive inverse is 5 − 2 = 3, since 2 + 3 mod 5 = 0.
There is more than one way to compute multiplicative inverses; in this subsection, we will present facts that will help us build algorithms for computing multiplicative inverses, and then we will use these algorithms to build a solver for systems of equations that have solutions according to CRT.
[link]  
Definition: Given a positive integer m ∈ ℕ and a congruence classes x ∈ ℤ/mℤ, suppose there exists a congruence class y ∈ ℤ/mℤ such that:
x ⋅ y
≡
1 (mod m)
Then we say that y is the multiplicative inverse of x in ℤ/mℤ. We usually denote the multiplicative inverse of x as x-1 (as is often done for multiplicative inverses over the integers, i.e., 2-1 = 1/2).
[link]  
Fact: Let p ∈ ℕ be a prime number, and let a ∈ ℤ/pℤ. Then we know by Fermat's little theorem that:
ap-1
≡
1 (mod p)
But we can factor the above to get:
a ⋅ ap-2
≡
1 (mod p)
Thus, the multiplicative inverse of a ∈ ℤ/pℤ is:
a-1
≡
ap-2 (mod p)
Note that:
a ⋅ a-1
≡
a ⋅ ap-2 (mod p)
≡
ap-1
≡
1
[link]  
Example: What is the multiplicative inverse of 2 ∈ ℤ/5ℤ? We can compute it as follows:
2-1
≡
25-2 (mod 5)
≡
23
≡
8
≡
3
We can check to confirm that this is true:
2 ⋅ 3
≡
6 (mod 5)
≡
1
How is computing multiplicative inverses related to solving systems of equations that have solutions according to CRT? Consider the following example.
[link]  
Example: Suppose we want to solve the following system of equations:
x
≡
1 (mod 5)
x
≡
0 (mod 4)
The above two equations are constraints on the integers that can be in the congruence class x. One way to state these constraints in English is: "x must be a multiple of 4, and x must be in 1 + 5ℤ". But then we can rewrite the above as a single equation:
4 ⋅ y
≡
1 (mod 5)
Then, we only need to solve for y, and let x = 4 ⋅ y. What is y? The above equation implies that y is the multiplicative inverse of 4 in ℤ/5ℤ. Thus, we can compute:
y
≡
4-1 (mod 5)
 ≡
45-2 (mod 5)
 ≡
43
≡
64
≡
4
Thus, the multiplicative inverse of 4 in ℤ/5ℤ is itself. Plugging y into x = 4 ⋅ y gives us 16. Thus, we know by CRT that we have our unique solution in ℤ/(4 ⋅ 5)ℤ = ℤ/20ℤ:
x
≡
16 (mod 20)
The above example suggests that we can solve certain pairs of equations with CRT solutions if one of the congruence classes is 0 and the other 1. What if the other congruence class is not 1?
[link]  
Example: Suppose we know that the multiplicative inverse of 3 ∈ ℤ/5ℤ is 2. Then we have that 2 ⋅ 3 ≡ 1 (mod 5). We can use this information to help us solve the following equation:
3 ⋅ x
≡
4 (mod 5)
Notice that:
3 ⋅ x
≡
4 ⋅ 1 (mod 5)
If the above really has a solution, then we can factor out 4 and cancel it on both sides using Euclid's lemma (since 4 and 5 are coprime). We do so by setting x = 4 ⋅ y and writing:
3 ⋅ (4 ⋅ y)
≡
4 ⋅ 1 (mod 5)
4 ⋅ (3 ⋅ y)
≡
4 ⋅ 1 (mod 5)
3 ⋅ y
≡
1 (mod 5)
We know that y = 2 because 2 is the multiplicative inverse of 3 in ℤ/5ℤ (in other words, 3-1 ≡ 2 (mod 5)). Then we have that:
y
≡
2 (mod 5)
x
≡
4 ⋅ y
x
≡
8
x
≡
3
Thus, x ≡ 3 is a solution to our equation. We can confirm this:
3 ⋅ 3
≡
4 (mod 5)
9
≡
4 (mod 5)
[link]  
Example: Note that what we actually did in the previous example when we cancelled 4 on both sides is that we multiplied both sides by the multiplicative inverse of 4. Suppose we knew that the multiplicative inverse of 4 ∈ ℤ/5ℤ is 4. We can use this information to help us solve the following equation:
3 ⋅ x
≡
4 (mod 5)
We multiply both sides by 4-1:
4-1 ⋅ 3 ⋅ x
≡
4-1 ⋅ 4 (mod 5)
4 ⋅ 3 ⋅ x
≡
4 ⋅ 4
12 ⋅ x
≡
16
2 ⋅ x
≡
1
Notice that we have now reduced the problem to finding the multiplicative inverse of 2. We know that 2-1 ≡ 3 (mod 5), so we now know that:
x
≡
2-1 (mod 5)
≡
3
[link]  
Example: Suppose we want to solve the following system of equations:
x
≡
0 (mod 11)
x
≡
4 (mod 7)
The above equations require that x ∈ ℤ/77ℤ be divisible by 11, and that x ∈ 4 + 7ℤ. Since x is divisible by 11, it is a multiple of 11, so we want to find x = 11 ⋅ y where:
11 ⋅ y
≡
4 (mod 7)
To solve the above, it is sufficient to multiply both sides of the equation by 11-1 (mod 7). Since 11 ≡ 4 (mod 7), it is sufficient to find 4-1 (mod 7).
11-1
≡
4-1 (mod 7)
≡
47-2
≡
45
≡
1024
≡
2
Thus, we can multiply both sides to obtain:
11 ⋅ y
≡
4 (mod 7)
11-1 ⋅ 11 ⋅ y
≡
11-1 ⋅ 4
y
≡
2 ⋅ 4
y
≡
8
y
≡
1
Thus, we have:
x
≡
11 ⋅ y (mod 77)
x
≡
11 ⋅ 1
x
≡
11 (mod 77)
[link]  
Fact: Suppose we are given two unequal prime numbers p, q ∈ ℕ, and the following two equations:
x
≡
1 (mod p)
x
≡
0 (mod q)
This implies x must be a multiple of q, so rewrite x = q ⋅ y. Then we have:
q ⋅ y
≡
1 (mod p)
Thus, we can solve for q-1 by computing:
q-1
≡
qp-2 (mod p)
Then we have:
q-1 ⋅ q ⋅ y
≡
q-1 ⋅ 1 (mod p)
y
≡
q-1 (mod p)
x
≡
q ⋅ y (mod (p ⋅ q))
Notice that q ⋅ y is indeed a solution to the original system because:
q ⋅ y
≡
1 (mod p)
    
     because y ≡ q-1 (mod p);
q ⋅ y
≡
0 (mod q)
    
     because q ⋅ y is a multiple of q.
[link]  
Fact: Suppose we are given two unequal prime numbers p, q ∈ ℕ, and the following two equations where a ∈ ℤ/pℤ:
x
≡
a (mod p)
x
≡
0 (mod q)
This implies x must be a multiple of q and a multiple of a, so rewrite x = a ⋅ q ⋅ y. Then we have:
a ⋅ q ⋅ y
≡
a (mod p)
As in the previous fact, the above works if y = q-1 (mod p), so compute:
y
=
q-1 (mod p)
x
≡
a ⋅ q ⋅ y (mod (p ⋅ q))
Notice that a ⋅ q ⋅ y is indeed a solution to the original system because:
a ⋅ q ⋅ y
≡
a (mod p)
    
     because y ≡ q-1 (mod p);
a ⋅ q ⋅ y
≡
0 (mod q)
    
     because a ⋅ q ⋅ y is a multiple of q.
[link]  
Fact: Suppose we are given two unequal prime numbers p, q ∈ ℕ, and the following two equations where a ∈ ℤ/pℤ and b ∈ ℤ/qℤ:
x
≡
a (mod p)
x
≡
b (mod q)
Suppose we instead solve the following two systems:
x1
≡
a (mod p)
x1
≡
0 (mod q)
x2
≡
0 (mod p)
x2
≡
b (mod q)
Notice that x1 + x2 is a solution to the original system because:
x1 + x2
≡
x1 + 0 (mod p)
≡
a + 0 (mod p)
≡
a (mod p)
x1 + x2
≡
0 + x2 (mod q)
≡
0 + b (mod q)
≡
b (mod q)
We know how to solve the above two systems separately:
x1
≡
a ⋅ q ⋅ q-1 (mod (p ⋅ q))
x2
≡
b ⋅ p ⋅ p-1 (mod (p ⋅ q))
Thus, we have the solution to the original system:
x
≡
x1 + x2 (mod (p ⋅ q))
We have shown that we can solve a system of equations with a solution according to CRT if the moduli in the equations are both prime. What if the moduli are merely coprime? So far, we only needed a way to compute multiplicative inverses of numbers modulo a prime, and Fermat's little theorem was sufficient for this purpose. However, if the moduli are not prime, we need some other method to compute multiplicative inverses.
[link]  
Fact: For any m ∈ ℕ, an x ∈ ℤ/mℤ has an inverse with respect to multiplication defined over ℤ/mℤ (i.e., a multiplicative inverse) iff gcd(x,m) = 1.
[link]  
Fact (Bezout's identity): For any two integers x ∈ ℤ, y ∈ ℤ where x ≠ 0 or y ≠ 0, let z = gcd(x,y). Then there exist a ∈ ℤ and b ∈ ℤ such that:
a ⋅ x + b ⋅ y
=
z
[link]  
Fact: For any two integers x ∈ ℤ, y ∈ ℤ where x ≠ 0 or y ≠ 0, and gcd(x,y) = 1, there exist a ∈ ℤ and b ∈ ℤ such that:
a ⋅ x + b ⋅ y
=
1
This fact is a special case of Bézout's identity (i.e., the case in which gcd(x,y) = 1).
[link]  
Example: Suppose we have s,t ∈ ℤ such that:
5 ⋅ s + 3 ⋅ t
=
1
We can then do the following:
− 5 ⋅ t + (5 ⋅ s + 3 ⋅ t) + 5 ⋅ t
=
1
(5 ⋅ s − 5 ⋅ t) + (3 ⋅ t + 5 ⋅ t)
=
1
5 ⋅ (s − t) + 8 ⋅ t
=
1
Thus, we have converted a instance of Bézout's identity for 5 and 3 into an instance of Bézout's identity for 5 and 8.

We can repeat the above as many times as we want. Suppose we instead want Bézout's identity for 3 and 13. We can do the following:
− 5 ⋅ 2 ⋅ t + (5 ⋅ s + 3 ⋅ t) + 5 ⋅ 2 ⋅ t
=
1
(5 ⋅ s − 5 ⋅ 2 ⋅ t) + (3 ⋅ t + 5 ⋅ 2 ⋅ t)
=
1
5 ⋅ (s − 2 ⋅ t) + 13 ⋅ t
=
1
[link]  
Fact: For any two integers a, b, s, t ℤ, suppose we have that:
a ⋅ s + b ⋅ t
=
1
Let us assume that a > b and that a mod b = r (in other words, for some k,
a mod b
=
r
b ⋅ k + r
=
a
Then we have that:
a ⋅ s + b ⋅ t
=
1
− b ⋅ k ⋅ s + (a ⋅ s + b ⋅ t) + b ⋅ k ⋅ s
=
1
(a ⋅ s − b ⋅ k ⋅ s) + (b ⋅ (t + k ⋅ s))
=
1
(a − b ⋅ k) ⋅ s + b ⋅ (t + k ⋅ s)
=
1
r ⋅ s + b ⋅ (t + k ⋅ s)
=
1
(a mod b) ⋅ s + b ⋅ (t + k ⋅ s)
=
1
Thus, for any instance of Bézout's identity for a and b and a > b, there must exist an instance of Bézout's identity for a mod b and b.
The above fact suggests that if we want to find the s and t coefficients for an equation a ⋅ s + b ⋅ t = 1 given a > b, we should try finding Bézout's identity for a mod b and b. But notice that:
a mod b
<
b
The above implies that the problem of finding the coefficients for an instance of Bézout's identity can be reduced to a smaller version of the problem: find Bézout's identity for a mod b and b can then be reduced further to finding b mod (a mod b) and a mod b. At this point, we have a strictly smaller instance of the problem:
a mod b
<
b
<
a
b mod (a mod b)
<
b
<
a
Thus, we can use recursion; the recursive algorithm that solves this problem is called the extended Euclidean algorithm, and is a modification of the recursive algorithm that computes the gcd of two numbers.
[link]  
Algorithm (extended Euclidean algorithm): The collection of equations considered in the Chinese remainder theorem can be solved constructively (i.e., in a way that provides a concrete solution and not just a proof that a solution exists) by applying an extended version of the greatest common divisor algorithm. We provide the definition of the algorithm below.
  1. extended Euclidean algorithm: x ∈ ℤ, y ∈ ℤ
    1. if y = 0
      1. (s,t) := (1, 0)
      2. return (s,t)
    2. otherwise
      1. (s,t) := extended Euclidean algorithm(y, x mod y)
      2. return (t, s - (⌊ x/y ⌋ ⋅ t) )
Given two inputs x ∈ ℤ, y ∈ ℤ, the extended Euclidean algorithm returns two integers u, v such that
u ⋅ x + v ⋅ y
=
gcd(x,y)
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).
[link]  
Example: Suppose we want to find the multiplicative inverse of 49 in ℤ/100ℤ and the multiplicative inverse of 100 in ℤ/49ℤ. We run the extended Euclidean algorithm on the inputs 49 and 100 to obtain the following instance of Bézout's identity:
(-24) ⋅ 100 + 49 ⋅ 49
=
1
We can use the above to find the multiplicative inverse of 49 in ℤ/100ℤ:
(-24) ⋅ 100 + 49 ⋅ 49
=
1
(-24) ⋅ 100 + 49 ⋅ 49
≡
1 (mod 100)
49 ⋅ 49
≡
1 (mod 100)
Thus, 49-1 = 49 in ℤ/100ℤ. We can also find the multiplicative inverse of 100 in ℤ/49ℤ (also known as 2 ∈ ℤ/49ℤ):
(-24) ⋅ 100 + 49 ⋅ 49
=
1
(-24) ⋅ 100 + 49 ⋅ 49
≡
1 (mod 49)
-24 ⋅ 100
≡
1 (mod 49)
25 ⋅ 100
≡
1 (mod 49)
Thus, 100-1 = 25 in ℤ/49ℤ.
[link]  
Example: Suppose we want to solve the following system:
x
≡
23 (mod 100)
x
≡
31 (mod 49)
We use the extended Euclidean algorithm to find that:
(-24) ⋅ 100 + 49 ⋅ 49
=
1
This tells us that −24 is the inverse of 100 in ℤ/49ℤ and that 49 is the inverse of 49 in ℤ/100ℤ. Thus, to build 31 in ℤ/49ℤ, we need:
31
≡
1 ⋅ 31 (mod 49)
≡
(100 ⋅ 100-1) ⋅ 31
≡
(100 ⋅ -24) ⋅ 31
To build 23 in ℤ/100ℤ, we need:
23
≡
1 ⋅ 23 (mod 100)
≡
(49 ⋅ 49-1) ⋅ 23
≡
(49 ⋅ 49) ⋅ 23
Then the solutions to the system are in the congruence class:
x
≡
(100 ⋅ -24) ⋅ 31 + (49 ⋅ 49) ⋅ 23 (mod (100 ⋅ 49))
≡
-19177 mod 4900
≡
423
[link]  
Algorithm: Suppose we are given a collection of equations of the following form such that m1,...,mk are all pairwise coprime.
x
≡
a1 (mod m1)
 ⋮
x
≡
ak (mod mk)
Let C be the set of these equations, where Ci is the ith equation. The following algorithm can be used to find a solution for this system of equations.
  1. solve system of equations: C is a set of constraints x ≡ ai mod mi
    1. while |C| > 1
      1. remove two equations Ci and Cj from C and solve them to obtain a new equation x ≡ c (mod mi ⋅ mj)
      2. add the new equation to C
    2. return the one equation left in C

[link]  3.11. More practice with CRT

[link]  
Example: Solve the following equation for x ∈ ℤ/5ℤ by multiplying both sides by the appropriate multiplicative inverse:
3 ⋅ x
≡
2 (mod 5)
[link]  
Example: Solve the following system of equations for x ∈ ℤ/35ℤ by finding multiplicative inverses of 5 ∈ ℤ/7ℤ and 7 ∈ ℤ/5ℤ:
x
≡
4 (mod 5)
x
≡
2 (mod 7)
[link]  
Example: Suppose you know that 7-1 ≡ 3 (mod 10). Solve the following system of equations:
x
≡
0 (mod 2)
x
≡
1 (mod 5)
x
≡
3 (mod 7)
We first solve the first two equations. We know x must be a multiple of 2 that is in 1 + 5ℤ. Thus, we set x = 2 ⋅ y and we solve:
x
≡
1 (mod 5)
2 ⋅ y
≡
1 (mod 5)
Then we know that:
y
≡
2-1 (mod 5)
≡
25-2
≡
23
≡
8
≡
3
Thus, x ≡ 2 ⋅ 3 ≡ 6 (mod (2 ⋅ 5)). This leaves two equations:
x
≡
6 (mod 10)
x
≡
3 (mod 7)
We first find 10-1 (mod 7):
10-1
≡
107-2 (mod 7)
≡
105
 ≡
5
We now have 10-1 ≡ 5 (mod 7) and 7-1 ≡ 3 (mod 10), so now we can express 6 as a multiple of 7 in ℤ/10ℤ, and we can express 3 as a multiple of 10 in ℤ/7ℤ:
x
≡
6 (mod 10)
≡
6 ⋅ 1
≡
6 ⋅ (7 ⋅ 7-1)
x
≡
3 (mod 7)
≡
3 ⋅ 1
≡
3 ⋅ (10 ⋅ 10-1)
Thus, we add these two terms to obtain our solution in ℤ/(7 ⋅ 10)ℤ:
x
≡
6 ⋅ (7 ⋅ 7-1) + 3 ⋅ (10 ⋅ 10-1) (mod 70)
≡
6 ⋅ (7 ⋅ 3) + 3 ⋅ (10 ⋅ 5)
≡
6 ⋅ 21 + 3 ⋅ 50
≡
126 + 150
≡
276
≡
66
[link]  
Example: Suppose we have a single processor that can perform arithmetic operations (addition, subtraction, multiplication, and modulus) on integers that can be represented with at most 11 bits (211 = 2048). On this processor, a single arithmetic operation can be performed in 11 time steps. We also have three other processors that can perform arithmetic on integers that can be represented with at most 4 bits (24 = 16). Each of these processors can perform an arithmetic operation on 4-bit integers in 4 time steps.

For example, suppose we want to perform 1000 arithmetic operations on 11-bit integers. Using a single processor, this would require:
1000 ⋅ 11 = 11,000 time steps
If we use three coprime numbers 13, 14, and 15, and we use each of the three 4-bit processors to perform these operations modulo 13, 14, and 15 in parallel, 1000 operations would require:
1000 ⋅ 4 = 4,000 time steps
Note that 13 ⋅ 14 ⋅ 15 = 2730, and that 2730 > 2048, so:
13 ⋅ 14 ⋅ 15
>
211
Suppose it takes 1400 time steps to solve a system of three congruence equations of the following form:
x
≡
a (mod 13)
x
≡
b (mod 14)
x
≡
c (mod 15)
If we want to perform the computations as quickly as possible and we can use either the 11-bit processor or the three 4-bit processors, how many operations k would we need to perform before we decided to switch from the the 11-bit processor to the 4-bit processors?
To solve this problem, we can first write down two function describing the time cost of the two strategies for k operations:
f(k)
=
k ⋅ 11
g(k)
=
k ⋅ 4 + 1400
Notice that f(1) < g(1), so if we only wanted to perform k = 1 operation, we would prefer to use the 11-bit processor. The point at which we would want to switch would be when f(k) ≥ g(k), so we can find the point at which the two functions intersect:
f(k)
≥
g(k)
k ⋅ 11
≥
k ⋅ 4 + 1400
k ⋅ 7
≥
1400
k
 ≥
200
Thus, if k ≥ 200, we want to use the 4-bit processors.
[link]  
Example: Suppose we are using echolocation to measure the distance to a wall that is at most 15 distance units away. We have two devices that emit sounds at two different frequencies. One device emits sound every 3 seconds, while the other device emits a sound every 11 seconds. Suppose we hear the following:
  • the device that emits a sound every 3 seconds hears a response 2 seconds after each time it emits a sound;
  • the device that emits a sound every 11 seconds hears a response 4 seconds after each time it emits a sound.
If sound travels one distance unit per second, how far away is the wall?
[link]  
Example: Suppose Alice, Bob, and Eve are using the Shamir secret sharing protocol to store a combination for a lock; all three participants would need to work together to retrieve the secret lock combination in ℤ/60ℤ. They are each given the following equations:
Alice:
    
x
≡
1 (mod 3)
Bob:
    
x
≡
3 (mod 4)
Eve:
    
x
≡
2 (mod 5)
  1. What is the lock combination?
  2. The lock only permits anyone to try two incorrect combinations before locking down completely and becoming inaccessible. Suppose Eve has a chance to steal either Bob's secret information or Alice's secret information, but she can only choose one. Whose information should she steal in order to unlock the lock?
[link]  
Example: Suppose we want to store a number n between 0 and 500,000 on a collection of 5-bit memory regions. However, we want to make sure that if any one of the memory regions is turned off, we can still recover the number exactly, without any missing information or errors. How many memory regions will we need to use? Note that 323 = 32,768 and 324 = 1,048,576.
We will need five memory regions. Suppose we choose five coprime numbers less than or equal to 25 = 32: 25,27,29,31, and 32. Note that any product of four of these numbers is greater than 500,000 because 25 ⋅ 27 ⋅ 29 ⋅ 31 = 606,825. Then with five 5-bit memory regions, we can store each of the following five values in one region:
n mod 25
n mod 27
n mod 29
n mod 31
n mod 32
If any of the above values are lost, it is still possible to recover n by solving a system with four equations. In the worst case, the product of the moduli would be 606,825 > 500,000.
[link]  
Example: Suppose we make the following simplifications: for every t years,
  • when the Earth revolves around the sun, it travels a circumference of 1 unit, at a rate of 1 ⋅ t (once per year);
  • when the asteroid Ceres revolves around the sun, it travels a circumference of 5 units;
  • when the planet Jupiter revolves around the sun, it travels a circumference of 11 units.
Suppose that on June 21st, 2000, the Earth, Ceres, and Jupiter all align (i.e., one can draw a straight line through all three). Next, suppose that it is June 21st of some year between 2000 and 2055. At this time, there is no alignment. However, Jupiter aligned with earth on June 21st two years ago, and Ceres aligned with Earth on June 21st three year ago. What year is it?

[link]  3.12. Euler's totient function, Euler's theorem, and applications

[link]  
Definition: For any input m ∈ ℕ, define Euler's totient function φ by:
φ(m)
=
|{k | k ∈ {1,...,m}, gcd(k,m) = 1}|
[link]  
Example: Compute φ(15).
φ(15)
=
|{k | k ∈ {1,...,15}, gcd(k,15) = 1}|
=
|{1,2,4,7,8,11,13,14}|
=
8
[link]  
Example: Suppose p ∈ ℕ is a prime number. What is φ(p)?

φ(p)
=
|{k | k ∈ {1,...,p}, gcd(k,p) = 1}|
=
|{1,2,3,...,p-1}|
=
p-1
[link]  
Example: What is φ(15)?
φ(15)
=
|{k | k ∈ {1,...,15}, gcd(k,15) = 1}|
=
15 - |{k | k ∈ {1,...,15}, gcd(k,15) ≠ 1}|
=
15 - |{3,6,9,12,15} ∪ {5,10,15}|
=
15 - |{3,6,9,12}| - |{5,10}| - |{15}|
=
15 - (5-1) - (3-1) - 1
=
15 - 5 - 3 + 1 + 1 - 1
=
15 - 5 - 3 + 1
=
(3 ⋅ 5) - 5 - 3 + 1
=
(3-1) ⋅ (5-1)
=
2 ⋅ 4
=
8
[link]  
Fact: For any x ∈ ℕ and y ∈ ℕ, if gcd(x,y) = 1 then:
φ(x) ⋅ φ(y)
=
φ(x ⋅ y)
[link]  
Example: Suppose p ∈ ℕ and q ∈ ℕ are prime numbers. What is φ(p ⋅ q)?
φ(p ⋅ q)
=
φ(p) ⋅ φ(q)
=
(p-1) ⋅ (q-1)
[link]  
Fact: For any prime p ∈ ℕ, we have that:
φ(pk)
=
pk - pk-1
[link]  
Fact: For any a ∈ ℕ and m ∈ ℕ, if am-1 mod m = 1 then:
am-1 mod m
=
1
am-1
=
1 + k ⋅ m
1
=
gcd(1 + k ⋅ m, k ⋅ m)
=
gcd(am-1, k ⋅ m)
=
gcd(a, k ⋅ m)
=
gcd(a, m)
Thus, a and m are coprime.
[link]  
Example: Suppose m ∈ ℕ is a Carmichael number. At most how many Fermat liars does m have?
[link]  
Fact: We can use φ to provide a formula for the probability that the Fermat primality test will detect that a Carmichael number m ∈ ℕ is actually composite. It is approximately:
(m - φ(m)) / m
To be more precise (since we do not check 0 or 1 in our actual implementation), it is:
((m - 3) - φ(m)) / (m - 3)
Unfortunately, Euler's totient function does not in general have a better upper bound than f(m) = m.
[link]  
Example: How many elements of ℤ/mℤ have a multiplicative inverse in ℤ/mℤ? Since an x ∈ ℤ/mℤ has an inverse iff gcd(x,m) = 1. Thus, the set of such x is exactly the set {x | x ∈ {1,...,m}, gcd(k,m) = 1}. But this is the definition of φ(m). Thus, there are φ(m) elements in ℤ/mℤ that have a multiplicative inverse.
[link]  
Theorem (Euler's theorem): For any m ∈ ℕ and a ∈ ℤ/mℤ, if gcd(m,a) = 1 then we have that:
aφ(m) mod m
=
1
Notice that if m is a prime number, then φ(m) = m-1. Then for any a ∈ ℤ/mℤ, gcd(a,m) = 1 and am-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.
[link]  
Fact: For any m ∈ ℕ and a ∈ ℤ/mℤ, if gcd(m,a) = 1 then for any i ∈ ℤ/φ(m)ℤ such that i ≡ 0 we have that
ai mod m
=
1
This is because:
i
≡
0 (mod φ(m))
=
k ⋅ φ(m)
aφ(m) ⋅ k mod m
=
(aφ(m))k mod m
=
1k mod m
 =
1 mod m
[link]  
Fact: For any p ∈ ℕ, if p is prime and a ∈ ℤ/pℤ then for any k ∈ ℤ we have that:
ak mod p
=
a(k mod (p-1)) mod p
[link]  
Fact: For any m ∈ ℕ and a ∈ ℤ/mℤ, if gcd(m,a) = 1 then for any k ∈ ℤ we have that:
ak mod m
=
a(k mod φ(m)) mod m
[link]  
Example: We can compute 238 mod 7 as follows because 7 is prime:
238
≡
238 mod (7-1) (mod 7)
=
238 mod 6
=
22
=
4
[link]  
Example: We can compute 4210000000 mod 5 as follows because 5 is prime:
4210000000
≡
4210000000 mod (5-1) (mod 5)
=
4210000000 mod 4
=
40
=
1
[link]  
Example: We can compute 48100+ 3 mod 15 as follows because gcd(4,15) = 1:
4(8100 + 3)
≡
4(8100 + 3) mod φ(15) (mod 15)
=
4(8100 + 3) mod ((5-1) ⋅ (3-1))
=
4(8100 + 3) mod 8
=
43
=
64
=
4
[link]  
Example: Compute 56603 mod 7.
[link]  
Fact: For any m ∈ ℕ and a ∈ ℤ/mℤ where gcd(m,a) = 1, we can use the Euler's theorem to find the inverse of a. Notice that:
aφ(m) mod m
=
1
(aφ(m)-1 ⋅ a) mod m
=
1
Thus, aφ(m)-1 mod m is the multiplicative inverse of a in ℤ/mℤ.
[link]  
Example: Find the multiplicative inverse of 52 mod 7 in ℤ/7ℤ.

It is sufficient to notice that 56 ≡ 1 (mod 7), so 52 ⋅ 54 ≡ 1, so 54 is the inverse of 52 in ℤ/7ℤ.
[link]  
Definition: For m ∈ ℕ, We define (ℤ/mℤ)* to be the following subset of ℤ/mℤ:
(ℤ/mℤ)*
=
{ a | a ∈ ℤ/mℤ, a has an inverse in ℤ/mℤ }
[link]  
Example: Does 11 have an inverse in ℤ/22ℤ (i.e., is it true that 11 ∈ (ℤ/22ℤ)*)?
[link]  
Example: Compute |(ℤ/35ℤ)*|.
|(ℤ/35ℤ)*|
=
|{ a | a ∈ ℤ/35ℤ, a has an inverse in ℤ/35ℤ }|
=
|{ a | a ∈ ℤ/35ℤ, gcd(a,35) = 1 }|
=
|{ a | a ∈ ℤ/35ℤ, gcd(a,35) = 1 }|
=
φ(35)
=
φ(5 ⋅ 7)
=
φ(5) ⋅ φ(7)
=
4 ⋅ 6
=
24
[link]  
Fact: For any m ∈ ℕ, (ℤ/mℤ)* is closed under multiplication modulo m. That is, for any a ∈ ℤ/mℤ and b ∈ ℤ/mℤ, if there exist a-1 ∈ ℤ and b-1 ∈ ℤ then (a ⋅ b) has an inverse (a-1 ⋅ b-1). We can use the commutativity of multiplication to show this:
(a ⋅ b) ⋅ (a-1 ⋅ b-1)
≡
(a ⋅ a-1) ⋅ (b ⋅ b-1)
≡
1 ⋅ 1
≡
1

[link]  3.13. Assignment #3: Multiplicative Inverses, CRT, and Efficient Computation

In this assignment you will solve several equations, and you will define a collection of Python functions for finding inverses of congruence classes, for solving systems of equations using the Chinese remainder theorem, and for employing CRT solutions. You must submit a single Python source file named a3.py (submitted to the location hw3/a3.py). Please follow the gsubmit directions.

You may import the following library functions in your module (you may not need all these functions for this assignment depending on how you approach the problems, but they may be used):

from math import floor
from fractions import gcd
        
You may also use the following built-in functions:
  • the pow() function can compute modular exponents efficiently (as in, ak mod n can be written in Python as pow(a,k,n));
  • the sum() function returns the sum of a list of integers (e.g., sum(1,2,3,4) returns 10).
Your file may not import any other modules or employ any external library functions associated with integers and sets unless explicitly permitted to do so in a particular problem. Solutions to each of the programming problem parts below should be fairly concise. You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on the lecture notes and on each other; carefully consider whether you can use functions from the lecture notes, or functions you define in one part within subsequent parts.
  1. Solve the following equations using step-by-step equational reasoning, and list each step. For this problem, you must use Fermat's little theorem and/or Euler's theorem to compute inverses of congruence classes. Your solutions for this problem should appear as comments, delimited using '''...''', in a3.py. You may use the = ascii character to represent the ≡ relational operator on congruence classes.
    1. Solve the following equation for x ∈ ℤ/7ℤ:
      5 ⋅ x ≡ 3 (mod 7)
    2. Solve the following system of equations for x ∈ ℤ/15ℤ:
      x
      		≡
      2 (mod 3)
      x
      		≡
      1 (mod 5)
    3. Let p and q be unequal prime numbers. If p-1 ≡ 5 (mod q) and q-1 ≡ 3 (mod p), find the solution x ∈ ℤ/(p ⋅ q)ℤ to the following system of equations (your solution should be in terms of p and q):
      x
      		≡
      1 (mod p)
      x
      		≡
      2 (mod q)
    4. Solve the following system of equations for x ∈ ℤ/36ℤ:
      x
      		≡
      3 (mod 4)
      x
      		≡
      6 (mod 9)
  2. Implement the following Python functions for computing multiplicative inverses of congruence classes.
    1. Implement a function invPrime(a, p) that takes two integers a and p > 1 where p is prime. The function should return the multiplicative inverse of a ∈ ℤ/pℤ (if a ≡ 0, it should return None). Your solution must use Fermat's little theorem.

      >>> [invPrime(i, 7) for i in range(0,7)]
      [None, 1, 4, 5, 2, 3, 6]
      >>> [invPrime(i, 13) for i in range(1,13)]
      [1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12]
                    
    2. Include the following definition in your code. This non-recursive implementation of the extended Euclidean algorithm avoids a stack overflow error on large inputs.

      def egcd(a, b):
          (x, s, y, t) = (0, 1, 1, 0)
          while b != 0:
              k = a // b
              (a, b) = (b, a % b)
              (x, s, y, t) = (s - k*x, x, t - k*y, y)
      return (s, t)
                    
      Given two inputs a and b, egcd(a, b) returns a solution (s, t) to the following instance of Bézout's identity:
      a ⋅ s + b ⋅ t
      		 =
      gcd(a, b)
      Using egcd(), implement a function inv(a, m) that takes two integers a and m > 1. If a and m are coprime, it should return the multiplicative inverse of a ∈ ℤ/mℤ. If a and m are not coprime, it should return None.

      >>> [inv(i, 13) for i in range(1,13)]
      [1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12]
      >>> [inv(i, 8) for i in range(1,8)]
      [1, None, 3, None, 5, None, 7]
                    
  3. Implement the following Python functions for solving certain systems of equations involving congruence classes.
    1. Implement a function solveOne(c, a, m) that takes three integers c, a, and m ≥ 1. If c and m are coprime, the function should return the solution x ∈ {0, ..., m-1} to the following equation:
      c ⋅ x
      		≡
      a (mod m)
      If c and m are not coprime, the function should return None.

      >>> solveOne(3, 4, 7)
      6
      >>> solveOne(1, 5, 11)
      5
      >>> solveOne(2,3,8)
      None
                    
    2. Implement a function solveTwo(e1, e2) that takes two tuples e1 and e2 as inputs, each of the form (c, a, m) (i.e., containing three integer elements). Each tuple (c, a, m) corresponds to an equation of the form:
      c ⋅ x
      		≡
      a (mod m)
      Thus, the two tuples, if we call them (c, a, m) and (d, b, n), correspond to a system of equations of the form:
      c ⋅ x
      		≡
      a (mod m)
      d ⋅ x
      		≡
      b (mod n)
      The function solveTwo() should return the unique solution x to the above system of equations. If either equation cannot be solved using solveOne(), or n and m are not coprime, the function should return None.

      >>> solveTwo((3, 4, 7), (1, 5, 11))
      27
                    
    3. Implement a function solveAll(es) that takes a list of one or more equations, each of the form (c, a, m). The list corresponds to the system of equations (assume all the mi are mutually coprime):
      c1 ⋅ x
      		≡
      a1 (mod m1)
      		⋮
      ck ⋅ x
      		≡
      ak (mod mk)
      The function solveAll() should return the unique solution x to the above system of equations. If any individual equation cannot be solved using solveOne(), or if the moduli are not all mutually coprime, the function should return None.

      >>> solveAll([(3,4,7), (1,5,11)])
      27
      >>> solveAll([(5,3,7), (3,5,11), (11,4,13)])
      856
      >>> solveAll([(1,2,3), (7,8,31), (3,5,7), (11,4,13)])
      7109
      >>> solveAll([(3,2,4), (7,8,9), (2,8,25), (4,4,7)])
      554
                    
  4. Suppose we represent the sum of a collection of exponentiation operations as a list of tuples, where each tuple contains two integers: the base and the exponent. For example, the list [(2,4),(3,5),(-6,3)] represents the sum of powers 24 + 35 + (−6)3.

    1. Implement a function sumOfPowers(nes, ps) that takes a list of one or more tuples nes (i.e., nes is of the form [(a1,n1),...,(ak,nk)]) as its first argument, and a list of one or more primes ps (i.e., of the form [p1,...,pm]) as its second argument. The function should return the correct result of the sum of powers as long as the following is true (e.g., on a computer with unlimited memory and time):
      0
      		≤
      a1n1 + ... + aknk
      		<
      p1 ⋅ ... ⋅ pm
      You may assume the second list contains distinct prime numbers. You may not assume that the numbers in the first input list have any particular patterns or relationships; they can be in any order, they can be of any size, and they may or may not share factors. Your implementation must work efficiently on very large inputs (e.g., with computations like 229999999999999999999999999999999996, as presented in the examples below).

      >>> sumOfPowers([(2,3), (5,6)], [3,5,7,11,13,17,19,23,29]) == 2**3 + 5**6
      True
      >>> 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]
      >>> sumOfPowers(\
             [(2,29999999999999999999999999999999996)\
             ,(-8,9999999999999999999999999999999999)\
             ,(2,29999999999999999999999999999999996)\
             ,(7,7),(-13,3)], primes)
      821346
                    
    2. Extra credit: Modify your implementation of sumOfPowers() so that it can handle inputs even if the exponents themselves are extremely large. You must use Euler's theorem to accomplish this; you may not assume that any particular patterns will exist in the bases or exponents.

      >>> sumOfPowers([(2,10**1000000 + 1), (-2,10**1000000 + 1), (3,3)], primes)
      27
                    

[link]  4. Computational Complexity of Modular Arithmetic Algorithms

[link]  4.1. Definition of computational problems and their complexity

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.
[link]  
Definition: 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.
[link]  
Definition: The computational complexity of a problem refers to the running time of the most efficient algorithm that can solve the problem.

[link]  4.2. Complexity of algorithms for solving tractable problems

In this subsection we consider the running time of efficient algorithms for performing common arithmetic operations (addition, subtraction, multiplication, exponentiation, and division). We consider the complexity of these arithmetic operations on each of the following domains:
  • unbounded positive integers;
  • integers modulo 2n;
  • integers modulo k for some k ∈ ℕ.
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
2n-1 ⋅ an-1 + ... + 20 ⋅ a0
Below are some specific examples:
111
=
22 ⋅ 1 + 21 ⋅ 1 + 20 ⋅ 1
1101
=
23 ⋅ 1 + 22 ⋅ 1 + 21 ⋅ 0 + 20 ⋅ 1
10
=
21 ⋅ 1 + 20 ⋅ 0
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 ≤ 2n - 1 and y ≤ 2m - 1.
[link]  
Algorithm: There exists an algorithm that can compute the sum of an n-bit integer x and an m-bit integer y in time O(max(n,m)+1). The size of the output is O(max(n,m)+1).
  1. addition of unbounded positive integers: n-bit integer x, m-bit integer y
    1. r (a bit vector to store the result)
    2. c := 0 (the carry bit)
    3. for i from 0 to max(n,m)-1
      1. r[i] := (x[i] xor y[i]) xor c
      2. c := (x[i] and y[i]) or (x[i] and c) or (y[i] and c)
    4. r[max(n,m)+1] := c
    5. return r
How can we use the addition algorithm to implement multiplication? One approach for multiplying two positive integers x, y ∈ ℕ is to do repeated addition of y (repeating the addition operations x times). However, if x is an n-bit integer, this would require up to 2n-1 addition operations, which would take exponential time in the representation size of the input x.

A more efficient approach is to use the representation of x as a sum of powers of 2, and to apply the distributive property. Suppose x is represented as the binary bit string an-1...a0. Then we have:
x ⋅ y
=
(an-1 ⋅ 2n-1 + ... + a1 ⋅ 21 + a0 ⋅ 20) ⋅ y
=
an-1 ⋅ 2n-1 ⋅ y + ... + a1 ⋅ 21 + a0 ⋅ 20 ⋅ y
Notice that we have now rewritten multiplication as n-1 addition operations. The only other problem is how to multiply y by powers of 2. We can do so simply by appending a 0 to the bit string representation of y. Suppose y is represented as the binary bit string bn-1...b0. Then we have:
2 ⋅ y
=
2 ⋅ bn-1...b1b0
=
2 ⋅ (bn-1 ⋅ 2n-1 + ... + b1 ⋅ 21 + b0 ⋅ 20)
=
bn-1 ⋅ 2n + ... + b1 ⋅ 22 + b0 ⋅ 21
=
(bn-1 ⋅ 2n + ... + b1 ⋅ 22 + b0 ⋅ 21) + 0 ⋅ 20
=
bn-1...b1b00
Thus, our algorithm only needs to depend on addition, and on shifting bit strings left by one (a.k.a., appending a 0 to the bit string at the position of the least significant bit).
[link]  
Algorithm: There exists an algorithm that can compute the product of an n-bit integer x and an m-bit integer y in time O(n ⋅ (max(n,m)+1+n)) or O(max(n,m)2). The size of the output is O(n+m) (because the shift left for the 21 case does not contribute to the final result, the m-bit integer is shifted left at most n-1 times, but there may still be a carried bit on the last addition operation performed).
  1. multiplication of unbounded positive integers: n-bit integer x, m-bit integer y
    1. r (a bit vector to store the result)
    2. for i from 0 to n-1
      1. if x[i] is 1
        1. r := r + y (using unbounded integer addition)
      2. shift the bits of y left by one bit (i.e., multiply y by 2)
    3. return r
[link]  
Algorithm: There exists an algorithm that can compute the exponentiation xy of an n-bit integer x and an m-bit integer y in time O(n ⋅ 2m). The size of the output is O(n ⋅ 2m). Notice that this means that for unbounded integer outputs, the algorithm runs in exponential time.
  1. exponentiation of unbounded positive integers: n-bit integer x, m-bit integer y
    1. r (a bit vector to store the result)
    2. for i from 0 to m-1
      1. if y[i] is 1
        1. r := r ⋅ x (using unbounded integer multiplication)
      2. x := x ⋅ x (using unbounded integer multiplication)
    3. return r
[link]  
Algorithm: There exists an algorithm that can compute the integer quotient ⌊ x / y ⌋ of an n-bit integer x and an m-bit integer y in time O((n ⋅ n) + (n ⋅ (2 ⋅ n))) or O(n2).
  1. integer division of unbounded positive integers: n-bit integer x, m-bit integer y
    1. if y > x
      1. return 0
    2. for i from 0 to n-1
      1. shift y left by one bit
    3. r (a bit vector to store ⌊ x / y ⌋ ⋅ y)
    4. q (a bit vector to store the integer quotient)
    5. p := 2n-1 (to keep track of the current power of 2)
    6. for i from 0 to n-1
      1. if r+y < x
        1. r := r+y (using unbounded integer addition)
        2. q := q+p (using unbounded integer addition)
      2. shift y right by one bit
      3. shift p right by one bit
    7. return q
[link]  
Algorithm: There exists an algorithm that can compute x mod y of an n-bit integer x and an m-bit integer y in time O(n2). This is accomplished by first performing integer division, then an integer multiplication, and then a subtraction. This corresponds to the formula for the modulus operation:
x mod y
=
x - ⌊ x/y ⌋ ⋅ y
When we consider the operations above as operating on integers modulo 2n (with results also in 2n), this corresponds to simply dropping any bits beyond the n least-significant bits when performing the computation.
[link]  
Fact: There exists an algorithm that can compute the sum of two n-bit integers x and y in time O(n). The size of the output is O(n).
[link]  
Fact: There exists an algorithm that can compute the product of two n-bit integers x and y in time O(n2). The size of the output is O(n).
[link]  
Fact: There exists an algorithm that can compute xy for two n-bit integers x and y in time O(n3). The size of the output is O(n).
[link]  
Fact: The recursive algorithm for gcd (and the extended Euclidean algorithm) makes O(log (max(x,y))) recursive calls on an integer inputs x ∈ ℕ and y ∈ ℕ. Notice that this means that the number of recursive calls is linear, or O(max(n,m)), for inputs consisting of an n-bit integer x and an m-bit integer y.
To see the above, consider the following fact: for any a ∈ ℕ, b ∈ ℕ, 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).
[link]  
Fact: The recursive algorithm for the extended Euclidean algorithm on inputs consisting of an n-bit integer x and an m-bit integer y runs in time O(max(n,m) ⋅ (2 ⋅ max(n,m)2 + max(n,m))), or O(max(n,m)3). The number of recursive calls is about max(n,m), and each recursive call involves an integer division, a multiplication, and a subtraction.

If all inputs and outputs are integers that can be represented with at most n bits, the running time is then O(n3).
[link]  
Fact: The following problem can be solved in polynomial time: given x ∈ (ℤ/nℤ)*, compute x-1. This can be reduced to running the extended Euclidean algorithm, which has a polynomial running time.

If all inputs and outputs are integers that can be represented with at most n bits, the running time is then O(n3).
[link]  
Fact: There exists an O(max(n,m)3 + (n+m)2) algorithm that can solve the following system of two equations (for n-bit integers x,x' and m-bit integers y,y') using the Chinese remainder theorem:
s
≡
x' (mod x)
s
≡
y' (mod y)
This algorithm calls the extended Euclidean algorithm on x and y, and then performs four multiplications modulo (x ⋅ y).

If all inputs and outputs are integers that can be represented with at most n bits, the running time is then O(n3).
[link]  
Exercise: Multiply the following two numbers (represented in binary) using the multiplication algorithm presented in lecture: 1101 ⋅ 101.
We can proceed by repeatedly shifting the first input left (corresponding to multiplication by 2), and multiplying each shifted version by a corresponding digit from the second input:
1101 ⋅ 1 + 11010 ⋅ 0 + 110100 ⋅ 1
=
1101 + 110100
=
1000001

[link]  4.3. Complexity of (probably) intractable problems

In the previous section we saw that addition, subtraction, multiplication, exponentiation, and division (both integer division, modulus, and multiplication by multiplicative inverses) can all be computed efficiently (i.e., in polynomial time) both over integers and over congruence classes. It is also possible to efficiently compute roots and logarithms of integers (we omit proofs of this fact in this course). However, no efficient algorithms are known for computing roots and logarithms of congruence classes.
[link]  
Definition: A problem can be solved in polynomial time iff there exists for some constant c an algorithm that solves all instances of the problem in time O(nc). The set of all problems that can be solved in polynomial time is called P, and if a problem can be solved in polynomial time, we say that the problem is in P.
[link]  
Definition: A problem can be solved in exponential time iff there exists an algorithm that solves all instances of the problem in time O(2n).
[link]  
Definition: There exists a polynomial-time reduction from a problem A to a problem B iff there exists a polynomial-time algorithm that can convert any instance of problem A into an instance of problem B (i.e., convert an input for A into an input for B, and convert the output from B into an output from A).
A polynomial-time reduction from one problem to another can be viewed as two separate polynomial-time algoritms: a conversion algorithm that takes inputs to problem A and invokes a solver for problem B some polynomial number of times, and a conversion algorithm that takes all the outputs obtained from the solver for problem B and assembles and/or converts them into outputs for problem A.
solver for
problem B		 ⇒
⇒
⇒		 conversion
from output(s) from
B to output from A
⇑⇑⇑ ⇓
conversion
from input for
A to input(s) for B		 ⇐ solver for
problem A
We can summarize the above diagram by simply saying that problem A reduces to problem B.
problem B ⇐ problem A
We have already seen examples of such reductions. For example, a CRT solver for two equations makes a single call to the extended Euclidean algorithm. Thus, there exists a polynomial-time reduction from the problem of solving a two-equation system using CRT to the problem of computing multiplicative inverses.
finding
multiplicative
inverses		 ⇐ solving two-equation
systems using CRT
[link]  
Fact: If there exists a polynomial-time reduction from problem A to problem B, and problem A is not in P (i.e., there exists no polynomial-time algorithm to solve A), then problem B must not be in P, either.

To see why B cannot be in P, we can present a proof by contradiction. Suppose that there does exist a polynomial-time algorithm to solve problem B. Then the polynomial-time reduction from A to B can invoke a polynomial-time algorithm. But then the reduction and algorithm for B working together will constitute a polynomial-time algorithm to solve A. Then it must be that A is in P. But this contradicts the fact that A is not in P, so no such polynomial-time algorithm for B could exist.
The above fact allows us to make conclusions about the computational complexity of certain problems based on their relationships (in terms of implementation) to other problems.
problem B

premise:
can be solved in
polynomial time

B ∈ P		 ⇐ problem A

conclusion:
can be solved in
polynomial time

A ∈ P
problem B

conclusion:
cannot be solved in
polynomial time

B ∉ P		 ⇐ problem A

premise:
cannot be solved in
polynomial time

A ∉ P
Intuitively, we can imagine that if problem A is "attached to" (i.e., depends on) problem B, an "easy" problem B will "pull" A down into the set of easily solvable problems P, while a "difficult" problem A will "pull" problem B into the set of hard-to-solve problems.
[link]  
Conjecture (factoring): The following problem is not in P: given any integer n ∈ ℕ where n = p ⋅ q and p and q are prime, find p and q.
[link]  
Fact: Suppose that n = p ⋅ q for two primes p ∈ ℕ and q ∈ ℕ. Given only n and φ(n), it is possible to compute p and q. Consider the following:
φ(n)
=
(p − 1) ⋅ (q − 1)
φ(n)
=
p ⋅ q − p − q + 1
φ(n)
=
n - p − q + 1
φ(n) - n
=
- p − q + 1
φ(n) - n - 1
=
− p − q
Thus, it is sufficient to solve the following system of equations for p and q:
n
=
p ⋅ q
φ(n) - n - 1
=
− p − q
[link]  
Example: Suppose that n = 15 and φ(n) = 8. Factor n.

We can plug n and φ(n) into the system of equations derived in the applicable fact:
15
=
p ⋅ q
8 − 15 − 1
=
− p − q
With two equations and two unknowns, we can now solve for p and q:
8 − 15 − 1
=
− p − q
p
=
15 − 8 + 1 − q
=
8 − q
15
=
(8 − q) ⋅ q
0
=
− q2 + 8q − 15
0
=
q2 − 8q + 15
At this point, we use the quadratic equation:
q
=
1/2 ⋅ (8 ± √(64 − 4(1)(15)))
q
=
1/2 ⋅ (8 ± √(4))
q
=
1/2 ⋅ (8 ± 2)
q
∈
{3, 5}
{p, q}
=
{3, 5}
[link]  
Conjecture (computing φ): The following problem is not in P: given any integer n ∈ ℕ where n = p ⋅ q and p and q are prime, find φ(n).

If we can compute φ(n), then we can compute p and q. If computing φ(n) were any easier than factoring n (e.g., if we had a polynomial-time algorithm for computing φ(n)), then our claim about the hardness of factoring n would be a contradiction. In other words, factoring n can be reduced to solving φ(n).
computing φ(n)

conclusion:
cannot be solved in
polynomial time

computing φ(n) ∉ P		 ⇐ factoring n

conjecture:
cannot be solved in
polynomial time

factoring ∉ P
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].

Suppose we are given the following equation:
xy
=
z
There are three computational questions we could ask about the above equation:
  • given x and y, compute z (this is the exponentiation operation);
  • given x and z, compute y (this is the logarithm operation, since we have logx z = y in an equivalent notation);
  • given y and z, compute x (this is the yth root operation, since we have y√(z) = x in an equivalent notation).
We have efficient algorithms for computing all three of the above if x, y, and z are all integers or real numbers. Suppose we instead consider the following equation for some n ∈ ℕ:
xy
≡
z (mod n)
In other words, we can interpret the equation as a congruence of equivalence classes in ℤ/nℤ. In this case, we already know that the first operation (exponentiation) has an efficient implementation because exponentiation and modulus are both efficient operations. However, we believe that the other two operations (computation of logarithms and roots of congruence classes) are computationally difficult (no polynomial-time algorithm exists to compute solutions).
[link]  
Conjecture (RSA problem): The following problem is not in P: compute m given only the following:
n
=
p ⋅ q
    
for two primes p and q in ℕ
e
∈
ℤ/φ(n)ℤ
    
where e ≥ 3
c
=
me mod n
    
for an unknown m ∈ ℤ/nℤ
Notice that the RSA problem is analogous to computing the eth root of c in ℤ/nℤ:
e√(c) (mod n)
=
e√(me) (mod n)
=
m (mod n)
Note also that this can be accomplished by first finding φ(n) and then computing the inverse of e, but this is as difficult as factoring n, and we assume that is not in P. Is there another way to compute m? We do not know, but we assume that there is no other faster (i.e., polynomial-time) way to do so.
[link]  
Conjecture (discrete logarithm assumption): The following problem is not in P: compute e given only the following:
n
∈
ℕ
m
∈
{1,...,n − 1}
c
=
me mod n
    
for an unknown e ∈ ℕ
Notice that this is analogous to computing the logarithm of a value c in ℤ/nℤ with respect to a known base m:
logm (c)
=
logm (me)
=
e
Note that the RSA problem requires that e ≥ 3, so it does not include the problem of computing square roots. The last intractable problem we will consider in this section is the problem of computing square roots of congruence classes within ℤ/nℤ for some n ∈ ℕ. We examine this problem separately from the RSA problem because it is possible to reduce factoring directly to the problem of computing square roots (while there is currently no known deterministic polynomial-time reduction from the factoring problem to the RSA problem).

Before we formally define the problem of computing square roots in ℤ/nℤ, we must first introduce some concepts and facts. This is because the problem of computing square roots in ℤ/nℤ is different from the problem of computing square roots of integers in ℕ, and this difference is likely what makes it computationally more difficult.
[link]  
Definition: Given some n ∈ ℕ and some y ∈ ℤ/nℤ, we say that y is a quadratic residue in ℤ/nℤ if there exists x ∈ ℤ/nℤ such that x2 ≡ y.
[link]  
Example: Let us find the quadratic residues in ℤ/7ℤ:
02 ≡ 0 (mod 7)
12 ≡ 1 (mod 7)
22 ≡ 4 (mod 7)
32 ≡ 2 (mod 7)
42 ≡ 2 (mod 7)
52 ≡ 4 (mod 7)
62 ≡ 1 (mod 7)
The quadratic residues in ℤ/7ℤ are 0, 1, 2, and 4. Notice that 3, 5, and 6 are not quadratic residues in ℤ/7ℤ. Thus, the equations x2 ≡ 3, x2 ≡ 5, and x2 ≡ 6 have no solution in ℤ/7ℤ.
[link]  
Example: Consider the set of congruence classes ℤ/5ℤ. We have that:
02 ≡ 0 (mod 5)
12 ≡ 1 (mod 5)
22 ≡ 4 (mod 5)
32 ≡ 4 (mod 5)
42 ≡ 1 (mod 5)
Notice that 2 and 3 are not quadratic residues in ℤ/5ℤ. Thus, neither x2 ≡ 2 nor x2 ≡ 3 have solutions in ℤ/5ℤ.
[link]  
Fact: Given some n ∈ ℕ and some y ∈ ℤ/nℤ, if y and n are coprime and y is a non-zero quadratic residue in ℤ/nℤ then there exist at least two a,b ∈ ℤ/nℤ such that a ≠ b, a2 ≡ y, and b2 ≡ y.

Note that this is analogous to square roots in ℤ (since √(z) ∈ ℤ and −√(z) ∈ ℤ are both square roots of z ∈ ℤ if they exist).

We can prove this fact in the following way: suppose that y is a quadratic residue. Then there exists at least one x ∈ ℤ/nℤ such that:
x2 mod n
=
y
But this means that (n − x) ∈ ℤ/nℤ is such that:
((n − x)2) mod n
=
(n2 − (2 ⋅ n ⋅ x) + x2) mod n
=
x2 mod n
=
y mod n
Thus, x and (n − x) are both roots of y.
[link]  
Example: It is the case that 4 ∈ ℤ/5ℤ is a quadratic residue in ℤ/5ℤ, with two roots 2 and 3:
22 mod 5
=
4
32 mod 5
=
9 mod 5
=
4
[link]  
Example: Consider 0 ∈ ℤ/3ℤ. We have that:
02 ≡ 0 (mod 3)
12 ≡ 1 (mod 3)
22 ≡ 1 (mod 3)
Thus, x2 ≡ 0 has exactly one solution in ℤ/3ℤ.
[link]  
Fact: Let p ∈ ℕ be a prime such that p mod 4 = 3, and suppose that y ∈ ℤ/pℤ. Then y has either 0, 1, or 2 roots in ℤ/pℤ.
[link]  
Fact: Let p ∈ ℕ be a prime such that p mod 4 = 3, and suppose that y ∈ ℤ/pℤ is a quadratic residue with two roots in ℤ/pℤ. Then we can compute the roots using the following formula:
x ≡ ± y(p+1)/4 (mod p)
In fact, if the modulus n is not prime, there may exist more than two roots of a value in ℤ/nℤ.
[link]  
Example: It is the case that 1,-1,6,-6 ∈ ℤ/35ℤ are all square roots of 1 ∈ ℤ/35ℤ:
12 mod 35
=
1
(-1)2 mod 35
=
342 mod 35
=
1156 mod 35
=
((33 ⋅ 35)+1) mod 35
=
1 mod 35
62 mod 35
=
36 mod 35
=
1 mod 35
(-6)2 mod 35
=
292 mod 35
=
841 mod 35
=
((24 ⋅ 35)+1) mod 35
=
1 mod 35
[link]  
Example: Suppose we are given an instance of the congruent squares problem where y = 2 and n = 15. We want to find x ∈ ℤ/15ℤ such that x ≢ ± y but x2 ≡ y2 ≡ 22 ≡ 4. Notice that we have that:
y
≡
2 mod 3
y2
≡
22 mod 3
≡
1 mod 3
(3-y)2
≡
12 mod 3
≡
1 mod 3
Notice also that we have that:
y
≡
2 mod 5
y2
≡
22 mod 5
≡
4 mod 5
(5-y)2
≡
32 mod 5
≡
4 mod 5
Thus, the square roots of 4 in ℤ/3ℤ are 1 and 2, and the square roots of 4 in ℤ/5ℤ are 2 and 3. We can then apply the Chinese remainder theorem to every pair of combinations:
r1
≡
1 mod 3
r1
≡
2 mod 5
r1
≡
7 mod 15
r2
≡
2 mod 3
r2
≡
2 mod 5
r2
≡
2 mod 15
r3
≡
1 mod 3
r3
≡
3 mod 5
r3
≡
13 mod 15
r4
≡
2 mod 3
r4
≡
3 mod 5
r4
≡
8 mod 15
Thus, x = 8 and x = 7 are solutions to x ≢ ± 2 and x2 ≡ 4.
[link]  
Fact (Hensel's lemma): Let p ∈ ℕ be a prime number greater than 2, and let k ∈ ℕ be any positive integer (i.e., k ≥ 1). Suppose that x and p are coprime, and that x ∈ ℤ/pkℤ can be squared to obtain some quadratic residue r ∈ ℤ/pkℤ:
x2 ≡ r (mod pk)
We can compute y ∈ ℤ/pk+1ℤ such that:
y2 ≡ r (mod pk+1)
We compute it as follows. First, we compute c using the following formula:
c
≡
x-1 ⋅ 2-1 ⋅ ((r - x2) / pk) (mod p)
Then, we have that:
y
≡
x + c ⋅ pk
To see why Hensel's lemma is true, suppose that we have that:
x2
≡
r (mod pk)
Notice that if it is possible to "lift" x to a root of r in ℤ/pk+1ℤ, the only possibility is that this new root y has an additional multiple of pk. Thus, it must be that for some integer multiple c, we have:
y
=
x + c ⋅ pk
We can then substitute:
y2
≡
r (mod pk+1)
(x + (c ⋅ pk))2
≡
r (mod pk+1)
But we can simplify the above equation:
(x + (c ⋅ pk))2
≡
r (mod pk+1)
x2 + (2 ⋅ x ⋅ c ⋅ pk) + (c2 ⋅ p2k)
≡
r (mod pk+1)
But notice that the third term on the left-hand side in the above equation is equivalent to the congruence class 0 + pk+1ℤ:
c2 ⋅ p2k
≡
0 (mod pk+1)
Thus, we have:
x2 + (2 ⋅ x ⋅ c ⋅ pk)
≡
r (mod pk+1)
(x2 − r) + (2 ⋅ x ⋅ c ⋅ pk)
≡
0
The above can be rewritten using the divisibility predicate as:
pk+1
|
(x2 − r) + (2 ⋅ x ⋅ c ⋅ pk)
Thus, we can divide both sides of the above relationship by pk to obtain:
p
|
(x2 − r)/(pk) + (2 ⋅ x ⋅ c)
We can then rewrite the above as an equation of congruence classes:
(x2 − r)/(pk) + (2 ⋅ x ⋅ c)
≡
0 (mod p)
(2 ⋅ x ⋅ c)
≡
− (x2 − r)/pk
c
≡
x-1 ⋅ 2-1 ⋅ (− (x2 − r)/pk)
c
≡
x-1 ⋅ 2-1 ⋅ ((r − x2)/pk)
Thus, we have derived the formula in Hensel's lemma.
[link]  
Example: To better understand Hensel's lemma, we can derive the lemma for a particular example. Let us start with the following equation:
42
≡
2 (mod 7)
Suppose we want to find y ∈ ℤ/72ℤ such that:
y2
≡
2 (mod 49)
We know that the difference between 4 and y must be a multiple of 7, so we write:
y
=
4 + 7 ⋅ c
Then we proceed:
y2
≡
2 (mod 49)
(4 + 7 ⋅ c)2
≡
2 (mod 49)
42 + (2 ⋅ 7 ⋅ c ⋅ 4) + (49 ⋅ c2)
≡
2 (mod 49)
42 + (2 ⋅ 7 ⋅ c ⋅ 4)
≡
2 (mod 49)
We simplify further to compute c:
(42 - 2) + (2 ⋅ 7 ⋅ c ⋅ 4)
≡
0 (mod 49)
14 + (2 ⋅ 7 ⋅ c ⋅ 4)
≡
0 (mod 49)
The above can be rewritten using the divisibility predicate as:
49 | 14 + (2 ⋅ 7 ⋅ c ⋅ 4)
7 | 2 + (2 ⋅ c ⋅ 4)
We can again rewrite the above as an equation of congruence classes:
2 + (2 ⋅ c ⋅ 4)
≡
0 (mod 7)
2 ⋅ c ⋅ 4
≡
− 2 (mod 7)
2 ⋅ c ⋅ 4
≡
5 (mod 7)
c
≡
2-1 ⋅ 4-1 ⋅ 5 (mod 7)
c
≡
4 ⋅ 2 ⋅ 5 (mod 7)
c
≡
5 (mod 7)
Thus, we have:
y
≡
4 + 7 ⋅ 5 (mod 49)
y
≡
39 (mod 49)
Since 49 − 39 = 10, we have:
y
≡
± 10 (mod 49)
y2
≡
2 (mod 49)
[link]  
Example: We want to find both solutions y ∈ ℤ/121ℤ to:
y2
≡
5 (mod 121)
Since 121 = 112, we have p = 11, k = 1, and r = 5. We begin by finding x ∈ ℤ/11ℤ such that:
x2
≡
5 (mod 11)
Since 11 ∈ 3 + 4ℤ, we can use an explicit formula:
x
≡
± 5(11+1)/4 (mod 11)
≡
± 53
≡
± 3 ⋅ 5
≡
± 4
Thus, it is sufficient to lift the solution 4 ∈ ℤ/11ℤ to a solution in ℤ/121ℤ using Hensel's lemma. We compute c:
c
≡
x-1 ⋅ 2-1 ⋅ ((r − x2)/pk) (mod p)
 ≡
4-1 ⋅ 2-1 ⋅ ((5 − 16)/11) (mod 11)
 ≡
4-1 ⋅ 2-1 ⋅ (− 1)
≡
3 ⋅ 6 ⋅ (− 1)
≡
(− 18)
≡
4
Thus, we have:
y
≡
4 + 4 ⋅ 11 (mod 121)
≡
4 + 44
≡
48
Thus, we have the solution
y
≡
± 48 (mod 121)
[link]  
Example: The distance travelled by an object that is at rest at time t = 0 and then immediately begins accelerating at 4 meters/second2 (i.e., the speed of the object increases by the quantity 4 meters/second every second) can be defined in terms of time in second t as:
d
=
1/2 ⋅ 4 ⋅ t2
We might expect an object to behave this way if it is being pulled by gravity, or if it is using a stable propulsion engine (e.g., a rocket).

Suppose we are using a range ambiguity resolution technique to track the distance the object has travelled. If it a particular moment, we know that the distance from the object is in the congruence class 10 + 11ℤ, what can we say about the amount of time t that has elapsed since the object started moving?

Since the distance is in 10 + 11ℤ, we can say:
d
≡
10 (mod 11)
1/2 ⋅ 4 ⋅ t2
≡
10
2 ⋅ t2
≡
10
We know that 2-1 ≡ 6 (mod 11), so we multiply both sides of the above equation to obtain:
t2
≡
60 (mod 11)
t2
≡
5 (mod 11)
Thus, we can compute:
t
≡
5(11+1)/4 (mod 11)
t
≡
53
t
≡
3 ⋅ 5
t
≡
4 (mod 11)
Thus, we can say that the amount of time that has elapsed is in 4 + 11ℤ.
[link]  
Example: Solve the following system of equations for x ∈ ℤ/21ℤ (find all solutions):
x2
≡
1 (mod 3)
x2
≡
1 (mod 7)
We know that there is exactly one solution y ∈ ℤ/21ℤ to the following system:
y
≡
1 (mod 3)
y
≡
1 (mod 7)
The solution is simply y = 1, and since there is only one solution, this is the only possibility. Thus, we are looking for all the solutions to the following equation:
x2
≡
1 (mod 21)
Since 3 mod 4 = 7 mod 4 = 3, we know that there are two solutions to each of the following equations:
x2
≡
1 (mod 3)
x2
≡
1 (mod 7)
The solutions are as follows:
x
≡
1 (mod 3)
x
≡
2 (mod 3)
x
≡
1 (mod 7)
x
≡
6 (mod 7)
Taking every pair of combinations with one solution from ℤ/3ℤ and one solution from ℤ/7ℤ, we get:
x1
≡
1 (mod 3)
x1
≡
1 (mod 7)
x1
≡
1 (mod 21)
x2
≡
2 (mod 3)
x2
≡
1 (mod 7)
x2
≡
8 (mod 21)
x3
≡
1 (mod 3)
x3
≡
6 (mod 7)
x3
≡
13 (mod 21)
x4
≡
2 (mod 3)
x4
≡
6 (mod 7)
x4
≡
20 (mod 21)
[link]  
Example: How many solutions x ∈ ℤ/(33 ⋅ 35)ℤ does the following system of equations have:
x2
≡
4 (mod 33)
x2
≡
4 (mod 35)
We know that each of the following equations have two solutions (2 and -2 in the respective sets). Notice that 4 mod 3 = 1.
x2
≡
1 (mod 3)
x2
≡
4 (mod 11)
x2
≡
4 (mod 5)
x2
≡
4 (mod 7)
Thus, there are two possible choices for each of the variables r1 ∈ {-2,2}, r2 ∈ {-2,2}, r3 ∈ {-2,2}, r4 ∈ {-2,2}, so there are 2 ⋅ 2 ⋅ 2 ⋅ 2 = 24 = 16 possible systems of the form:
x
≡
r1 (mod 3)
x
≡
r2 (mod 11)
x
≡
r3 (mod 5)
x
≡
r4 (mod 7)
Each system has a unique solution because the tuple (r1, r2, r3, r4) is unique, so there are 16 solutions for x in ℤ/(33 ⋅ 35)ℤ. Alternatively, we could break the problem down into two subproblems. First, we solve the following equation:
x2
≡
4 (mod 33)
We obtain four distinct solutions (r1, r2, r3, r4) in ℤ/33ℤ. Next, we solve the following equation:
x2
≡
4 (mod 35)
We then have four distinct solutions in (s1, s2, s3, s4) ℤ/35ℤ. Since gcd(33,35) = 1, we can then take any combination of solutions ri and si and set up the system:
x
≡
ri (mod 33)
x
≡
si (mod 35)
There will be exactly one solution to each of the above systems. There are 42 = 16 distinct systems, so there will be 16 distinct solutions.
We can summarize everything we know about computing square roots of congruence classes as follows. Suppose we want to find all solutions to the equation x2 ≡ a (mod n) for some n ∈ ℕ and some a ∈ ℤ/nℤ.
  • If n is a prime p, the possibilities are:
    • a is not a quadratic residue in ℤ/pℤ, so there are no solutions to the equation,
    • a ≡ 0, in which case x ≡ 0 is the one and only solution to the equation,
    • a is a quadratic residue in ℤ/pℤ, so there are exactly two solutions to the equation, ± x ∈ ℤ/pℤ.
  • If n is prime power pk+1 and a is coprime with p, the possibilities are:
    • a is not a quadratic residue in ℤ/pkℤ, so it is not a quadratic residue in ℤ/pk+1ℤ;
    • a is a quadratic residue in ℤ/pkℤ, and both square roots of a in ℤ/pkℤ can be "lifted" to ℤ/pk+1ℤ using Hensel's lemma.
  • If n is a product of two coprime numbers k and m, then there is a solution in ℤ/nℤ for every possible combination of y and z such that:
    y2
    		≡
    a mod k
    z2
    		≡
    a mod m
    Each combination corresponds to a solution x ∈ ℤ/nℤ defined using CRT as:
    x
    		≡
    y mod k
    x
    		≡
    z mod m
Let us consider the problem of finding all of the square roots of a member of ℤ/nℤ. Notice that this problem is analogous to computing all the square roots of y in ℤ/nℤ:
√(y)
=
± x
The main difference is that the number of square roots may be greater than 2. This problem is believed to be computationally difficult (i.e., no algorithm in P exists that can solve the problem). In fact, even finding just one additional square root is believed to be computationally difficult.
[link]  
Conjecture (congruent squares): The following problem is not in P: given n = p ⋅ q for two primes p and q in ℕ and y ∈ ℤ/nℤ, find an x ∈ ℤ/nℤ such that x2 ≡ y2 but x ≢ ± y.

Factoring can be reduced to finding congruent squares. Suppose we want to factor n. We find x and y such that:
x2 mod n
=
y2 mod n
0 mod n
=
(x2 − y2) mod n
=
((x + y) ⋅ (x − y)) mod n
n
|
(x + y) ⋅ (x − y)
Since n cannot divide (x+y) (because x ≢ ± y, so x + y ≠ n), and it cannot divide (x-y) (since (x+y) < n), and (x-y) ≠ 0 (since x ≢ ± y), it must be that n shares factors with both (x+y) and (x-y). Thus, it must be that either gcd(n,x + y) or gcd(n,x - y) is a non-trivial factor of n, and this can be computed efficiently.
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.
congruent squares
(square roots of
congruence classes)
⇑ ⇑
computing φ(n)
for n = p ⋅ q		 ⇐
⇒		 factoring
n = p ⋅ q
⇑ ⇑
RSA problem
(eth roots of
congruence classes)
discrete logarithm
(logarithms of
congruence classes)

[link]  4.4. Applications of intractability

The computational intractability of certain problems in modular arithmetic makes it possible to address some practical security issues associated with implementing communication protocols. In particular, it helps address two common problems:
  • parties must communicate over a public communications channel, so everything they send is visible both to their receiver and to anyone that may be eavesdropping;
  • parties trying to communicate cannot physically meet to agree on shared secret information before communicating.
[link]  
Protocol (hard-to-forge identification with meeting): Suppose Alice and Bob know that Alice will need to send Bob a single message at some point in the future. However, it is possible that Eve might try to impersonate Alice and send a message to Bob while pretending to be Alice.

In order to help Bob confirm that a message is truly from Alice (or to determine which message is from Alice given multiple messages), Alice and Bob meet in person and agree on a secret identifier s. When Alice decides to send a message m to Bob, she will send (m, s). Bob can then compare s to his own copy of s and confirm the message is from Alice.

Eve's only attack strategy is to try and guess s. As long as Alice and Bob choose s from a very large range of integers, the probability that Eve can guess s correctly is small.
A major flaw in the above identification protocol is that Alice and Bob must first meet in person to agree on a secret. Can Alice and Bob agree on a secret without meeting in person?
[link]  
Protocol (hard-to-forge identification without meeting): Suppose Alice and Bob know that Alice will need to send Bob a single message at some point in the future. Alice prepares for this by doing the following:
  • choose two large primes p and q at random;
  • compute n = p ⋅ q;
  • send the public identifier n to Bob over a public/non-secure communication channel.
When Alice is ready to send her message m to Bob, Alice will send (m, (p, q)), where (p, q) is the private identifier. Bob can confirm that p ⋅ q = n, at which point he will know Alice was the one who sent the message.
[link]  
Conjecture (forging identification): The following problem is not in P: in the previously defined protocol, given a public identifier n, compute the private identifier (p, q).

If it were possible to quickly (i.e., in polynomial time) compute the private identifier, then it would be easy to forge the identity of a sender by recording their public identifier n. However, suppose that this forging computation could be used as a subprocedure in a factoring algorithm. Then it would be possible to implement an efficient factoring algorithm. In other words, factoring n can be reduced to forging a private identifier. Thus, the problem of forging a private identifier must not be in P (i.e., the fastest algorithm that exists for forging an identity is not in P, which means there is no polynomial-time for forging an identity).
forging private
identifier for n

conclusion:
cannot be solved in
polynomial time

forging ∉ P		 ⇐ factoring n

conjecture:
cannot be solved in
polynomial time

factoring ∉ P
Note that the reduction also works in the other direction: an algorithm for factoring can be used for forging an identity. However, this proves nothing about the difficulty of forging! Just because forging can be reduced to an inefficient algorithm for factoring does not mean that there does not exist some other algorithm for forging that does not rely on factoring.
alternative
efficient
algorithm		 ⇐ forging private
identifier for n		 ⇒ factoring n
The above identification protocol improves over the previous protocol because it allows Alice and Bob to agree on an identifier for Alice without meeting in person. Its security relies on the fact that it is unlikely that Eve is capable of forging identifiers because her ability to forge would solve a problem that we believe is very difficult to solve.

However, the protocol still has many other flaws. For example, Eve could preempt Alice and send her own signature n before Alice has a chance to send her signature to Bob. A more thorough examination of such protocols is considered in computer science courses focusing explicitly on the subject of cryptography.
[link]  
Protocol (Diffie-Hellman key exchange): We introduce the Diffie-Hellman key exchange protocol. This protocol is useful if two parties who cannot meet physically want to agree on a secret value that only they know.
  • Public key generation (performed by one party):
    1. Randomly choose a public large prime number p ∈ ℕ and an element g ∈ ℤ/pℤ.
  • Private key generation (performed by both parties):
    1. Party A randomly chooses a secret a ∈ ℤ/φ(p)ℤ.
    2. Party B randomly chooses a secret b ∈ ℤ/φ(p)ℤ.
  • Protocol:
    1. Party A computes (ga mod p) and sends this public value to party B.
    2. Party B computes (gb mod p) and sends this public value to party A.
    3. Party A computes (gb mod p)a mod p.
    4. Party B computes (ga mod p)b mod p.
    5. Since multiplication over ℤ/φ(p)ℤ is commutative, both parties now share a secret ga ⋅ b mod p.
This protocol's security only relies on the discrete logarithm assumption.
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.
[link]  
Protocol (RSA protocol): We introduce the RSA public-key cryptographic protocol. This protocol is useful in many scenarios, such as the following:
  • a sender wants to send the receiver a secret message over a public channel;
  • a receiver wants to allow any number of senders to send him messages over a public channel, and the receiver does not yet know who the senders will be.
This protocol can also be used to prove the identity of the receiver.
  • Key generation (performed by the receiver):
    1. Randomly choose two secret prime numbers p ∈ ℕ and q ∈ ℕ of similar size.
    2. Compute a public key value n = p ⋅ q.
    3. Compute the secret value φ(n) = (p-1) ⋅ (q-1).
    4. Choose a public key value e ∈ {2,...,φ(n)-1} such that gcd(e, φ(n)) = 1.
    5. Compute the secret private key d = e-1 mod φ(n)
  • Protocol (encryption and decryption): There are two participants: the sender and the receiver.
    1. The sender wants to send a message m ∈ {0,...,n-1} where gcd(m,n) = 1 to the receiver.
    2. The receiver reveals the public key (n,e) to the sender.
    3. The sender computes the ciphertext (encrypted message) c = me mod n.
    4. The sender sends c to the receiver.
    5. The receiver can recover the original message by computing m = cd mod n.
The above encryption-decryption process works because for some k ∈ ℤ:
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. In fact, the eavesdropper can also recover p and q.
[link]  
Protocol (Rabin cryptosystem): We introduce the Rabin cryptosystem protocol. It is similar to the RSA scheme, but it does not rely on the difficulty of the RSA problem.
  • Key generation (performed by the receiver):
    1. Randomly choose two secret prime numbers p ∈ ℕ and q ∈ ℕ of similar size.
    2. Compute a public key value n = p ⋅ q.
  • Protocol (encryption and decryption): There are two participants: the sender and the receiver.
    1. The sender wants to send a message m ∈ {0,...,n-1} to the receiver.
    2. The receiver reveals the public key n to the sender.
    3. The sender computes the ciphertext (encrypted message) c = m2 mod n.
    4. The sender sends c to the receiver.
    5. The receiver can recover the original message by computing √(c) in ℤ/pℤ and ℤ/qℤ, and then finding the four solutions to the following system by using the Chinese remainder theorem:
      m
      		≡
      √(c) mod p
      m
      		≡
      √(c) mod q.
Notice that the receiver must guess which of the square roots corresponds to the original message.
The following diagram summarizes the relationships between algorithms that might break each of the protocols presented in this section, and existing problems that are believed not to be in P. Thus, our conjectures imply that all of the problems below are not in P.
breaking
Rabin encryption		 ⇐ congruent squares
(square roots of
congruence classes)
⇑ ⇑
finding RSA
secret key		 ⇐ computing φ(n)
for n = p ⋅ q		 ⇐
⇒		 factoring
n = p ⋅ q
⇑ ⇑
decrypting individual
RSA messages		 ⇐ RSA problem
(eth roots of
congruence classes)
breaking
Diffie-Hellman		 ⇐ discrete logarithm
(logarithms of
congruence classes)

[link]  4.5. Assignment #4: Intractable Problems in Modular Arithmetic

In this assignment you will solve several equations, and you will define a collection of Python functions that demonstrate the relationships between intractable problems in modular arithmetic. You must submit a single Python source file named a4.py (submitted to the location hw4/a4.py). Please follow the gsubmit directions.

You may import the following library functions in your module (you may not need all these functions for this assignment depending on how you approach the problems, but they may be used):

from math import floor
from fractions import gcd
        
Your file may not import any other modules or employ any external library functions associated with integers and sets unless explicitly permitted to do so in a particular problem. Solutions to each of the programming problem parts below should be fairly concise. You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on the lecture notes and on each other; carefully consider whether you can use functions from the lecture notes, or functions you define in one part within subsequent parts.
  1. Solve the following equations using step-by-step equational reasoning, and list each step. Your solutions for this problem should appear as comments, delimited using '''...''', in a4.py. You may use the = ascii character to represent the ≡ relational operator on congruence classes.
    1. Solve the following equation for all solutions x ∈ ℤ/17ℤ (note that you cannot use the explicit formula in this case):
      x2
      		≡
      16 (mod 17)
    2. Solve the following equation for all solutions x ∈ ℤ/19ℤ:
      x2
      		≡
      5 (mod 19)
    3. Solve the following equation for all solutions x ∈ ℤ/33ℤ:
      x2
      		≡
      1 (mod 33)
    4. Solve the following equation for all solutions x ∈ ℤ/21ℤ:
      (2 ⋅ x2) + 5
      		≡
      16 (mod 21)
    5. Solve the following equation for all solutions x ∈ ℤ/49ℤ:
      x2
      		≡
      2 (mod 49)
  2. Implement the following Python functions for factoring a positive integer. These algorithms must be efficient (i.e., they must run in polynomial time).
    1. Implement a function factorsFromPhi(n, phi_n) that takes two integers n and phi_n. You may assume (i.e., you do not need to verify in your code) that n is a product of two distinct positive prime numbers and that phi_n = φ(n). The function should return both prime factors of n as a tuple.

      >>> factorsFromPhi(77, 60)
      (7, 11)
      >>> factorsFromPhi(14369648346682547857, 14369648335605206820)
      (9576890767, 1500450271)
                    
    2. Implement a function factorsFromRoots(n, x, y) that takes three integers n, x, and y. You may assume that n is a product of two distinct positive prime numbers, and that the following is true:
      x2
      		≡
      y2 (mod n)
      x
      		≢
      ± y (mod n)
      The function should return both prime factors of n as a tuple.

      >>> factorsFromRoots(35, 1, 6)
      (5, 7)
      >>> factorsFromRoots(14369648346682547857, 12244055913891446225, 1389727304093947647)
      (1500450271, 9576890767)
                    
  3. Suppose you are supplied with efficient implementations of algorithms for breaking the RSA, Diffie-Hellman, and Rabin cryptographic protocols. Below, we provide efficient implementations of such algorithms that only work on a few sample inputs (since we do not believe efficient algorithms for breaking these protocols exist, we must cheat in this way).

    # Efficiently computes (d, p, q) from (e, n).
    def secretFromPublicRSA(e, n): 
        input_output = {\
            (3, 22): (7, 2, 11),\
            (12358454755, 16461679220973794359): (14494300537577940091, 5754853343, 2860486313),\
            (1276890747, 19923108241787117701): (3754753864034662355, 3367900313, 5915587277)\
            }
        return input_output[(e, n)]

    # Efficiently computes (p, q) from n.
    def secretFromPublicRabin(n): 
        input_output = {\
            22: (2, 11),\
            8634871258069605953: (1500450271 , 5754853343),\ 
            16461679220973794359: (5754853343, 2860486313),\
            19923108241787117701: (3367900313, 5915587277)\
            }
        return input_output[n]
        
    # Efficiently computes x from (pow(g,x,p), g, p).
    def secretFromPublicDiffieHellman(c, g, p): 
        input_output = {\
            (5, 6, 17): 11,\
            (39011215311116229077, 4358934859, 71755440315342536873): 349543,\
            (12429507738024501208, 2388853717, 36413321723440003717): 598651\
            }
        return input_output[(c, g, p)]

    # Efficiently computes m from (pow(m,e,n), e, n).
    def decryptMsgRSA(c, e, n):
        input_output = {\
            (20, 3, 22): 4,\
            (15797173040326157838, 12358454755, 16461679220973794359): 237846739,\
            (9408372600079591252, 1276890747, 19923108241787117701): 489968371\
            }
        return input_output[(c, e, n)]

    # Efficiently computes m from (pow(m,2,n), n).
    def decryptMsgRabin(c, n):
        input_output = {\
            (14, 55): 17,\
            (122180308849, 16461679220973794359): 349543,\
            (240069004580393641, 19923108241787117701): 489968371\
            }
        return input_output[(c, n)]
             
    Implement the following Python functions for efficiently solving intractable problems in modular arithmetic. You may invoke any of the above algorithms in your solutions (you may assume that the above algorithms work on all inputs, not just those provided in the fake implementations above; your algorithms must work on all possible inputs under this assumption, not just those handled by the fake implementations above).
    1. Implement a function factor(n) that takes an integer n and returns both prime factors of n.

      >>> factor(16461679220973794359)
      (5754853343, 2860486313)
                    
    2. Implement a function root(b, a, n) that takes three integers a, b, and n and returns the ath root of b in ℤ/nℤ. You may assume that n is a product of two distinct prime numbers. In other words, it should be true that:
      root(pow(b, a, n), a, n)
      		≡
      b
      Note: the order of the arguments in the equation above did not originally match the example supplied below (the a and pow(b, a, n) parameters in the equation were switched from those in the example). Since this was discovered shortly before the assignment deadline, we will accept either order for the parameters in your implementation. We leave the sample input as it was originally, and adjust the equation above to match it.

      >>> root(15797173040326157838, 12358454755, 16461679220973794359)
      237846739
                    
    3. Implement a function dlog(a, b, p) that takes three integers a, b, and p and returns the discrete logarithm of a with respect to base b in ℤ/pℤ. You may assume that p is prime. In other words, it should be true that:
      pow(b, dlog(a, b, n), n)
      		≡
      a

      >>> dlog(39011215311116229077, 4358934859, 71755440315342536873)
      349543
                    
    4. Implement a function roots(a, n) that takes two integers a and n and returns all four square roots of a in ℤ/nℤ as a tuple. You may assume that n is the product of two distinct positive prime numbers. Hint: in addition to the decryption functions above, you may need to employ the Chinese remainder theorem.

      >>> roots(12187081, 8634871258069605953)
      (3491, 8634871258069602462, 1559172527496317142, 7075698730573288811)
                    
  4. In this problem you will implement an algorithm for computing all the square roots of a congruence class in ℤ/nℤ, given a complete factorization of n into its distinct prime factor powers (assuming all the prime factors are in 3 + 4ℤ).
    1. Implement a Python function sqrtsPrime(a, p) that takes two arguments: an integer a and a prime number p. You may assume that a and p are coprime. If p is not in 3 + 4ℤ or a has no square roots in ℤ/pℤ, the function should return None. Otherwise, it should return the two congruence classes in ℤ/pℤ that solve the following equation:
      x2
      		≡
      a (mod p)

      >>> sqrtsPrime(2, 7)
      (3, 4)
      >>> sqrtsPrime(5, 7) # 5 has no square roots
      None
      >>> sqrtsPrime(5, 17) # 17 mod 4 =/= 3
      None
      >>> sqrtsPrime(763472161, 5754853343)
      (27631, 5754825712)
                    
    2. Implement a Python function sqrtsPrimePower(a, p, k) that takes three arguments: an integer a, a prime number p, and a positive integer k. You may assume that a and p are coprime. If p is not in 3 + 4ℤ or a has no square roots in ℤ/pkℤ, the function should return None. Otherwise, it should return the congruence classes in ℤ/pkℤ that solve the following equation:
      x2
      		≡
      a (mod pk)

      >>> sqrtsPrimePower(2, 7, 2)
      (10, 39)
      >>> sqrtsPrimePower(763472161, 5754853343, 4)
      (27631, 1096824245608362247285266960246506343570)
                    
    3. Implement a Python function sqrts(a, pks) that takes two arguments: an integer a and a list of tuples pks in which each tuple is a distinct positive prime number paired with a positive integer power. You may assume that a and n are coprime. You may assume that all the primes in pks are in 3 + ℤ/4ℤ (if any are not, the function should return None). Let n be the product of all the prime powers in the list pks. Then the function should return a set of all the distinct square roots of a in ℤ/nℤ that are solutions to the following equation:
      x2
      		≡
      a (mod n)
      Your implementation must be efficient (i.e., it may not iterate over all possible values in ℤ/nℤ to look for square roots), and it must work for any positive number of entries in pks.

      >>> sqrts(2, [(7,4)])
      {235, 2166}
      >>> sqrts(1, [(7,1), (11,1)])
      {1, 76, 43, 34}
      >>> sqrts(1, [(7,1), (11,1), (3,1)])
      {1, 76, 43, 34, 155, 188, 197, 230}
      >>> sqrts(1, [(7,2), (11,1), (3,2)])
      {1, 197, 881, 1079, 3772, 3970, 4654, 4850}
      >>> sqrts(1, [(7,1), (11,1), (3,1), (19,1)])
      {1, 265, 419, 1198, 1310, 1462, 1616, 1882, 2507, 2773, 2927, 3079, 3191, 3970, 4124, 4388}
      >>> sqrts(76349714515459441, [(1500450271,3), (5754853343,2)])
      {276314521,
       111875075121925861006908948065990250824231090118,
       50900491283175338098734392241768315796265192809,
       60974583838750522908174555824221935028242211830}
                    

[link]  Review #1. Properties, Algorithms, and Applications of Modular Arithmetic

This section contains a comprehensive collection of review problems going over the course material covered until this point. Many of these problems are an accurate representation of the kinds of problems you may see on an exam.
[link]  
Exercise: For some a ∈ ℕ, suppose that a-1 ∈ ℤ/21ℤ and a-1 ∈ ℤ/10ℤ (that is, a has an inverse in ℤ/21ℤ, and it also has an inverse in ℤ/10ℤ). Determine whether or not a has an inverse in ℤ/210ℤ. Explain why or why not. Hint: use gcd.
If a has an inverse in ℤ/10ℤ and ℤ/21ℤ, then gcd(a,10) = 1 and gcd(a,21) = 1. Since gcd(10,21) = 1, a shares no factors with the product 10 ⋅ 21 = 210, so gcd(a, 210) = 1. Thus, a must have a multiplicative inverse in ℤ/210ℤ.
[link]  
Exercise: Bob is trying to implement a random number generator. However, he's distracted and keeps making mistakes while building his implementation.
  1. Bob begins his algorithm by generating two coprime numbers a and m such that gcd(a,m) = 1. However, he mixes them up and defines the following computation:
    [      (i ⋅ m) mod a      |      i ∈ {1,...,a-1}      ]
    Is Bob going to get a permutation? Why or why not?
    Yes, Bob will still get a permutation because gcd(a,m) = 1, which means m mod a is also coprime with m (we can see this because this is exactly what the extended Euclidean algorithm computes before making a recursive call, or by observing that if m mod a shares a factor with a, so must m).
  2. Bob notices part of his mistake and tries to fix his algorithm; he ends up with the following:
    [      (i ⋅ m) mod m      |      i ∈ {1,...,m-1}      ]
    How many distinct elements does the list he gets in his output contain?
    It contains exactly one element: 0 (mod m), since all multiples of the congruence class m are equivalent to 0 (mod m).
  3. Bob notices his algorithm isn't returning a permutation, but he mixes up a few theorems and attempts the following fix:
    [      (i ⋅ am-1) mod m      |      i ∈ {1,...,m-1}      ]
    Bob tests his algorithm on some m values that are prime numbers. How many elements does the set he gets in his output contain?
    It contains all the elements {1,...,m-1}, generated in ascending order, since by Fermat's little theorem, am-1 ≡ 1 (mod m) if m is prime.
  4. Bob doesn't like the fact that his permutation doesn't look very random, so he moves the i term to the exponent:
    [      (ai ⋅ (m-1)) mod m      |      i ∈ {1,...,m-1}      ]
    Bob tests his algorithm on some m values that are prime numbers. How many elements does the set he gets in his output contain?
    It contains exactly one element: 1 (mod m), since by the consequences of Fermat's little theorem and Euler's theorem, if m is prime we have:
    ak
    		≡
    ak mod φ(m) (mod m)
    		≡
    ak mod (m-1) (mod m)
[link]  
Exercise: Suppose you have the following instance of Bézout's identity: 2 ⋅ 3 + (−1) ⋅ 5 = 1. Solve the following system of equations:
x
≡
2 (mod 3)
x
≡
3 (mod 5)
Given 3-1 ≡ 2 (mod 5), and 5-1 ≡ −1 ≡ 2 (mod 3), the formula for the solution is:
x
≡
2 ⋅ (5 ⋅ 5-1) + 3 ⋅ (3 ⋅ 3-1) mod (3 ⋅ 15)
≡
2 ⋅ (5 ⋅ 2) + 3 ⋅ (3 ⋅ 2)
≡
20 + 18 mod 15
≡
38 mod 15
≡
8 mod 15
[link]  
Exercise: Solve the following system of equations:
x
≡
2 (mod 7)
x
≡
3 (mod 5)
To demonstrate an alternative but inefficient method to find a solution, we can list the positive members of the equivalence classes 2 ∈ ℤ/7ℤ and 3 ∈ ℤ/5ℤ that are less than 7 ⋅ 5 = 35. The one element that appears in both lists is the unique solution in ℤ/35ℤ to the above system.
2 + 7ℤ
=
{..., 2, 9, 16, 23, 30, ...}
3 + 5ℤ
=
{..., 3, 8, 13, 18, 23, 28, 33, ...}
[link]  
Exercise: Determine the size of the following set:
{x | x ∈ ℤ/(11 ⋅ 13)ℤ,      x ≡ 5 mod 11,      x ≡ 7 mod 13}
By the Chinese remainder theorem, we know there exists exactly one solution in ℤ/(11 ⋅ 13)ℤ to the following system of equations:
x
≡
5 (mod 11)
x
≡
7 (mod 13)
Thus, the size of the set is 1.
[link]  
Exercise: For a given y ∈ ℤ/(p ⋅ q)ℤ where p and q are distinct primes, how many solutions does the following system of equations have:
x
≡
y2 (mod p)
x
≡
y2 (mod q)
The value y2 ∈ ℤ/(p ⋅ q)ℤ is a constant with respect to x, so by the Chinese remainder theorem, there is exactly one solution x ∈ ℤ/(p ⋅ q)ℤ to the above system.
[link]  
Exercise: Determine the size of the following set:
{x | x ∈ ℤ/(11 ⋅ 13)ℤ,      s ∈ ℤ/11ℤ,      t ∈ ℤ/13ℤ,      x ≡ s mod 11,      x ≡ t mod 13 }
Consider the following set. Notice that the right-hand side of the comprehension is exactly the same as that of the above. The only difference is that the left-hand side x in the above expression has been replaced with (x, s, t).
{(x, s, t) | x ∈ ℤ/(11 ⋅ 13)ℤ, s ∈ ℤ/11ℤ, t ∈ ℤ/13ℤ, x ≡ s mod 11, x ≡ t mod 13 }
By the Chinese remainder theorem, we know that exactly one tuple (x, s, t) for each x ∈ ℤ/(11 ⋅ 13)ℤ will satisfy the conditions in the comprehension, because for each distinct pair (s, t), exactly one x ∈ ℤ/(11 ⋅ 13)ℤ will be a solution to the system of equations:
x
≡
s (mod 11)
x
≡
t (mod 13)
Thus, the conditions in the comprehension will be satisfied at least once for every x ∈ ℤ/(11 ⋅ 13)ℤ. Thus, the entire set is exactly the set ℤ/(11 ⋅ 13)ℤ, and it is the case that
|ℤ/(11 ⋅ 13)ℤ|
=
11 ⋅ 13
=
143
[link]  
Exercise: Suppose that n ∈ ℕ is even and n/2 − 1 is odd. Determine the size of the following set:
{i ⋅ (n/2 - 1) mod n | i ∈ {0,...,n-1} }
We know that gcd(n/2 − 1, n/2) = 1. Since n/2 − 1 is odd, 2 is not a factor of n/2 − 1, so gcd(n/2 − 1, n) = 1. Thus, n/2 − 1 and n are coprime. Thus, the above set must be a permutation.
[link]  
Exercise: For any n ∈ ℕ, let a ∈ ℤ/nℤ have an inverse a-1 ∈ ℤ/nℤ. Determine the size of the following set:
{ (a ⋅ i) mod n | i ∈ ℤ/nℤ }
If a has an inverse in ℤ/nℤ (whether or not n is prime), then gcd(a, n) = 1, so the above set must be a permutation.
[link]  
Exercise: Let p be a prime number. Compute the set size |ℤ/pℤ - (ℤ/pℤ)*|.
Since (ℤ/pℤ)* is the set of elements of ℤ/pℤ that have multiplicative inverses, it is the set of elements a ∈ ℤ/pℤ such that gcd(a, p) = 1. However, because p is prime, all of the elements in ℤ/pℤ except 0 have this property (since gcd(p, 0) = p; recall that 0/p ∈ ℤ and p|0). Thus,
ℤ/pℤ - (ℤ/pℤ)*
=
{0}
Thus, |ℤ/pℤ - (ℤ/pℤ)*| = 1.

Alternatively, we know that |ℤ/pℤ| = p and |(ℤ/pℤ)*| = φ(p) = p − 1, and p − (p − 1) = 1.
[link]  
Exercise: In a game, you win if you can guess correctly whether a large number n is prime in under a minute (if you are wrong, you win nothing and you lose nothing). You are given a handheld calculator that can only perform addition, subtraction, multiplication, division, exponentiation, and modulus (the calculator can represent arbitrarily large numbers, and can provides quotients to any precision). Describe one strategy you can use to give yourself a high probability of winning.
If you pick a few random a ∈ {2,...,n-1} and compute an-1 mod n, if the result is ever greater than 1 (i.e., the Fermat primality test) then a would be a witness that n is composite. You would then be able to say with certainty that p is not prime, winning the game. Once time is about to run out, you should guess that the number is prime.
[link]  
Exercise: Suppose that n ∈ ℕ. Compute the following:
534 ⋅ n + 1 mod 11
We can compute the exponent 34 ⋅ n + 1 modulo φ(11) by Euler's theorem, because gcd(5,11) = 1. Likewise, we can compute the exponent within the exponent, 4 ⋅ n + 1, modulo φ(φ(11)) because gcd(3,φ(11)) = 1. Thus, we have:
φ(11)
=
11 - 1
=
10
φ(10)
=
φ(5) ⋅ φ(2)
=
(5-1) ⋅ (2-1)
=
4
534 ⋅ n + 1 mod 11
=
534 ⋅ n + 1 mod φ(φ(11)) mod φ(11) mod 11
=
534 ⋅ n + 1 mod 4 mod 10 mod 11
=
531 mod 10 mod 11
=
53 mod 11
=
(25 ⋅ 5) mod 11
=
(3 ⋅ 5) mod 11
=
15 mod 11
=
4 mod 11
[link]  
Exercise: Suppose we make the following simplifications:
  • the Earth rovolves around the sun once per year;
  • the asteroid Ceres rovolves around the sun every 5 years;
  • the planet Jupiter revolves around the sun every 11 years.
Suppose that on June 21st, 2000, the Earth, Ceres, and Jupiter all align (i.e., one can draw a straight line through all three).
  1. Which two of these objects will align again on June 21st, and in which year?
    The next time Earth and Ceres align will be in five years, in 2005, as x = 5 is the smallest non-zero solution in ℕ to the following system (the first equation represents alignment with Earth; the second equation represents alignment with Ceres):
    x
    		≡
    0 mod 1
    x
    		≡
    0 mod 5
  2. How many years will pass before all three align again?
    The smallest non-zero solution in ℕ to the following system is x = 55, so they will all align again in 2055:
    x
    		≡
    0 mod 1
    x
    		≡
    0 mod 5
    x
    		≡
    0 mod 11
  3. Suppose that it is June 21st of some year between 2000 and 2055. At this time, there is no alignment. However, Jupiter aligned with earth on June 21st four years ago, and Ceres aligned with Earth on June 21st one year ago. What year is it?
    The following system of equations captures the situation. Since the solution must be in ℤ/55ℤ, we can find a unique solution using the Chinese remainder theorem. By inspection of the elements of 4 + 11ℤ = {4, 15, 26, ...}, the solution is x = 26.
    x
    		≡
    0 mod 1
    x
    		≡
    1 mod 5
    x
    		≡
    4 mod 11
    Alternatively, we can use the formula; since x ≡ 0 (mod 1) is true for all x, there are actually only two equations:
    x
    		≡
    1 mod 5
    x
    		≡
    4 mod 11
    Since 11 ≡ 1 (mod 5), 11-1 ≡ 1 (mod 5); we also have:
    5-1
    		≡
    59 (mod 11)
    		≡
    254 ⋅ 5
    		≡
    34 ⋅ 5
    		≡
    5 ⋅ 3 ⋅ 5
    		≡
    4 ⋅ 5
    		≡
    9
    Then the solution is:
    x
    		≡
    1 ⋅ (11 ⋅ 1) + 4 ⋅ (5 ⋅ 9) (mod (5 ⋅ 11))
    		≡
    11 + 180
    		≡
    191
    		≡
    26
[link]  
Exercise: Suppose there exist two devices, where one can either produce or consume exactly 2 units of power and another can either produce or consume exactly 7 units of power:
  • device A: +/− 2 units
  • device B: −/+ 7 units
Suppose we want to produce exactly 1 unit of power using a combination of some number of A devices and B devices. Is this possible?
Yes, this is possible because 2 and 7 are coprime, so there exists an instance of Bézout's identity of the form 2 ⋅ s + 7 ⋅ t = 1.
[link]  
Exercise: Suppose Eve asks Alice for some sensitive information, so Alice requests that they employ the RSA protocol. However, Eve wants to conserve resources, so she cheats. Eve chooses a large prime p, picks an e ∈ ℤ/(p-1)ℤ, and tells Alice that (p,e) is her public key.
  1. Suppose another eavesdropper, Carl, learns that Eve is cheating this way. Can he decrypt Alice's messages if he intercepts them in transit?
    2. Yes. Carl can easily compute d = e-1 mod φ(p) because he can compute φ(p) = p-1 given the public value p. Given any ciphertext me mod p, he can compute (me)d mod p = m to decrypt it.
  2. What can Alice do to check whether Eve is cheating before she transmits any "encrypted" messages to her?
    Alice can use the Fermat primality test to check whether the n in Eve's public key (n,e) is probably prime or composite. If the Fermat primality test indicates that n is composite (i.e., Alice finds a witness a ∈ ℤ/nℤ that n is composite because an-1 mod n ≠ 1), Alice can agree to send encrypted messages to Eve.
  3. What can Eve do to keep cheating but make it computationally more difficult for Alice to catch her?
    If Eve tells Alice that she will always use a Carmichael number n for all her public keys, Alice will have a harder time detecting when Eve is cheating (i.e., if Alice is unable to find witnesses, Alice has no way of knowing whether this is because Eve is cheating and using a prime, or because Eve is using a Carmichael number for n).

    However, Alice can adopt a policy that makes it impossible for Eve to cheat if she wants to communicate with Alice. Alice can announce that she will only send messages to Eve if Alice is able to quickly find a Fermat witness for n. If Alice cannot find a witness quickly, Alice will request that the receiver generate a new n and a new public key (n, e).

    Assuming Eve does not want to cheat, but wants to communicate with Alice, it is likely that any n Eve generates will not be a Carmichael number, and if so, it is likely that Alice will be able to quickly detect that the n is composite. Thus, adopting such a policy is very unlikely to impair Alice's ability to communicate with an honest receiver.

    Notice that simply encrypting some test messages and then trying to decrypt them in order to detect whether Eve is cheating can lead to false positive. As we saw in the previous problem, some ciphertexts may be exactly the same as the message being sent (by coincidence).
The following is a breakdown of what you should be able to do at this point in the course (and of what you may be tested on in an 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 permutation of a set {1,...,m-1}
    • generate a "random" number using permutations
    • find the greatest common divisor of two relatively small integers
    • 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 x1 ⊕ ... ⊕ xn 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 pi in ℤ/piℤ, and then performing CRT once is less expensive than working in ℤ/nℤ the whole time
    • solving equations and performing computations
      • solve a system of linear equations where each equation is modulo some ni and the coefficient is coprime with the moduli
        • derive a system of equations from a word problem
          • rotating objects
          • objects that generate/consume different amounts of power
          • Shamir secret sharing and applications
        • 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 ℤ/nℤ
        • using φ(n)
        • using a given output from the extended Euclidean algorithms or (equivalently) an instance of Bézout's identity
    • 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

[link]  5. Algebraic Structures

In the previous sections, we studied a specific algebraic structure, ℤ/nℤ, as well as its operations (e.g., addition, multiplication), and its properties (commutativity, associativity, and so on). There exist many other algebraic structures that share some of the properties of ℤ/nℤ. In fact, we can create a hierarchy, or even a web, of algebraic structures by picking which properties of ℤ/nℤ we keep and which we throw away.

Showing that some new algebraic structure is similar or equivalent to another, more familiar structure allows us to make inferences about that new structure based on everything we already know about the familiar structure. In computer science, the ability to compare algebraic structures using their properties is especially relevant because every time a programmer defines a new data structure and operations on that data structure, they are defining an algebraic structure. Which properties that algebraic structure possesses determines what operations can be performed on it, in what order they can be performed, how efficiently they can be performed, and how they can be broken down and reassembled.

[link]  5.1. Permutations

Recall that a permutation on a set X is a bijective relation between X and X (i.e., a subset of the set product X × X). Since a permutation is a bijective 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. We will adopt the following notation for permutations:
[a1,...,an]
Where a1,...,an is some rearrangement of the integers from 0 to n-1. For example, the identity permutation on n elements would be:
[0,1,2,3,4,5,...,n-1]
[link]  
Definition: Any permutation that swaps exactly two elements is called a swap. Examples of swaps are [0,3,2,1], [1,0], and [0,6,2,3,4,5,1].
[link]  
Definition: Any permutation that swaps exactly two adjacent elements is called an adjacent swap. Examples of adjacent swaps are [0,1,3,2], [1,0,2,3,4], and [0,1,3,2,4,5,6].
[link]  
Definition: Define Sn to be the set of all permutations of the set {0,...,n-1}.
[link]  
Example: The set of permutations of {0,1} is S2 = {[0,1], [1,0]}.
[link]  
Example: The set of permutations of {0,1,2} is S3 = {[0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]}.
[link]  
Fact: The set Sn contains n! permutations.

Suppose we want to construct a permutation [a1,...,an] using the elements in {0,...,n-1}, where we are only allowed to take each element in the set once and assign it to an unassigned entry ai. Then for the first slot, we have n possibilities; for the second, we have n-1 possibilities. For the third, we have n-2 possibilities, and so on until we have only one possibility left. Thus, the number of possible permutations we can make is:
n!
=
n ⋅ (n-1) ⋅ (n-2) ⋅ ... ⋅ 2 ⋅ 1
[link]  
Definition: Define the set Cn to be the set of all cyclic permutations on n elements. Any permutation that performs a circular shift on elements is a cyclic permutation (also known as a cyclic shift permutation, a circular shift permutation, or just a shift permutation). Examples of shifts are [6,7,0,1,2,3,4,5], [2,3,4,0,1], and [4,0,1,2,3].
[link]  
Definition: Define the set Mn to be the set of all multiplication-induced permutations on n elements. Any permutation on n elements that corresponds to multiplication by some coprime a < n is called a multiplication-induced permutation. Examples of such permutations include [0,2,4,1,3] (corresponding to multiples 2 ⋅ i for ascending i in ℤ/5ℤ).
[link]  
Example: The set of multiplication-induced permutations on 6 elements (i.e., permutations of {0,1,2,3,4,5}) is the collection of permutations of the form [a ⋅ 0 mod 6, a ⋅ 1 mod 6, a ⋅ 2 mod 6, a ⋅ 3 mod 6, a ⋅ 4 mod 6, a ⋅ 5 mod 6] for each a that is coprime with 6. Thus, a ∈ {1,5}, and so we have:
M6 = {[0,1,2,3,4,5], [0,5,4,3,2,1]}.
[link]  
Example: The set of multiplication-induced permutations on 7 elements (i.e., permutations of {0,1,2,3,4,5,6}) is:
M7 = {[0,1,2,3,4,5,6], [0,2,4,6,1,3,5], [0,3,6,2,5,1,4], [0,4,1,5,2,6,3], [0,5,3,1,6,4,2], [0,6,5,4,3,2,1]}.
Note that |M7| = φ(7) = 6 because there are 6 possible a ∈ ℤ/7ℤ that are coprime with 7.

[link]  5.2. Algebraic Structures and Axioms

An algebraic structure is a set together with a binary operator over that set. All algebraic structures are closed under their binary operation.
[link]  
Definition: Let S be a set, and let ⊕ be a binary operator. Let closure(S,⊕) be the closure of S under ⊕. We can define the set closure(S,⊕) in the following way:
closure(S, ⊕)
=
{ x1 ⊕ x2 | x1,x2 ∈ S } ∪ { x1 ⊕ (x2 ⊕ x3) | x1,x2,x3 ∈ S } ∪ { (x1 ⊕ x2) ⊕ x3 | x1,x2,x3 ∈ S } ∪ ...
Alternatively, we could define it in the following way using recursion:
closure0(S, ⊕)
=
S
closuren(S, ⊕)
=
{ x ⊕ y | x,y ∈ (closuren-1(S, ⊕) ∪ ... ∪ closure0(S, ⊕)}
closure(S, ⊕)
=
closure0(S, ⊕) ∪ closure1(S, ⊕) ∪ closure2(S, ⊕) ∪ ...
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.
Furthermore, algebraic structures can be categorized according to the additional algebraic properties they possess. In this section we introduce terminology for several common types of algebraic structure.
[link]  
Definition: Let G be a set, and let (A, ⊕) be an algebraic structure where A = closure(G, ⊕). In this case, we call A a magma and we call G the generating set or the set of generators of A.

In other words, a set A is a magma under operator ⊕ if:
  • A is closed under ⊕ (i.e., for all x, y ∈ A, x ⊕ y ∈ A).
If (A, ⊕) possesses no other algebraic properties, we say (A, ⊕) is a free magma, or that (A, ⊕) is strictly a magma.
[link]  
Definition: We call an algebraic structure (A, ⊕) a semigroup under ⊕ if:
  • A is closed under ⊕;
  • ⊕ is associative on A (for all x,y,z ∈ A, the equation (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) is true).
If (A, ⊕) possesses no other algebraic properties, we call it a free semigroup or we say it is strictly a semigroup.
[link]  
Definition: We call an algebraic structure (A, ⊕) a monoid under ⊕ if:
  • A is closed under ⊕;
  • ⊕ is associative on A;
  • A contains an identity (which we call 1) in A (where for all x ∈ A, the equations 1 ⊕ x = x and x ⊕ 1 = x are always true).
If (A, ⊕) possesses no other algebraic properties, we call it a free monoid or we say it is strictly a monoid.
[link]  
Definition: We call an algebraic structure (A, ⊕) a group under ⊕ if:
  • A is closed under ⊕;
  • ⊕ is associative on A;
  • A contains an identity;
  • A has inverses with respect to ⊕ (for all x ∈ A, there exists x-1 ∈ A such that x ⊕ x-1 = 1 and x-1 ⊕ x = 1 are always true).
If (A, ⊕) possesses no other algebraic properties, we call it a free group or we say it is strictly a group.
[link]  
Definition: We call an algebraic structure (A, ⊕) an abelian group under ⊕ if:
  • A is closed under ⊕;
  • ⊕ is associative on A;
  • A contains an identity;
  • A has inverses with respect to ⊕;
  • ⊕ is commutative on A (i.e., for all x,y ∈ A, the equation x ⊕ y = y ⊕ x is always true).
[link]  
Fact: Define Sn to be the set of permutations of the set {0,...,n-1}. Together with the binary composition operation o on permutations, Sn is a group, and we call it the symmetric group on n element:
  • Sn is closed under composition of permutations (since Sn contains all of them);
  • composition of functions (including permutations) is associative;
  • there is an identity permutation [0,1,2,3,4,5,...,n-1];
  • every permutation p ∈ Sn has an inverse p-1 ∈ Sn such that p o p-1 = [0,1,...,n-1].
Notice that Sn is not commutative.
[link]  
Fact: The set of cyclic permutations Cn is an abelian group (i.e., it is a commutative group).
[link]  
Fact: The set of multiplication-induced permutations Mn is an abelian group (i.e., it is a commutative group).
[link]  
Fact: For any n ∈ ℕ, the algebraic structures (ℤ/nℤ, +) and ((ℤ/nℤ)*, ⋅) are abelian groups.

[link]  5.3. Isomorphisms: Equivalence of Algebraic Structures

The concept of an isomorphism between two algebraic structures captures the fact that two structures are not only the same size, but that the two structures have the same internal "structure" with respect to their respective operations. Isomorphisms are useful because they allow us to learn more about a structure by studying the structure isomorphic to it. They can also be useful because if two structures are isomorphic, we can perform computations in one structure instead of another structure (e.g., because it is more secure, more efficient, and so on) while obtaining the same final result.
[link]  
Fact: Let A be an algebraic structure with operator ⊕ and let B be an algebraic structure with operator ⊗. We say that A is isomorphic to B, which we denote as (A,⊕) ≅ (B,⊗) or simply A ≅ B, if the following conditions hold:
  • there exists a bijection (i.e., a bijective relation) between A and B, which we denote using  = ;
  • for all a, a' ∈ A and b,b' ∈ B, if a = b and a' = b' then a ⊕ a' = b ⊕ b'.
Another way to state the definition is to write it in terms of a bijective map m between A and B:
  • there exists a bijective map m between A and B;
  • for all a, a' ∈ A,      m(a ⊕ a') = m(a) ⊗ m(a').
In other words, an isomorphism is a bijection that preserves (or respects) the binary operations on the two sets: if any true equation involving elements from A and the operator ⊕ is transformed by replacing all elements of a with their corresponding elements m(b) ∈ B and by replacing all instances of ⊕ with ⊗, the resulting equation is still true.
[link]  
Example: Consider the set of permutations on two elements S2 and the set of congruence classes ℤ/2ℤ. It is true that (S2,o) ≅ (ℤ/2ℤ,+), where o is composition of permutations and where + is addition of congruence classes in ℤ/2ℤ. The following table demonstrates the bijection:
S2 ℤ/2ℤ
[0,1] 0
[1,0] 1
The following table demonstrates that the bijection above respects the two operations.
S2 ℤ/2ℤ
[0,1] o [0,1] = [0,1] 0 + 0 = 0
[0,1] o [1,0] = [1,0] 0 + 1 = 1
[1,0] o [0,1] = [1,0] 1 + 0 = 1
[1,0] o [1,0] = [0,1] 1 + 1 = 0
Another way to demonstrate the above is to show that the "multiplication tables" (though the operation need not be multiplication) for the two operators are exactly the same (i.e., the entries in the multiplication table all correspond according to the bijection).
+
o		 0
[0,1]		 1
[1,0]
0
[0,1]		 0
[0,1]		 1
[1,0]
1
[1,0]		 1
[1,0]		 0
[0,1]
[link]  
Fact: For any positive integer n ∈ ℕ, (ℤ/nℤ,+) ≅ (Cn, o).
[link]  
Example: Consider the set of cyclic permutations on three elements C3 and the set of congruence classes ℤ/3ℤ. It is true that (C3,o) ≅ (ℤ/3ℤ,+).
C3ℤ/3ℤ
[0,1,2] o [0,1,2] = [0,1,2]0 + 0 = 0
[0,1,2] o [1,2,0] = [1,2,0]0 + 1 = 1
[0,1,2] o [2,0,1] = [2,0,1]0 + 2 = 2
[1,2,0] o [0,1,2] = [1,2,0]1 + 0 = 1
[1,2,0] o [1,2,0] = [2,0,1]1 + 1 = 2
[1,2,0] o [2,0,1] = [0,1,2]1 + 2 = 0
[2,0,1] o [0,1,2] = [2,0,1]2 + 0 = 2
[2,0,1] o [1,2,0] = [0,1,2]2 + 1 = 0
[2,0,1] o [2,0,1] = [1,2,0]2 + 2 = 1
[link]  
Example: To compute the composition of two permutations [45,46,...,49,0,1,2,...,44] o [3,4,5,...,49,0,1,2], it is sufficient to recognize that [45,46,...,49,0,1,2,...,44] corresponds to 45 ∈ ℤ/50ℤ, and [3,4,5,...,49,0,1,2] corresponds to 3 ∈ ℤ/50ℤ. Thus, since 45 + 3 = 48, the result of the composition must be [48,49,0,1,2,...,47].
45 + 3
=
48
[45,46,...,49,0,1,2,...,44] o [3,4,5,...,49,0,1,2]
=
[48,49,0,1,2,...,47]
[link]  
Fact: For any prime p ∈ ℕ, (ℤ/φ(p)ℤ,+) ≅ ((ℤ/pℤ)*, ⋅).

Note that |ℤ/φ(p)ℤ| = φ(p) = |(ℤ/pℤ)*|.
[link]  
Example: Consider the set ℤ/2ℤ with the addition operation + modulo 2, and the set (ℤ/3ℤ)* together with the multiplication operation ⋅ modulo 3. It is true that (ℤ/2ℤ, +) ≅ ((ℤ/3ℤ)*,⋅).
(ℤ/2ℤ, +) ((ℤ/3ℤ)*, ⋅)
0 + 0 = 0 1 ⋅ 1 = 1
0 + 1 = 1 1 ⋅ 2 = 2
1 + 0 = 1 2 ⋅ 1 = 2
1 + 1 = 0 2 ⋅ 2 = 1
[link]  
Example: Consider the set ℤ/2ℤ with the addition operation + modulo 2, and the set (ℤ/6ℤ)* together with the multiplication operation ⋅ modulo 6. It is true that (ℤ/2ℤ, +) ≅ ((ℤ/6ℤ)*,⋅). Note that (ℤ/6ℤ)* = {1,5}, because only 1 and 5 in the range {0,...5} are coprime with 6.
(ℤ/2ℤ, +) ((ℤ/6ℤ)*, ⋅)
0 + 0 = 0 1 ⋅ 1 = 1
0 + 1 = 1 1 ⋅ 5 = 5
1 + 0 = 1 5 ⋅ 1 = 5
1 + 1 = 0 5 ⋅ 5 = 1
Isomorphisms need not be defined between different sets. It is possible to define an isomorphism between a set and itself that has non-trivial, interesting, and even useful characteristics.
[link]  
Fact: For any n ∈ ℕ and any a ∈ ℤ/nℤ where a is coprime with n, (ℤ/nℤ,+) ≅ (ℤ/nℤ,+) under the bijection that relates x ∈ ℤ/nℤ with a ⋅ x ∈ ℤ/nℤ. This is because for any x,y ∈ ℤ/nℤ, we have:
a ⋅ (x + y)
≡
a ⋅ x + a ⋅ y
[link]  
Fact: For any n ∈ ℕ and any e ∈ ℤ/φ(n)ℤ where e is coprime with φ(n), ((ℤ/nℤ)*,⋅) ≅ ((ℤ/nℤ)*,⋅) under the bijection that relates x ∈ (ℤ/nℤ)* with xe ∈ (ℤ/nℤ)*. This is because for any x, y ∈ (ℤ/nℤ)*, we have:
(x ⋅ y)e
≡
xe ⋅ ye (mod n)
[link]  
Example: Consider the set ℤ/3ℤ with the addition operation + modulo 3, and another instance of the set ℤ/3ℤ with the addition operation + modulo 3. The following is a bijection between (ℤ/3ℤ, +) and (ℤ/3ℤ, +):
ℤ/3ℤℤ/3ℤ
00
12
21
This bijection is an isomorphism:
ℤ/3ℤℤ/3ℤ
0 + 0 = 00 + 0 = 0
0 + 1 = 10 + 2 = 2
0 + 2 = 20 + 1 = 1
1 + 0 = 12 + 0 = 2
1 + 1 = 22 + 2 = 1
1 + 2 = 02 + 1 = 0
2 + 0 = 21 + 0 = 1
2 + 1 = 01 + 2 = 0
2 + 2 = 11 + 1 = 2
[link]  
Example (homomorphic encryption supporting addition): Suppose that for some n ∈ ℕ, Alice wants to store a large number of congruence classes b1,...,bk ∈ ℤ/nℤ in Eve's database (perhaps Alice will generate or collect these over a long period of time). Alice does not have enough memory to store the congruence classes herself, but she does not want to reveal the congruence classes to Eve.

What Alice can do before she stores anything in Eve's database is to pick some secret a ∈ ℤ/nℤ that is coprime with n. Then, every time Alice needs to store some b in Eve's database, Alice will instead send Eve the obfuscated value (a ⋅ b) mod n. Since a is coprime with n, there exists a-1 ∈ ℤ/nℤ. Thus, if Alice retrieves some obfuscated data entry c from Eve's database, she can always recover the original value by computing (a-1 ⋅ c) mod n, because:
a-1 ⋅ (a ⋅ b)
≡
b (mod n)
Furthermore, Alice can ask Eve to compute the sum (modulo n) of all the entries in the database (or any subset of them). Suppose that Alice has stored obfuscated versions of b1,...,bk ∈ ℤ/nℤ in Eve's database. Then if Eve computes the sum of all the obfuscated entries stored in her database, she will get:
a ⋅ b1 + ... + a ⋅ bk
=
a ⋅ (b1 + ... + bk) (mod n)
Thus, if Alice asks Eve for the sum of all the obfuscated entries in the database, Alice can recover the actual sum of the original entries that she stored in the database because:
a-1 ⋅ (a ⋅ (b1 + ... + bk))
=
b1 + ... + bk (mod n)
In this way, Alice has avoided having to store and add all the database entries, while preventing Eve finding out the actual entries, or their sum.
[link]  
Example (homomorphic encryption supporting multiplication): Suppose that for some n ∈ ℕ, Alice wants to store a large number of congruence classes b1,...,bk ∈ (ℤ/nℤ)* in Eve's database. Alice does not have enough memory to store the congruence classes herself, but she does not want to reveal the congruence classes to Eve.

We assume that Alice knows or can easily compute φ(n), while Eve does not know and cannot compute it (perhaps Alice generated n using a method similar to the one in RSA encryption protocol).

What Alice can do before she stores anything in Eve's database is to pick some secret e ∈ ℤ/φ(n)ℤ that is coprime with φ(n). Since Alice knows e and φ(n), she can compute e-1 using the extended Euclidean algorithm.

Then, every time Alice needs to store some b in Eve's database, Alice will instead send Eve the encrypted value be mod n. If Alice retrieves some encrypted data entry c from Eve's database, she can always recover the original value by computing (ce-1}) mod n, because by Euler's theorem:
(be)e-1
≡
be ⋅ e-1
≡
b (mod n)
Furthermore, Alice can ask Eve to compute the product (modulo n) of all the entries in the database (or any subset of them). Suppose that Alice has stored encrypted versions of b1,...,bk ∈ ℤ/nℤ in Eve's database. Then if Eve computes the product of all the encrypted entries stored in her database, she will get:
b1e ⋅ ... ⋅ bke
=
(b1 ⋅ ... ⋅ bk)e (mod n)
Thus, if Alice asks Eve for the product of all the encrypted entries in the database, Alice can recover the actual product of the original entries that she stored in the database because:
((b1 ⋅ ... ⋅ bk)e)e-1
=
b1 ⋅ ... ⋅ bk (mod n)
In this way, Alice has avoided having to store and multiply all the database entries, while preventing Eve from finding out the actual entries, or their product. Furthermore, because it is believed that factoring n, computing φ(n), and solving the RSA problem is computationally difficult, it is highly unlikely that Eve can decrypt the database entries or the result.
[link]  
Fact: Given a set of possible data values ℤ/nℤ (e.g., integers within a certain range), any compression algorithm for elements in ℤ/nℤ must be a bijection and a permutation (since it must be invertible in order for decompression to be possible). As a result, it must necessarily expand the representation size of some elements.
[link]  
Example: Suppose that we are working with elements in ℤ/11ℤ = {0,1,2,3,4,5,6,7,8,9,10}. Suppose we define an algorithm that compresses 10 ∈ ℤ/11ℤ into an element in ℤ/11ℤ with a smaller representation size. One example of such an element is %1, since:
10 ⋅ 10
≡
1 (mod 11)
Thus, one possible implementation of a compression algorithm is a function that takes any x ∈ ℤ/11ℤ and returns (10 ⋅ x) mod 11. Since 10 has an inverse in ℤ/11ℤ, this function is invertible, so decompression is possible (simply multiply by 10 again). However, this will necessarily expand the representation of at least one value: 1 ∈ ℤ/11ℤ:
10 ⋅ 1
≡
10 (mod 11)
Note that this cannot be avoided because multiplying all the elements in ℤ/11ℤ by 10 amounts to a permutation, so at least one compressed element must be 10.

[link]  5.4. Assignment #5: Algebraic Structures and Isomorphisms

In this assignment you will solve several problems involving algebraic structures, and you will define a collection of Python functions that exploit isomorphisms between algebraic structures. You must submit a single Python source file named a5.py (submitted to the location hw5/a5.py). Please follow the gsubmit directions.

You may import the following library functions in your module (you may not need all these functions for this assignment depending on how you approach the problems, but they may be used):

from math import floor
from fractions import gcd
        
Your file may not import any other modules or employ any external library functions associated with integers and sets unless explicitly permitted to do so in a particular problem. Solutions to each of the programming problem parts below should be fairly concise. You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on the lecture notes and on each other; carefully consider whether you can use functions from the lecture notes, or functions you define in one part within subsequent parts.
  1. Solve the following equations using step-by-step equational reasoning, and list each step. Your solutions for this problem should appear as comments, delimited using '''...''', in a5.py.
    1. Compute the following composition of permutations (the result should be a permutation):
      [1,2,3,0] o [3,0,1,2] = ?
    2. Compute the following composition of permutations (the result should be a permutation):
      [46,47,...,99,0,1,2,3,4,...,45] o [11,12,...,99,0,1,2,3,4,...,10] = ?
    3. Let p, q ∈ Cn be two distinct cyclic permutation on n elements. Compute the following:
      p o q o p-1 o q-1 = ?
    4. Let p ∈ Sn be a swap permutation on n elements. Compute the following:
      p o p o p o p = ?
    5. Define the isomorphism between the two algebraic structures (S2, o) and ((ℤ/3ℤ)*, ⋅). You must write down a bijection that specifies how each element in S2 corresponds to an element of (ℤ/3ℤ)*, and you must write down four pairs of corresponding equations that show that the behavior of o on elements of S2 is the same as the behavior of ⋅ on corresponding elements of (ℤ/3ℤ)*.
    6. Define the isomorphism between the two algebraic structures (S2, o) and ((ℤ/4ℤ)*, ⋅). You must write down a bijection that specifies how each element in S2 corresponds to an element of (ℤ/4ℤ)*, and you must write down four pairs of corresponding equation that show that the behavior of o on elements of S2 is the same as the behavior of ⋅ on corresponding elements of (ℤ/4ℤ)*.
    7. Using a single equation involving integers, explain why there can be no isomorphism between the two algebraic structures (S4, o) and (ℤ/5ℤ, +).
  2. In this problem, you will implement functions that perform arithmetic operations while relying on an untrusted helper function. Any code that does not conform exactly to the specified requirements will receive no credit.
    1. Suppose you are supplied with the following function for computing the sum of a list of integers l modulo some 2n:

      def publicSum(l, n):
          s = sum(l) % pow(2,n)
          print("publicSum(" + str(l) + ") = "+str(s)+" (mod 2**" + str(n)+")")
          return s
                    
      Implement a Python function privateSum(l, n) that can compute the sum of a list of numbers modulo 2n without revealing the actual sum to the public (i.e., the output printed by publicSum should reveal no obvious information about the actual sum). Your implementation may not use any Python addition function other than publicSum. Your function is allowed to use the multiplication operator * and the modulus operator %.

      The following sample outputs are just examples. Your outputs may differ; this is acceptable as long as they conform to the above specification.

      >>> privateSum([5,17,2,4,9,2],3)
      publicSum([1, 5, 2, 4, 5, 2]) = 3 (mod 2**3)
      7
      >>> privateSum([8**20,3**13,7**17,11**9,19**8,34**11],20)
      publicSum([0, 28003, 917975, 513851, 608081, 460800]) = 431558 (mod 2**20)
      283302
      >>> privateSum([9**100, 6**99],50)
      publicSum([1023002024670457, 0]) = 1023002024670457 (mod 2**50)
      843457135947937
                    
    2. Suppose you are supplied with the following function for computing the product of a list of integers l modulo some 2n:

      def publicProduct(l, n):
          p = 1
          for x in l:
              p *= x % pow(2,n)
          print("publicProduct("+str(l)+") = "+str(p%pow(2,n))+" (mod 2**" + str(n)+")")
          return p % pow(2,n)
                    
      Implement a Python function privateProduct(l, n) that can compute the product of a list of numbers modulo 2n without revealing the actual product to the public (i.e., the output printed by publicProduct should reveal no information about the actual product to anyone, unless they can solve an intractable problem in modular arithmetic). Your implementation may not use any Python addition functions, and it may not use any multiplication functions other than publicProduct. Your function is allowed to use the exponentiation operator **, the modulus operator %, and the function pow(). You may also want to use some algorithms from previous assignments, such as inv() and egcd() from Assignment #3.

      The following sample outputs are just examples. Your outputs may differ; this is acceptable as long as they conform to the above specification.

      >>> privateProduct([5,17,3,5,9,1],3)
      publicProduct([5, 1, 3, 5, 1, 1]) = 3 (mod 2**3)
      3
      >>> privateProduct([7**21,3**13,5**17,11**9,19**7,23**11],20)
      publicProduct([644679, 800515, 1038837, 720059, 633931, 752103]) = 389511 (mod 2**20)
      563815
      >>> privateProduct([9**100, 7**99],50)
      publicProduct([725109995756321, 995892725925687]) = 1109453331708695 (mod 2**50)
      1123987677261495
                    
  3. Implement the following Python functions for working with permutations. Any code that does not conform exactly to the specified requirements will receive no credit.
    1. Implement a function permute(p, l) that takes two arguments: a permutation p (represented as a Python list of integers) and a list l of the same length as the permutation. It should return the list after it has been permuted according to the permutation.

      >>> permute([2,1,0], ['a','b','c'])
      ['c','b','a']
                    
    2. Implement a function C(k, m) that takes two integers k and m where k < m and returns the cyclic permutation in Cm that shifts all elements up by k.

      >>> C(1, 4)
      [1, 2, 3, 0]
                    
    3. Implement a function M(a, m) that takes two coprime integers a and m where 0 < a < m and returns the multiplication-induced permutation in Mm that corresponds to multiplication by a modulo m:

      >>> M(2, 5)
      [0, 2, 4, 1, 3]
                    
    4. Implement a function sort(l) that takes a list of integers of some length n and returns:
      • a cyclic permutation p ∈ Cn that will sort the list into ascending order, if it exists;
      • a multiplication-induced permutation p ∈ Mn that will sort the list into ascending order, if it exists;
      • None otherwise.

      >>> sort([38,16,27])
      [1,2,0]
      >>> permute(sort([38,49,16,27]), [38,49,16,27])
      [16,27,38,49]
      >>> sort([1, 13, 4, 17, 6, 23, 9])
      [0, 2, 4, 6, 1, 3, 5]
      >>> sort([0, 17, 4, 21, 8, 25, 12, 29, 16, 3, 20, 7, 24, 11, 28,\
                15, 2, 19, 6, 23, 10, 27, 14, 1, 18, 5, 22, 9, 26, 13])
      [0, 23, 16, 9, 2, 25,18, 11, 4, 27, 20, 13, 6, 29, 22,
       15, 8, 1, 24, 17, 10, 3, 26, 19, 12, 5, 28, 21, 14, 7]
                    
    5. Suppose you are supplied with the following function for applying a sequence of permutation ps to an input list l. For this problem, assume that ps only contains cyclic permutations from the set of permutations C2n for some n ∈ ℕ (that is, the set of cyclic permutations on sets with 2n elements).

      def publicPermute(l, ps):
          lNew = l[0:] # Make a copy.
          for p in ps:
              lNew = permute(p, lNew)
          print("publicPermute("+str(l)+", ...) = "+str(lNew))
          return lNew
                    
      Implement a Python function privatePermute(l, ps) that applies the sequence of permutations to l without revealing either the original input list l or the final result. Your implementation must use publicPermute() to perform the list of permutations. When running, your implementation of privatePermute() may make at most two additional calls to permute() (these two calls must not be inside a loop body, they should only be executed once per call to privatePermute(), and privatePermute() must not be recursive).

      The following sample outputs are just examples. Your outputs may differ; this is acceptable as long as they conform to the above specification.

      >>> privatePermute(['a','b','c','d','e'], [C(3,5), C(1,5), C(4,5), C(2,5), C(3,5)])
      publicPermute([1, 2, 3, 4, 0], ...) = [4, 0, 1, 2, 3]
      ['d', 'e', 'a', 'b', 'c']
      >>> privatePermute([25,34,2,1,56,7,86,2,45,1], [C(5,10), C(8,10), C(3,10), C(2,10), C(1,10)])
      publicPermute([3, 4, 5, 6, 7, 8, 9, 0, 1, 2], ...) = [2, 3, 4, 5, 6, 7, 8, 9, 0, 1]
      [1, 25, 34, 2, 1, 56, 7, 86, 2, 45]
                    

[link]  5.5. Generators of Algebraic Structures

Because an algebraic structure (A,⊕) often consists of a set of objects that can be "built up" using the binary operator ⊕ from a smaller, possibly finite, collection of generators G ⊂ A, it is often easier to reason about an algebraic structure by first reasoning about its generators, and then applying structural induction.
[link]  
Fact: Let W be the set of swap permutations on n elements. Then W is a set of generators for the set of permutations Sn, which can be defined as:
S
=
closure(W, o)
[link]  
Fact: Let A be the set of adjacent swap permutations on n elements. Then A is a set of generators for the set of permutations Sn, which can be defined as:
S
=
closure(A, o)
[link]  
Fact: The set ℤ/nℤ has a single generator 1 ∈ ℤ/nℤ with respect to addition + modulo n:
ℤ/nℤ
=
closure({1}, +)
[link]  
Fact: If a and n are coprime, then a is a generator for ℤ/nℤ with respect to addition + modulo n:
ℤ/nℤ
=
closure({a}, +)
[link]  
Fact: Suppose we have two algebraic structures A and B where for some operator ⊕:
A
=
closure({a}, ⊕)
B
=
closure({b}, ⊕)
If the generator a can be expressed in terms of b, i.e., a = b ⊕ ... ⊕ b, then it must be that:
A
⊂
B
Furthermore, if in addition to the above, the generator b can be expressed in terms of a, i.e., b = a ⊕ ... ⊕ a, then it must be that:
B
⊂
A
This would then imply (by basic set theory):
A
=
B

[link]  5.6. Isomorphisms and Linear Equations of Congruence Classes

[link]  
Fact: Let n be a positive integer. Then if + represents addition modulo n, we have:
ℤ/nℤ
≅
closure({1}, +)
In other words, 1 is a generator for ℤ/nℤ with respect to +.
[link]  
Fact: Let a and n be coprime positive integers. Then if + represents addition modulo n, we have:
ℤ/nℤ
≅
closure({a}, +)
In other words, a can be a single generator for ℤ/nℤ with respect to +. This is equivalent to a fact we have already seen.
[link]  
Fact: Let a and n be any two positive integers. Then if + represents addition modulo n, we have:
ℤ/(n/gcd(n,a))ℤ
≅
closure({a}, +)
≅
closure({gcd(n,a)}, +)
[link]  
Example: Consider n = 6 and a = 4. Then we have g = gcd(4,6) = 2. We have:
closure({4}, +)
=
{4 ⋅ 0, 4 ⋅ 1, 4 ⋅ 2}
=
{0, 4, 2}
=
closure({2}, +)
Note that:
4
=
2 + 2 (mod 6)
2
=
4 + 4 (mod 6)
Thus, 2 can be expressed using the generator 4, and 4 can be expressed using the generator 2.
[link]  
Fact (linear congruence theorem): Suppose that for a positive integer n and two congruence classes a ∈ ℤ/nℤ and b ∈ ℤ/nℤ where g ≡ gcd(a,n), we are given the following equation:
a ⋅ x
≡
b (mod n)
Since a and n are not coprime, we cannot solve the above equation. Furthermore, if b ∉ closure({a}, +), we know the equation cannot be solved. Since closure({a}, +) = closure({g}, +), the equation can only be solved if b ∈ closure({g}, +). In other words, the equation can only be solved if g|b.

Note that if g ≡ gcd(n,m) and b ∈ closure({g}, +), we have:
n
=
n' ⋅ g
a
=
a' ⋅ g
b
=
b' ⋅ g
(a' ⋅ g) ⋅ x
≡
(b' ⋅ g) (mod (n' ⋅ g))
We can then rewrite the above as:
(a' ⋅ g) ⋅ x
=
(b' ⋅ g) + k ⋅ (n' ⋅ g)
We can divide both sides of the above equation by g:
a' ⋅ x
=
b' + k ⋅ n'
We can convert the above equation back into an equation of congruence classes:
a' ⋅ x
≡
b' mod n'
At this point a' and n' are coprime, we can compute a'-1 (mod n') and multiply both sides by it to find our solution x:
a'-1 ⋅ a' ⋅ x
≡
a'-1 ⋅ b' mod n'
x
≡
a'-1 ⋅ b' mod n'
[link]  
Example: Solve the following equation for x ∈ ℤ/8ℤ, or explain why no solution exists:
2 ⋅ x
=
3 (mod 8)
Since 3 ∉ closure({2}, +), there is no solution x.
[link]  
Example: Solve the following equation for x ∈ ℤ/24ℤ, or explain why no solution exists:
16 ⋅ x
=
7 (mod 24)
If we attempt to apply the linear congruence theorem, we will find that gcd(16,24) = 8, and 7 ∉ closure({8},+), which means there is no solution.
[link]  
Example: Solve the following equation for x ∈ ℤ/15ℤ, or explain why no solution exists:
9 ⋅ x
=
6 (mod 15)
We know that gcd(9,15) = 3, so we can apply the linear congruence theorem:
3 ⋅ x
=
2 (mod 5)
We can now multiply both sides by 3-1 ≡ 2 (mod 5) to obtain the solution:
3-1 ⋅ 3 ⋅ x
=
3-1 ⋅ 2 (mod 5)
x
=
4 (mod 5)

[link]  5.7. Isomorphisms and the Chinese Remainder Theorem

[link]  
Fact: Let n and m be coprime positive integers. Let ℤ/nℤ × ℤ/mℤ be the set product of ℤ/nℤ and ℤ/mℤ, and let ⊕ be an operation on ℤ/nℤ × ℤ/mℤ defined as follows:
(a,b) ⊕ (c,d)
=
(a + c,b + d)
Then it is true that (ℤ/nℤ × ℤ/mℤ, ⊕) ≅ (ℤ/(m ⋅ n)ℤ, +).
[link]  
Fact: Let n and m be positive integers. and let g = gcd(n,m). Let ℤ/(n/g)ℤ × ℤ/(m/g)ℤ × ℤ/gℤ be a set product, and let ⊕ be an operation on ℤ/(n/g)ℤ × ℤ/(m/g)ℤ × ℤ/gℤ defined as follows:
(a,b,c) ⊕ (x,y,z)
=
(a + x,b + y, c + z)
Then it is true that (ℤ/(n/g)ℤ × ℤ/(m/g)ℤ × ℤ/gℤ, ⊕) ≅ (ℤ/((m ⋅ n)/g)ℤ, +).
[link]  
Example: Consider the set ℤ/2ℤ × ℤ/3ℤ with the operation ⊕, and the set ℤ/6ℤ together with the operation +. It is true that (ℤ/2ℤ × ℤ/3ℤ, ⊕) ≅ (ℤ/6ℤ, +). The bijection is specified below.
ℤ/2ℤ × ℤ/3ℤ ℤ/6ℤ
(0,0)0
(0,1)4
(0,2)2
(1,0)3
(1,1)1
(1,2)5
The isomorphism is demonstrated below.
ℤ/2ℤ × ℤ/3ℤℤ/6ℤ
(0,0) ⊕ (0,0) = (0,0)0 + 0 = 0
(0,0) ⊕ (0,1) = (0,1)0 + 4 = 4
(0,0) ⊕ (0,2) = (0,2)0 + 2 = 2
(0,0) ⊕ (1,0) = (1,0)0 + 3 = 3
(0,0) ⊕ (1,1) = (1,1)0 + 1 = 1
(0,0) ⊕ (1,2) = (1,2)0 + 5 = 5
(0,1) ⊕ (0,0) = (0,1)4 + 0 = 4
(0,1) ⊕ (0,1) = (0,2)4 + 4 = 2
(0,1) ⊕ (0,2) = (0,0)4 + 2 = 0
(0,1) ⊕ (1,0) = (1,1)4 + 3 = 1
(0,1) ⊕ (1,1) = (1,2)4 + 1 = 5
(0,1) ⊕ (1,2) = (1,0)4 + 5 = 3
ℤ/2ℤ × ℤ/3ℤℤ/6ℤ
(0,2) ⊕ (0,0) = (0,2)2 + 0 = 2
(0,2) ⊕ (0,1) = (0,0)2 + 4 = 0
(0,2) ⊕ (0,2) = (0,1)2 + 2 = 4
(0,2) ⊕ (1,0) = (1,2)2 + 3 = 5
(0,2) ⊕ (1,1) = (1,0)2 + 1 = 3
(0,2) ⊕ (1,2) = (1,1)2 + 5 = 1
(1,0) ⊕ (0,0) = (1,0)3 + 0 = 3
(1,0) ⊕ (0,1) = (1,1)3 + 4 = 1
(1,0) ⊕ (0,2) = (1,2)3 + 2 = 5
(1,0) ⊕ (1,0) = (0,0)3 + 3 = 0
(1,0) ⊕ (1,1) = (0,1)3 + 1 = 4
(1,0) ⊕ (1,2) = (0,2)3 + 5 = 2
ℤ/2ℤ × ℤ/3ℤℤ/6ℤ
(1,1) ⊕ (0,0) = (1,1)1 + 0 = 0
(1,1) ⊕ (0,1) = (1,2)1 + 4 = 5
(1,1) ⊕ (0,2) = (1,0)1 + 2 = 3
(1,1) ⊕ (1,0) = (0,1)1 + 3 = 4
(1,1) ⊕ (1,1) = (0,2)1 + 1 = 2
(1,1) ⊕ (1,2) = (0,0)1 + 5 = 0
(1,2) ⊕ (0,0) = (1,2)5 + 0 = 5
(1,2) ⊕ (0,1) = (1,0)5 + 4 = 3
(1,2) ⊕ (0,2) = (1,1)5 + 2 = 1
(1,2) ⊕ (1,0) = (0,2)5 + 3 = 2
(1,2) ⊕ (1,1) = (0,0)5 + 1 = 0
(1,2) ⊕ (1,2) = (0,1)5 + 5 = 4
Since 1 and 5 are generators for ℤ/6ℤ with respect to +, the corresponding elements (1,1) and (1,2) are generators for ℤ/2ℤ × ℤ/3ℤ.
[link]  
Fact: Suppose that for two positive integers n and m where g ≡ gcd(n,m) and two congruence classes a ∈ ℤ/nℤ and b ∈ ℤ/mℤ, we are given the following system of equations:
x
≡
a (mod n)
x
≡
b (mod m)
We then know that:
n
=
n' ⋅ g
m
=
m' ⋅ g
But this means that:
x
≡
a (mod (n' ⋅ g))
x
≡
b (mod (m' ⋅ g))
The above equations can be converted into facts about divisility:
x
=
a + k ⋅ (n' ⋅ g)
x
=
b + l ⋅ (m' ⋅ g)
But note that:
x
=
a + (k ⋅ n')) ⋅ g
x
=
b + (l ⋅ (m')) ⋅ g
The above implies:
x
=
a (mod g)
x
=
b (mod g)
Since x ≡ x, it must be that:
a
=
b (mod g)
Thus, a solution x exists for the system of equations only if a ≡ b (mod (gcd(n,m)).
[link]  
Fact: Suppose that for two positive integers n and m where g ≡ gcd(n,m) and two congruence classes a ∈ ℤ/nℤ and b ∈ ℤ/mℤ, we are given the following system of equations:
x
≡
a (mod n)
x
≡
b (mod m)
Note that because g ≡ gcd(n,m), we have:
n
=
n' ⋅ g
m
=
m' ⋅ g
To find a solution, first determine whether a ≡ b (mod g), and compute r = a (mod g). Then set:
x = y + r
We can now solve the following system for y:
y + r
≡
a (mod n)
y + r
≡
b (mod m)
We substruct r from both sides in both equations. We now have g | a-r and g | b-r, since r was the remainder when dividing a and b by g:
y
≡
(a − r) (mod n)
y
≡
(b − r) (mod m)
Now set:
y = g ⋅ z
We can now solve the following system for y:
g ⋅ z
≡
(a − r) (mod (n' ⋅ g))
g ⋅ z
≡
(b − r) (mod (m' ⋅ g))
Using the linear congruence theorem on both equations, we get:
z
≡
(a − r)/g (mod n')
z
≡
(b − r)/g (mod m')
We know that n' and m' are coprime, so we can solve for z using the usual method for solving systems of equations with coprime moduli. Once we find z, we can compute a solution x to the original system of equations:
x
≡
g ⋅ z + r (mod ((n ⋅ m) / g))
greatest
common
divisor
algorithm		 Fermat's
little
theorem		 Euler's
theorem
⇑ ⇑ ⇑
Bézout's
identity		 ⇐ extended
Euclidean
algorithm		 ⇐ algorithm for
finding
multiplicative
inverses		 ⇒ Euler's
totient
function φ
⇑
Chinese
remainder
theorem		 ⇐ CRT solver
for two
equations
⇑
linear
congruence
theorem		 ⇐ general
CRT solver
for two
equations
⇑
induction ⇐ general
CRT solver
for n
equations





formula for
3+4ℤ
primes		 ⇐ square roots
modulo p
⇑
Hensel's lemma ⇐ square roots
modulo p^k
⇑
CRT solver
for two
equations		 ⇐ square roots
modulo n ⋅ m

[link]  5.8. Implementations of Algebraic Structures and Operations

[link]  
Example: Recall that a magma is an algebraic structure with a set that is closed under a binary operation, and a free magma is such an algebraic structure with no additional algebraic properties. An example of a Python data structure that corresponds to such a structure is the set of nested lists. An implementation of the binary operation for such a data structure might be:

def op(x, y):
  return [x, y];
        
Notice that the above operation is not associative, has no identity or inverses, and is not commutative.

>>> op(1,2) == op(2,1)
False
>>> op(1,op(2,3)) == op(op(1,2),3)
False
        
[link]  
Example: A free commutative magma is an algebraic structure with no algebraic properties except commutativity. An example of a Python data structure that corresponds to this algebraic structure is the set of nested sets. An implementation of the binary operation for such a data structure might be:

def op(x, y):
  return {x, y};
        
Notice that the above operation is not associative, has no identity or inverses, but is commutative.

>>> op(1,2) == op(2,1)
True
>>> op(3,op(1,2)) == op(op(2,1),3)
True
>>> op(1,op(2,3)) == op(op(1,2),3)
False
        
[link]  
Example: A free monoid is an algebraic structure with no algebraic properties except associativity and the existence of an identity. An example of a Python data structure that corresponds to this algebraic structure is the set of lists (not nested lists). An implementation of the binary operation for such a data structure might be:

def op(x, y):
  return x + y # List concatenation done using +.
        
Notice that the above operation is associative and has the identity [].

>>> op([1],op([2],[3])) == op(op([1],[2]),[3])
True
>>> op([1],op([2],[3])) == op(op([1],[2]),[3])
True
>>> op([], [1,2,3]) == [1,2,3]
True
        

[link]  5.9. Assignment #6: Generalized CRT and Algebraic Properties of Data Structures

In this assignment you will solve several problems using the generalized Chinese remainder theorem and other techniques and facts you have learned in this course. You must submit a single file named a6.* (submitted to the location hw6/a6.*). The file extension may be anything you choose; please ask before submitting a file in an exotic or obscure file format (plain text is preferred). Please follow the gsubmit directions.
  1. Solve the following equations using step-by-step equational reasoning, and list each step.
    1. Solve the following equation for x ∈ ℤ/36ℤ if it exists; if no solution exists, explain why not:
      8 ⋅ x
      		≡
      12 (mod 36)
    2. Solve the following equation for x ∈ ℤ/22ℤ if it exists; if no solution exists, explain why not:
      2 ⋅ x
      		≡
      17 (mod 22)
    3. Solve the following system of equations and find a unique congruence class solution if it exists; if no solution exists, explain why not:
      x
      		≡
      5 (mod 15)
      x
      		≡
      15 (mod 25)
    4. Solve the following system of equations and find a unique congruence class solution if it exists; if no solution exists, explain why not:
      x
      		≡
      9 (mod 14)
      x
      		≡
      16 (mod 21)
    5. Solve the following system of equations and find a unique congruence class solution if it exists; if no solution exists, explain why not:
      x
      		≡
      5 (mod 12)
      x
      		≡
      6 (mod 16)
    6. Solve the following system of equations and find all congruence class solutions if any exist; if no solution exists, explain why not:
      x2
      		≡
      9 (mod 35)
      2 ⋅ x
      		≡
      6 (mod 14)
  2. Alice saved a 70-bit integer x in a 64-bit memory location (effectively storing x mod 264), and then she also saved x in a separate 32-bit memory location (effectively storing x mod 232). If Bob has has access to both memory locations (and nothing else), can he recover the original integer? Explain why or why not.
  3. Bob needs to store a number of items inside containers. He has two options: buy some number of containers that can hold 12 items each, or buy some number of containers that can hold 9 items each:
    • with containers that can hold 9 items, Bob will end up with all full containers except one, which will have only 2 items;
    • with containers that can hold 12 items, Bob will end up with all full containers except one, which will have only 8 items.
    1. Assuming that Bob has at most 35 items, how many items does Bob have?
    2. If Bob instead buys containers that can hold 4 items each, will all of the containers be full?
  4. Alice walks at 3 meters per second around a 42-meter track, while Bob walks at 2 meters per second around a 24-meter track. They begin walking clockwise at the same time, and after spending t seconds walking in circles, Alice is 9 meters to the right of her starting point along her track, while Bob is 18 meters to the right of his starting point along his track. If no more than 84 seconds have elapsed, how much time t has elapsed in seconds since Alice and Bob began walking?
  5. Your customer is a genealogist that studies family trees. The genealogist wants to use your database service to store the trees of ancestors of individual persons. For example, if Eve's parents are Alice and Bob, and Alice and Bob are simple trees with no ancestors, then Eve is represented by the larger tree Alice ⊕ Bob (or, equivalently, Bob ⊕ Alice). If Dan's parents are Eve and Carl, then Dan can be represented using the tree (Alice ⊕ Bob) ⊕ Carl. Every node and leaf in a tree represents a person. The two branches of each node in the tree represent the two biological parents of the person corresponding to that node.
    1. The set of all possible ancestor trees is an algebraic structure. Which of the following properties does ⊕ possess: associativity, commutativity, identity?
    2. Which of the following Python data structures would be appropriate for representing ancestor trees: nested lists, nested sets, or lists?
    3. The customer submitted a very large tree, and your staff decided to do an "optimization" by splitting the root node of the tree into the two subtrees on its branches and storing the two subtrees on separate servers, but under the same unique identifier 9423885. Do you need to inform the customer that information has been lost? Justify your answer using your answer to part (a) above.
  6. (Extra credit; submit the file hw6/a6.py using gsubmit any time before the date of the final): Suppose you are given an efficient function blackbox() that takes three positive integers k1, k2, and n where k1 < k2. For each possible exponent k ∈ {k1, ..., k2}, the function computes the average of the set of values:
    {ak mod n | a ∈ {1,...,n-1}}
    It then returns the minimum of the averages over all k ∈ {k1, ..., k2}. An inefficient but equivalent implementation is provided below for testing purposes:

    def avg(a):
        return float(sum(a))/len(a)

    def blackbox(k1, k2, n):
        return min([(avg([pow(a,k,n) for a in range(1,n)])) for k in range(k1, k2)])
              
    Implement a function factor(n) that can take any composite n that is the product of two distinct primes, and returns a pair (p,q) where p and q are the factors of n. Your implementation of factor() may make a number of calls to blackbox() that is polynomial in log(n), but not more than that.

[link]  Review #2. Algebraic Structures and their Properties

This section contains a comprehensive collection of review problems going over all the course material. Many of these problems are an accurate representation of the kinds of problems you may see on an exam.
[link]  
Exercise: Find all x ∈ ℤ/29ℤ that satisfy the following:
y2
≡
16 (mod 29)
x2
≡
y (mod 29)
We first solve for all possible y. Since 29 > 16, we have that ± 4 are the square roots of 16 in ℤ/29ℤ. Thus, we have two solutions for y:
y
∈
{4, 29 − 4}
y
∈
{4, 25}
We want to find all x that satisfy the system, so we need to solve for x for each possible y. Thus, we have:
y
≡
4 (mod 29)
x2
≡
4 (mod 29)
x
≡
± 2 (mod 29)
x
∈
{2, 29 − 2}
x
∈
{2, 27}
We also have:
y
≡
25 (mod 29)
x2
≡
25 (mod 29)
x
≡
± 5 (mod 29)
x
∈
{5, 29 − 5}
x
∈
{5, 24}
Thus, the possible solutions for x are:
x
∈
{2, 5, 24, 27}
Notice also that the problem could have been stated as:
x4
≡
16 (mod 29)
[link]  
Exercise: Determine which properties each of the following algebraic structures satisfy.
  1. The generating set G = {∅, {1}, {2}, {3}} with the union operation ∪ as the binary operator.
    We know that closure(G, ∪) is the set of subsets of {1,2,3}:
    closure(G, ∪)
    		=
    {∅, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}}
    Thus, we know from set theory that the union operation on sets is associative and commutative. There is an identity element ∅. There are no inverses.
  2. For positive integers a,n ∈ ℕ where gcd(a,n) = 1, generating set G = {a} with integer addition modulo n.
    The closure is the entire set {0,..., n − 1} because:
    {a, a + a, a + a + a, ..., a + ... + a}
    		=
    {(i ⋅ a) mod n | i ∈ {1 ,..., n}}
    Integer addition modulo n is associative and commutative, has identity 0, and for every x ∈ ℤ/nℤ, the inverse is n-x ∈ ℤ/nℤ.
[link]  
Exercise: Solve the following problems.
  1. Consider the following two circular shift permutations:
    [8,9,0,1,2,3,4,5,6,7]
    [5,6,7,8,9,0,1,2,3,4]
    How many of each would you need to compose to obtain the permutation [9,0,1,2,3,4,5,6,7,8]?
    These permutations specified are in C10, and we know that C10 ≅ ℤ/10ℤ. Notice that [8,9,0,1,2,3,4,5,6,7] ∈ C10 can correspond to 8 ∈ ℤ/10ℤ, that [5,6,7,8,9,0,1,2,3,4] ∈ C10 can correspond to 5 ∈ ℤ/10ℤ, and that [9,0,1,2,3,4,5,6,7,8] ∈ C10 can correspond to 9 ∈ ℤ/10ℤ. By Bézout's identity we have that:
    8 ⋅ 2 + 5 ⋅ (-3)
    		=
    1
    8 ⋅ 2 + 5 ⋅ 7
    		≡
    1 (mod 10)
    8 ⋅ (9 ⋅ 2) + 5 ⋅ (9 ⋅ 7)
    		≡
    9 ⋅ 1 (mod 10)
    8 ⋅ 8 + 5 ⋅ 3
    		≡
    9 (mod 10)
    Thus, we would need to compose 8 instances of the first permutation and 3 instances of the second permutation to obtain [9,0,1,2,3,4,5,6,7,8].
  2. Rewrite the permutation [3,4,0,1,2] as a composition of adjacent swap permutations.
    We can simply run the bubble sort algorithm on the above permutation and record the permutation that represents each swap. This leads to the following sequence:
    p1
    		=
    [0,2,1,3,4]
    p2
    		=
    [0,1,3,2,4]
    p3
    		=
    [0,1,2,4,3]
    p4
    		=
    [1,0,2,3,4]
    p5
    		=
    [0,2,1,3,4]
    p6
    		=
    [0,1,3,2,4]
    Thus, by applying the above sequence of permutations to [0,1,2,3,4] in reverse order, we can obtain [3,4,0,1,2], so the factorization of [3,4,0,1,2] into adjacent swap permutations is:
    [3,4,0,1,2]
    		=
    p1 o p2 o p3 o p4 o p5 o p6 o [0,1,2,3,4]
[link]  
Exercise: Suppose we want to perform k exponentiation operations (e.g., if k = 4, we want to compute (((ab)c)d)e) modulo 21. Assume the following:
  • a single exponentiation operation modulo 21 takes 213 = 9261 steps;
  • a single exponentiation operation modulo 3 takes 33 = 27 steps;
  • a single exponentiation operation modulo 7 takes 73 = 343 steps;
  • an exponentiation operation modulo 3 and an exponentiation operation modulo 7 together take 343 + 27 = 370 steps;
  • solving a two-equation system for two values, a modulo 3 and b modulo 7, takes 8000 steps using CRT;
  • we can either compute the exponentiation sequence directly modulo 21, or we can split it into two sequences of computations (one modulo 3, the other modulo 7) and then recombine using CRT at the end.
  1. What is the number of steps needed to perform k exponentiations modulo 21?
    f(k)
    		=
    9261 ⋅ k
  2. What is the number of steps needed to perform k exponentiations modulo 3 and k exponentiations modulo 7, then to recombine using CRT?
    f(k) = 370 ⋅ k + 8000
[link]  
Exercise: Find solutions to the following problems.
  1. Explain why the following polynomial has no integer solutions (Hint: you only need to evaluate the polynomial for two possible values of x):
    x4 + x2 + 3
    		=
    0
    If the above equation has an integer solution x, then it must have an integer solution modulo 2, since we can take the modulus of both sides:
    x4 + x2 + 3
    		=
    0
    (x4 + x2 + 3) mod 2
    		=
    0 mod 2
    x4 + x2 + 3
    		≡
    0 (mod 2)
    Thus, we have using logic that:
    (exists solution in ℤ)
    		→
    (exists solution modulo 2)
    (no solution modulo 2)
    		→
    (no solution in ℤ)
    Note that this only works in one direction. A solution modulo 2 does not necessarily imply that there is an integer solution.

    We see that for x = 0 and x = 1, the left-hand side is odd. The right-hand side is 0, so it is always even. Thus, no integer solution exists.
  2. Find at least one solution x ∈ ℤ/10ℤ to the following system of equations (you must use Bézout's identity):
    6 ⋅ y + 5 ⋅ x - 1
    		≡
    0 (mod 10)
    x2
    		≡
    y (mod 10)
    Since 5 and 6 are coprime, we can find a solution to the first equations. One such solution is:
    y
    		≡
    1 (mod 10)
    x
    		≡
    -1 (mod 10)
    		≡
    9 (mod 10)
    We also have that 92 ≡ 81 ≡ 1 (mod 10). Thus, since 12 ≡ 1 (mod 10), both equations are satisfied by this solution.
[link]  
Exercise: Find solutions to the following problems.
  1. Suppose you want to send some s ∈ ℤ/nℤ to Alice and Bob, but you want to ensure that the only way Alice and Bob can retrieve s is if they work together. What two distinct pairs (s1, p1) and (s2, p2) would you send to Alice and Bob, respectively, so that they would need to work together to recover s?
    You would need to send (s mod p, p) to Alice and (s mod q, q) to Bob where s < p ⋅ q and p and q are distinct and coprime.
  2. Suppose Bob is generating a public RSA key; he chooses a very large prime p, and then he chooses q = 2. Why is this not secure?
    Bob must share his public key (n, e). Since n = p ⋅ 2, n is even. This can immediately be seen by looking at the last bit of n (which will be 0, since n mod 2 = 0). It is then easy to recover the secret value p.
  3. Suppose Alice and Bob use Shamir secret sharing to share a password s to a lock that is not protected from brute force attacks (i.e., anyone can keep trying different passwords until they unlock it). Alice holds s mod p and Bob holds s mod q, where s < p ⋅ q. However, suppose that Bob happens to be using q = 2, and Alice knows this. What can Alice do to quickly break the lock?
    If Alice holds a and Bob holds b, the system of equations that would be set up to recover s is as follows:
    x
    		≡
    a (mod p)
    x
    		≡
    b (mod 2)
    Notice that there are only two possibilities for Bob's value b ∈ ℤ/2ℤ. Thus, Alice could set up two systems, one for b = 0 and another for b = 1, solve both, and try both secrets s on the lock.
[link]  
Exercise: Suppose that Alice, Bob, Carl, and Dan are sharing a secret s using Shamir secret sharing, where each participant is assigned a distinct modulus n that is coprime to everyone else's modulus. Each participant is holding a part of the secret s mod n, and the secret can be recovered by any two participants. However, Eve has sabotaged the value stored by one one the participants. Below are the values currently stored by everyone; one of them is corrupted.
  • Alice: nAlice = 3 and (s mod 3) = 2
  • Bob: nBob = 4 and (s mod 4) = 3
  • Carl: nCarl = 5 and (s mod 5) = 2
  • Dan: nDan = 7 and (s mod 7) = 4
  1. Which participant's stored value s mod n has Eve sabotaged?
    Any two participants can recover the secret s by setting up a system with two equations and solving the system using CRT. We list all of the possible combinations and solve for s to find which participant's value has been corrupted.
    • Alice and Bob:
      s
      		≡
      2 (mod 3)
      s
      		≡
      3 (mod 4)
      s
      		≡
      11 (mod 12)
    • Alice and Carl:
      s
      		≡
      2 (mod 3)
      s
      		≡
      2 (mod 5)
      s
      		≡
      2 (mod 15)
    • Alice and Dan:
      s
      		≡
      2 (mod 3)
      s
      		≡
      4 (mod 7)
      s
      		≡
      11 (mod 21)
    • Bob and Carl:
      s
      		≡
      3 (mod 4)
      s
      		≡
      2 (mod 5)
      s
      		≡
      7 (mod 20)
    • Bob and Dan:
      s
      		≡
      3 (mod 4)
      s
      		≡
      4 (mod 7)
      s
      		≡
      11 (mod 28)
    • Carl and Dan:
      s
      		≡
      2 (mod 5)
      s
      		≡
      4 (mod 7)
      s
      		≡
      32 (mod 35)
    Since three of the participants can consistently recover the same secret s = 11, and all pairs of participants in which Carl is present do not yield s = 11 and are inconsistent with one another, it must be Carl's data that has been sabotaged.
  2. What is the correct secret value s?
    Since three of the six possible pairings result in s = 11, and the other three are inconsistent and all involve Carl, it must be that s = 11 was the original uncorrupted secret.
  3. What's the number of different shared secret values these four participants can store (assuming they use the same moduli, and require that any two members should be able to recover the secret).
    Since any two participants must be able to recover s, it must be that s < n ⋅ m for every possible pair n and m. The smallest two values are 3 and 4, so 3 ⋅ 4 - 1 = 11, where 11 ∈ ℤ/(3 ⋅ 4)ℤ, is the largest possible s that can be receovered.
  4. Suppose you want to store an n-bit number s. You want to store it in a way that makes it possible to recover s even if one of the bits is corrupted. How can you accomplish this using at most approximately 2 ⋅ n bits?
    Choose four distinct coprime numbers m1, m2, m3, and m4 such that s is less than the product of every pair of these, but such that the product of any pair is not much larger than s (e.g., m1 and m2 can be stored in the same number of bits as s). Then store (s mod m1, s mod m2, s mod m3, s mod m4) using about 2 ⋅ n bits.

    If any individual bit is corrupted, this corrupts at most one of the four values stored. As with Alice, Bob, and Dan, the original value can still be recovered.
[link]  
Exercise: Bob decides to create his own online currency BobCoin. Bob knows that in order for BobCoin to be successful, it needs to be possible to make more BobCoins as more and more people start using them. However, he also does not want rapid inflation to occur. Thus, Bob issues BobCoins according to the following protocol:
  • every day, Bob chooses two new random primes p and q;
  • Bob computes n = p ⋅ q, and then discards p and q;
  • Bob posts n online for everyone to see;
  • at any time on that day, anyone can submit a factor f of n;
  • if f is a factor of n, Bob issues that person a BobCoin, invalidates n permanently so that no one else can use it, and generates a new n.
  1. Why is it okay for Bob to discard p and q?
    Because Bob can easily check whether a submitted f actually is a factor by computing gcd(f, n), or simply dividing n by f.
  2. Suppose that Bob always posts numbers n that have 100 digits, and it takes the fastest computer one year to factor a 100-digit number through trial and error. How many computers would Alice need, and for how long would she need to run them in parallel, to earn a BobCoin?
    Since it takes a 365 days to try all possible k factors of a 100-digit number, in one day one computer can try 1/365 ⋅ k factors. Thus, Alice would need 365 computers that she could run for one day, with each computer looking through a different region of factors.
  3. Suppose Bob wants to issue a complimentary BobCoin coupon to a group of 100 people. However, he wants to make sure that they can use their BobCoin coupon only if at least 20 out of those 100 people agree that the coupon should be redeemed for a BobCoin. How can Bob accomplish this?
    Bob can use Shamir secret sharing to accomplish this. Bob can take one of the factors f of n when he generates n, and choose 100 distinct primes such that the product of any 20 of the primes is greater than f while the product of any 19 of these primes is less than f. Bob can then distribute f mod m for each prime modulus m to each of the 100 people. If any 20 (or greater) of these 100 people agree to redeem the coupon, then can use CRT to reconstruct f and submit it to Bob for redemption.
[link]  
Exercise: Suppose you are given a black box that can take an integer n and two range boundaries k1 and k2. For each possible k in the range, the black box computes the average of the set:
{ak | a ∈ {1,...,n-1}}
It then returns the minimum of all of the above averages. How can this black box be used to compute a factor of n?
The following is a breakdown of what you should be able to do at this point in the course (and of what you may be tested on in an exam). Notice that many of the tasks below can be composed, and that many problems can be solved in more than one way.
  • find the greatest common divisor of two relatively small integers
  • check if a number is prime
    • using an exhaustive search
    • using the Fermat primality test
  • generate random permutations and integers
    • generate a permutation of a set {1,...,m-1}
    • generate a "random" number using permutations
    • generate a random number in a certain range
    • generate a random prime in a certain range
  • use randomly generated primes...
    • to encrypt information and transmit it safely (using RSA or Rabin encryption)
    • 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 x1 ⊕ ... ⊕ xn 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 pi in ℤ/piℤ, and then performing CRT once is less expensive than working in ℤ/nℤ the whole time
  • solving equations involving congruence classes and performing computations
    • compute multiplicative inverses ℤ/nℤ
      • using φ(n)
      • using a given output from the extended Euclidean algorithms or (equivalently) an instance of Bézout's identity
    • compute exponents modulo n efficiently
      • using Euler's theorem and φ (when possible)
      • using the efficient repeated-squaring method
    • solve a system of linear equations (i.e., with a coefficient on the left-hand side) where each equation is modulo some ni
      • derive a system of equations from a word problem
        • rotating/cycling objects
        • objects that generate/consume different amounts of power, time, space, etc.
        • Shamir secret sharing and applications
      • solve a system involving additive and multiplicative inverses
      • using the linear congruence theorem
      • using the generalized CRT process (even if moduli are not coprime)
    • compute square roots of congruence classes...
      • modulo a prime
      • modulo a (small) prime power
      • modulo a product of two coprime numbers
  • efficiency/complexity of modular arithmetic algorithms...
    • efficiency of modular addition, multiplication, and exponentiation
    • recognize when you cannot solve problems efficiently
      • computing φ(n) for an arbitrary n
      • factoring n for an arbitrary n
      • computing discrete logarithms
      • computing RSA secret keys from public keys, and decrypting RSA messages without any knowledge of secret keys
      • decrypting Rabin messages without any knowledge of secret keys
  • permutations and isomorphisms
    • sets of all permutations, cyclic permutations, multiplication-induced permutations, swap permutations, and adjacent swap permutations
      • composing two permutations
      • decomposing a permutation into adjacent swap permutations
    • isomorphisms between sets of congruence classes and permutation sets
      • cyclic permutations and (ℤ/nℤ, +)
      • multiplication-induced permutations and ((ℤ/nℤ)*, ⋅)
      • (ℤ/φ(n)ℤ, +) and ((ℤ/nℤ)*, ⋅)
      • homomorphic encryption (using multiplication-induced permutations or RSA encryption)
      • solving permutation equations via isomorphism to (ℤ/nℤ, +) or ((ℤ/nℤ)*, ⋅)
  • other algebraic structures and their properties
    • magmas, commutative magmas, monoids, groups, and commutative groups
      • examples of data structures or mathematical sets (e.g., ℤ/nℤ) of each
      • algebraic properties of each
    • data structures as algebraic structures
      • nested lists/trees, nested sets, lists, strings, integers

[link]  Appendix A. Python

The Python programming language will be among the languages we use in this course. This language supports the object-oriented, imperative, and functional programming paradigms, has automatic memory managememt, and natively supports common high-level data structures such as lists and sets. Python is often used as an interpreted language, but it can also be compiled.

[link]  A.1. Obtaining Python

The latest version of Python 3 can be downloaded at: http://www.python.org/getit/. In this course, we will require the use if Python 3, which has been installed on all the CS Department's undergraduate computing lab machines, as well as on csa2/csa3.

[link]  A.2. Common data structures (i.e., Python expressions)

Python provides native support for several data structures that we will use throughout this course: integers, strings, lists, tuples, sets, and dictionaries (also known as finite maps). In this subsection, we present how instances of these data structures are represented in Python, as well as the most common operations and functions that can be applied to these data structure instances.
  • Booleans consist of two constants: True and False.
    • The usual logical operations are available using the operators and, or, and not.

    >>> True                                      # A boolean constant.
    True
    >>> False                                     # A boolean constant.
    False
    >>> True and False or True and (not False)    # A boolean expression.
    True
              
  • Integers are written as in most other programming languages (i.e., as a sequence of digits).
    • The usual arithmetic operations are available using the operators +, *, -, and /. The infix operator // represents integer division, and the infix operators ** represents exponentiation. Negative integers are prefixed with the negation operator -.
    • The usual relational operators ==, !=, <, >, <=, >= are available.
    • The int() function can convert a string that looks like an integer into an integer.

    >>> 123                                       # An integer constant.
    True
    >>> 1 * (2 + 3) // 4 - 5                      # An integer expression.
    -4
    >>> 4 * 5 >= 19                               # A boolean expression involving integers.
    True
    >>> int("123")                                # A string being converted into an integer
    123
              
  • Strings are delimited by either ' or " characters. Strings can be treated as lists of single-character strings. Another way to look at this is that there is no distinction between a character and a string: all characters are just strings of length 1. Multiline strings can be delimited using """ or ''' (i.e., three quotation mark characters at the beginning and end of the string literal).
    • The empty string is denoted using '' or "".
    • Two strings can be concatenated using +.
    • The function len() returns the length of a string.
    • Individual characters in a string can be accessed using the bracketed index notation (e.g., s[i]). These characters are also strings themselves.

    >>> 'Example.'                                # A string.
    'Example.'
    >>> "Example."                                # Alternate notation for a string.
    'Example.'
    >>> len("ABCD")                               # String length.
    4
    >>> "ABCD" + "EFG"                            # String concatenation.
    'ABCDEFG'
    >>> "ABCD"[2]                                 # Third character in the string.
    'C'
              
  • Lists are similar to arrays: they are ordered sequences of objects and/or values. The entries of a list can be of a mixture of different types, and lists containing one or more objects are delimited using [ and ], with the individual list entries separated by commas. Lists cannot be members of sets.
    • The empty list is denoted using [].
    • Two lists can be concatenated using +.
    • The function len() returns the length of a list.
    • Individual entries in a list can be accessed using the bracketed index notation (e.g., a[i]).
    • To check if a value is in a list, use the in relational operator.

    >>> [1,2,"A","B"]                             # A list.
    [1, 2, 'A', 'B']
    >>> [1, 2] + ['A','B']                        # Concatenating lists.
    [1, 2, 'A', 'B']
    >>> len([1,2,"A","B"] )                       # List length.
    4
    >>> [1,2,"A","B"][0]                          # First entry in the list.
    1
    >>> 1 in [1, 2]                               # List containment check.
    True
              
  • Tuples are similar to lists (they are ordered, and can contain objects of different types), except they are delimited by parentheses ( and ), with entries separated by commas. The main distinction between lists and tuples is that tuples are hashable (i.e., they can be members of sets).
    • The empty tuple is denoted using ().
    • A tuple containing a single object x is denoted using (x, ).
    • Two tuples can be concatenated using +.
    • A tuple can be turned into a list using the list() function.
    • A list can be turned into a tuple using the tuple() function.
    • The function len() returns the length of a tuple.
    • Individual entries in a tuple can be accessed using the bracketed index notation (e.g., t[i]).
    • To check if a value is in a tuple, use the in relational operator.

    >>> (1,2,"A","B")                             # A tuple.
    (1, 2, 'A', 'B')
    >>> (1,)                                      # Another tuple.
    (1,)
    >>> (1, 2) + ('A','B')                        # Concatenating tuples.
    (1, 2, 'A', 'B')
    >>> list((1, 2, 'A','B'))                     # A tuple being converted into a list.
    [1, 2, 'A', 'B']
    >>> tuple([1, 2, 'A','B'])                    # A list being converted into a tuple.
    (1, 2, 'A', 'B')
    >>> len((1,2,"A","B"))                        # Tuple length.
    4
    >>> (1,2,"A","B")[0]                          # First entry in the tuple.
    1
    >>> 1 in (1, 2)                               # Tuple containment check.
    True
              
  • Sets are unordered sequences that cannot contain duplicates. They are a close approximation of mathematical sets. Sets cannot be members of sets.
    • The empty set is denoted using set().
    • The methods .union() and .intersect correspond to the standard set operations.
    • A list or tuple can be turned into a set using the set() function.
    • A set can be turned into a list or tuple using the list() or list() function, respectively.
    • The function len() returns the size of a set.
    • To access individual entries in a set, it is necessary to turn the set into a list or tuple.
    • To check if a value is in a set, use the in relational operator.

    >>> {1,2,"A","B"}                             # A set.
    {1, 2, 'A', 'B'}
    >>> ({1,2}.union({3,4})).intersection({4,5})  # Set operations.
    {4}
    >>> set([1, 2]).union(set(('A','B')))         # Converting a list and a tuple to sets.
    {'A', 1, 2, 'B'}
    >>> len({1,2,"A","B"})                        # Set size.
    4
    >>> 1 in {1,2,"A","B"}                        # Tuple containment check.
    True
              
  • Frozen sets are like sets, except they can be members of other sets. A set can be turned into a frozen set using the frozenset() function.

    >>> frozenset({1,2,3})                        # A frozen set.
    frozenset({1, 2, 3})
    >>> {frozenset({1,2}), frozenset({3,4})}      # Set of frozen sets.
    {frozenset({3, 4}), frozenset({1, 2})}
              
  • Dictionaries are unordered collections of associations between some set of keys and some set of values. Dictionaries are also known as finite maps.
    • The empty dictionary is denoted using {}.
    • The list of keys that the dictionary associates with values can be obtained using list(d.keys()).
    • The list of values that the dictionary contains can be obtained using list(d.values()).
    • The function len() returns the number of entries in the dictionary.
    • Individual entries in a dictionary can be accessed using the bracketed index notation (e.g., d[key]).

    >>> {"A":1, "B":2}                            # A dictionary.
    {'A': 1, 'B': 2}
    >>> list({"A":1, "B":2}.keys())               # Dictionary keys.
    ['A', 'B']
    >>> list({"A":1, "B":2}.values())             # Dictionary values.
    [1, 2]
    >>> len({"A":1, "B":2})                       # Dictionary size.
    2
    >>> {"A":1, "B":2}["A"]                       # Obtain a dictionary value using a key.
    1
              

[link]  A.3. Other Python expressions

Python provides concise notations for defining data structures and performing logical computations. In particular, it support a comprehension notation that can be used to build lists, tuples, sets, and dictionaries.
  • List comprehensions make it possible to construct a list by iterating over one or more other data structure instances (such as a list, tuple, set, or dictionary) and performing some operation on each element or combination of elements. The resulting list will contain the result of evaluating the body for every combination.

    >>> [ x for x in [1,2,3] ]
    [1, 2, 3]
    >>> [ 2 * x for x in {1,2,3} ]
    [2, 4, 6]
    >>> [ x + y for x in {1,2,3} for y in (1,2,3) ]
    [2, 3, 4, 3, 4, 5, 4, 5, 6]
              
    It is also possible to add conditions anywhere after the first for clause. This will filter which combinations are actually used to add a value to the resulting list.

    >>> [ x for x in {1,2,3} if x < 3 ]
    [1, 2]
    >>> [ x + y for x in {1,2,3} for y in (1,2,3) if x > 2 and y > 1 ]
    [5, 6]
              
  • Set comprehensions make it possible to construct a set by iterating over one or more other data structure instances (such as a list, tuple, set, or dictionary) and performing some operation on each element or combination of elements. The resulting list will contain the result of evaluating the body for every combination. Notice that the result will contain no duplicates because the result is a set.

    >>> { x for x in [1,2,3,1,2,3] }
    {1, 2, 3}
              
  • Dictionary comprehensions make it possible to construct a dictionary by iterating over one or more other data structure instances (such as a list, tuple, set, or dictionary) and performing some operation on each element or combination of elements. The resulting dictionary will contain the result of evaluating the body for every combination.

    >>> { key : 2 for key in ["A","B","C"] }
    {'A': 2, 'C': 2, 'B': 2}
              

[link]  A.4. Other useful built-in functions

The built-in function type() can be used to determine the type of a value. Below, we provide examples of how to check whether a given expression has one of the common Python types:

>>> type(True) == bool
True
>>> type(123) == int
True
>>> type("ABC") == str
True
>>> type([1,2,3]) == list
True
>>> type(("A",1,{1,2})) == tuple
True
>>> type({1,2,3}) == set
True
>>> type({"A":1, "B":2}) == dict
True
      

[link]  A.5. Common Python definition and control constructs (i.e., Python statements)

A Python program is a sequence of Python statements. Each statement is either a function definition, a variable assignment, a conditional statement (i.e., if, else, and/or elif), an iteration construct (i.e., a for or while loop), a return statement, or a break or continue statement.
  • Variable assignments make it possible to assign a value or object to a variable.

    x = 10
              
    It is also possible to assign a tuple (or any computation that produces a tuple) to another tuple:

    (x, y) = (1, 2)
              
  • Function and procedure definitions consist of the def keyword, followed by the name of the function or procedure, and then by one or more arguments (delimited by parentheses and separated by commas).

    def example(a, b, c):
        return a + b + c
              
  • Conditional statements consist of one or more branches, each with its own boolean expression as the condition (with the exception of else). The body of each branch is an indented sequence of statements.

    def fibonacci(n):
        # Computes the nth Fibonacci number.
        if n <= 0:
            return 0
        elif n <= 2:
            return 1
        else:
            return fibonacci(n-1) + fibonacci(n-2)
              
  • Iteration constructs make it possible to repeat a sequence of statements over and over. The body of an iteration construct is an indented sequence of statements.
    • The while construct has a boolean expression as its condition (much like if). The body is executed over and over until the expression in the condition evaluates to False, or a break statement is encountered.

      def example1(n):
          # Takes an integer n and returns the sum of
          # the integers from 1 to n-1.
          i = 0
          sum = 0
          while i < n:
              sum = sum + i
              i = i + 1
          return sum

      def example2(n):
          # Takes an integer n and returns the sum of
          # the integers from 1 to n-1.
          i = 0
          sum = 0
          while True:
              sum = sum + i
              i = i + 1
              if i == n:
                  break
          return sum
                    
    • The for construct makes it possible to repeat a sequence of statements once for every object in a list, tuple, or set, or once for every key in a dictionary.

      def example3(n):
          # Takes an integer n and returns the sum of
          # the integers from 1 to n-1.
          sum = 0
          for i in range(0,n):
              sum = sum + i
          return sum

      def example4(d):
          # Takes a dictionary d that maps keys to
          # integers and returns the sum of the integers.
          sum = 0
          for key in d:
              sum = sum + d[key]
          return sum