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 useful computational solutions to problems such as random number generation, prime number generation, error correction, trusted and distributed storage, secure communication, and others.
In covering the material for this course, we will use the standard language and conventions for discussing these mathematical structures that have been developed by the community of mathematicians over the course of history. You will need to become familiar with these conventions in order to find, identify, and use the structures and techniques that have already been developed for representing and solving certain computational problems. At the same time, we will also learn how modern programming languages and programming paradigms can be used to implement these structures and algorithms both accessibly and efficiently.
The development and application of mathematics involves abstraction. A problem can be viewed at multiple levels of abstraction, and in developing mathematics humans have adopted a variety of techniques that allow them to successfully employ abstraction to study natural phenomena and solve problems.
symbolic | abstract meaning | concrete meaning in application domain |
2 + 3 | 5 | five objects |
{(1, 2), (1, 3)} | acyclic graph | file system |
{(1, 2), (2, 3), (3, 1)} | graph with cycle | network |
{(0,1), (1,2), (2,0)} | permutation | random number sequence |
In this course, we will begin to reviewing the terminology and concepts of logic, integer arithmetic, and set theory, which we will use throughout the course. We will then show that the algebraic properties of the integers also apply to congruence classes of integers (i.e., the properties of modular arithmetic operations), and we will derive and utilize theorems that have useful computer science applications (such as for generating random numbers and creating cryptographic protocols). We will then go further and show that some of the algebraic properties that hold in integer and modular arithmetic can also apply to any data structure, and we will study how to recognize and take advantage of these properties.
formula | meaning | example of one possible Python representation |
true | always true | True |
false | always false | False
|
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 |
|
False <= True |
f1 iff f2 |
|
True == False |
¬ f | true if f is false | not (True or (False and True)) |
( f ) | true if f is true | (True and (not (False)) |
predicate example | depends on the definition of the predicate |
isPrime(7) |
meaning of 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 |
|
the sun is visible | it is daytime | meaning | interpretation |
true | true | true | a sunny day |
true | false | false | |
false | true | true | a cloudy day |
false | false | true | nighttime |
|
term | what it represents | example of one possible Python representation |
0 | 0 | 0 |
1 | 1 | 1 |
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)
|
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 |
predicate definition | example of one possible Python representation |
P(x) iff x > 0 and x < 2 | def P(x): return x > 0 and x < 2 |
Q(x) iff x > 3 | Q = lambda x: x > 3 |
formula | what it represents | example of one possible Python representation |
P(1) | true | P(1) |
P(1) or P(2) | true | P(1) or P(2)
|
Q(1) and P(1) | false | Q(1) and Q(1)
|
formula | what it represents |
x | y |
|
y is prime |
|
term | what it represents | example of one possible Python representation |
∅ | a set with no elements in it | set() |
{1,2,3} | {1,2,3} | {1,2,3} |
{2,..,5} | {2,3,4,5} | set(range(2,6)) |
{ x | x ∈ {1,2,3,4,5,6}, x > 3 } | {4,5,6} | {x for x in {1,2,3,4,5,6} if x > 3}
|
|{1,2,3,4}| | 4 | len({1,2,3,4})
|
term | what it represents | example of one possible Python representation |
S1 ∪ S2 | {z | z ∈ ℤ, z ∈ S1 or z ∈ S2} | {1,2,3}.union({4,5}) {1,2,3} | {4,5} |
S1 ∩ S2 | {z | z ∈ ℤ, z ∈ S1 and z ∈ S2} | {1,2,3}.intersection({2,3,5}) {1,2,3} & {2,3,5} |
|S| | the number of elements in S | len({1,2,3}) |
term | what it represents |
ℕ | {0, 1, 2, ...} |
ℤ | {..., -2, -1, 0, 1, 2, ...} |
subset()
operation on sets.
formula | what it represents | example of one possible Python representation |
1 ∈ {1,2,3} | true | 1 in {1,2,3} |
4 ∈ {1,2,3} | false | 4 in {1,2,3} |
∀ x ∈ {1,2,3}, x > 0 and x < 4 | true | forall({1,2,3}, lambda x: x > 0 and x < 4) |
∃ x ∈ {1,2,3}, x < 1 and x > 3 | false | exists({1,2,3}, lambda x: x < 1 or x > 3) |
∀ x ∈ ∅, f | true | |
∃ x ∈ ∅, f | false |
| iff |
| |||
| iff |
|
formula | what it represents | example of one possible Python representation |
3 ∈ {1,2,3} | true | 3 in {1,2,3} |
{1,2} ⊂ {1,2,3} | true | subset({1,2}, {1,2,3}) |
{4,5} ⊂ {1,2,3} | false | subset({4,5}, {1,2,3}) |
formula | what it represents |
z ∈ S | true if z is an element of S; false otherwise |
S1 ⊂ S2 | ∀ z ∈ S1, z ∈ S2 |
S1 = S2 | S1 ⊂ S2 and S2 ⊂ S1 |
term | what it represents | example of one possible Python representation |
{1,2} × {5,6,7} | {(1,5),(1,6),(1,7),(2,5),(2,6),(2,7)} | { (x,y) for x in {1,2} for y in {4,5,6,7} } |
predicate | definition | graphical example |
X × Y is the set product of X and Y | X × Y = { (x,y) | x ∈ X, y ∈ Y } | |
R is a relation between X and Y | R ⊂ X × Y | |
R is a function from X to Y R is a (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 |
X
and Y
.
R
is a relation over a set X
.
|
R
and a set X
and determines whether that relation is asymmetric? Recall that we can represent the implication logical operator using the Python operator <=
.
| = |
|
| = |
|
{'Alice', 'Bob', 'Carl', 'Dan', and 'Eve'}
:
hw1/hw1.py
. Please follow the gsubmit directions.
cube(n)
that takes a single positive integer argument n
and returns True
if and only if n
is a perfect cube (i.e., there exists an integer k
such that k
3 = n
). You cannot use loops, and you must use exists()
to receive credit. Efficiency is not important.
properPrimeFactors(n)
that takes a single positive integer argument n
and returns a finite set of integers containing all the prime proper factors of that number.
shared(S)
that takes any finite set of positive integers S
and returns a relation over S
in which any two numbers in S
that share at least one prime proper factor are related. If a number has no proper prime factors, then it shares no proper prime factors with any other number (including itself).
shared()
(assuming its input is a finite set of positive integers). Define three veriables in your code; each will represent a counterexample input (if it exists) that leads to an output that does not have the corresponding property:
shared()
, simply assign None
to the corresponding variable. If a property does not apply to all outputs of shared()
, assign an input set to the corresponding variable that returns an output relation that does not satisfy that property. For example, if we were doing the same thing for the property of asymmetry, we would choose a value for asymmetric
such that:
(1,2)
).isSymmetric()
that takes as its input two arguments: a set X
and a relation R
. The function should return True
if the relation R
is a symmetric relation on X
, and it should return False
otherwise.
isTransitive()
that takes as its input two arguments: a set X
and a relation R
. The function should return True
if the relation R
is a transitive relation on X
, and it should return False
otherwise.isEquivalence()
that takes as its input two arguments: a set X
and a relation R
. The function should return True
if the relation R
is an equivalence relation on X
, and it should return False
otherwise. Hint: read the notes in this section carefully and reuse functions that have already been defined.
R1
above so that R1
is an equivalence relation over X1
, and so that the following will evaluate to True
:
R2
above so that R2
is an equivalence relation over X2
, and so that the following will evaluate to True
:
R3
above so that R3
is an equivalence relation over X3
, and so that the following will evaluate to True
:
R3
. Solutions that use an explicitly defined set will receive no credit.
| = |
|
| = |
|
| = |
|
| ∈ |
| |||
| ∈ |
|
| = |
| |||
| = |
| |||
| = |
|
term | what it represents |
z z mod m z + mℤ |
{z + (a ⋅ m) | a ∈ ℤ} |
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 and c2 ⊂ c1, i.e., set equality applied to the congruence classes c1 and c2; false otherwise |
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
|
| ≡ |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
≡ |
| ||||
≡ |
|
property | definition |
ℤ/mℤ is closed under + | ∀ x,y ∈ ℤ/mℤ, x + y ∈ ℤ/mℤ |
+ is commutative on ℤ/mℤ | ∀ x,y ∈ ℤ/mℤ, x + y ≡ y + x |
+ is associative on ℤ/mℤ | ∀ x,y,z ∈ ℤ/mℤ, (x + y) + z ≡ x + (y + z) |
+ has a (left and right) identity 0 in ℤ/mℤ | ∀ x ∈ ℤ/mℤ, 0 + x ≡ x and x + 0 ≡ x |
ℤ/mℤ has inverses with respect to + | ∀ x ∈ ℤ/mℤ, (m - x) + x ≡ 0 |
ℤ/mℤ is closed under ⋅ | ∀ x,y ∈ ℤ/mℤ, x ⋅ y ∈ ℤ/mℤ |
⋅ is commutative on ℤ/mℤ | ∀ x,y ∈ ℤ/mℤ, x ⋅ y ≡ y ⋅ x |
+ is associative on ℤ/mℤ | ∀ x,y,z ∈ ℤ/mℤ, (x ⋅ y) ⋅ z ≡ x ⋅ (y ⋅ z) |
+ has a (left and right) identity 1 in ℤ/mℤ | ∀ x ∈ ℤ/mℤ, 1 ⋅ x ≡ x and x ⋅ 1 ≡ x |
⋅ distributes across + in ℤ/mℤ | ∀ x,y,z ∈ ℤ/mℤ, x ⋅ (y + z) ≡ (x ⋅ y) + (x ⋅ z) |
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| |||
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| | |
| |||
| = |
| |||
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| |||
| ∈ |
| |||
| | |
|
| | |
| |||
| ∈ |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
|
| ≡ |
| |||
| | |
| |||
| | |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ∤ |
| |||
| ≢ |
| |||
| ∤ |
| |||
| ≢ |
|
| ≡ |
| |||
| ≡ |
| |||
| = |
| |||
| = |
| |||
| | |
|
| | |
| |||
| = |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| = |
|
| = |
| |||
= |
|
| ≠ |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
| | |
|
| = |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
|
| = |
|
| = |
|
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
= |
| ||||
= |
| ||||
= |
|
|
| ≢ |
| |||
| ≢ |
|
| < |
|
| ≤ |
| |||
| ≤ |
|
| > |
|
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
| ≡ |
|
| ≡ |
|
| = |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
| |||
|
|
| = |
| |||
= |
| ||||
= |
| ||||
≈ |
|
algorithm input | algorithm output | meaning | description |
actually a composite number (this is not known at time of input) |
composite | the input is composite | true negative |
actually a prime number (this is not known at time of input) |
prime | the input is prime | true positive |
algorithm input | algorithm output | meaning | description |
actually a composite number (this is not known at time of input) |
composite | the input is definitely composite |
true negative |
actually a composite number (this is not known at time of input) |
probably prime | the input is either composite or prime |
false positive |
actually a prime number (this is not known at time of input) |
probably prime | the input is either composite or prime |
true positive |
actually a prime number (this is not known at time of input) |
composite | impossible | false negative (we will not consider algorithms that return such outputs) |
input number |
perfect algorithm |
perfect probable prime algorithm |
less accurate probable prime algorithm |
very inaccurate probable prime algorithm |
2 | prime | probably prime |
probably prime |
probably prime |
3 | prime | probably prime |
probably prime |
probably prime |
4 | composite | composite | probably prime |
probably prime |
5 | prime | probably prime |
probably prime |
probably prime |
6 | composite | composite | composite | probably prime |
7 | prime | probably prime |
probably prime |
probably prime |
8 | composite | composite | probably prime |
probably prime |
9 | composite | composite | composite | probably prime |
10 | composite | composite | probably prime |
probably prime |
| ≡ |
|
| = |
| |||
= |
|
| = |
| |||
| = |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
≡ |
|
for the chosen a we have... |
what it means | probability of this occurring if m is a 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 |
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 |
Euclid's lemma generalization |
⇐ | multiples of coprime a in ℤ/mℤ are a permutation |
||||
⇑ | ||||||
Fermat's little theorem |
random number generator |
⇒ | gcd(m,m+1) = 1 | |||
⇑ | ⇑ | |||||
greatest common divisor algorithm |
⇐ | Fermat primality test |
⇐ | probable prime detector |
||
⇑ | ||||||
probable prime generator |
hw2/hw2.py
. Please follow the gsubmit directions.
pow()
function, which can compute modular exponents efficiently (as in, ak mod n can be written in Python as pow(a,k,n)
), the abs()
function for computing the absolute value of an integer, and the //
for integer division (you should avoid using /
because it does not work for very large integers). Your file may not import any other modules or employ any external library functions associated with integers and sets unless explicitly permitted to do so in a particular problem.
'''
...'''
, in hw2.py
. You may use the =
ascii character to represent the ≡ relational operator on congruence classes.closest(t, ks)
that takes two arguments: a target integer t
and a list of integers ks
. The function should return the integer k
in ks
that is closest to t
(i.e., the integer k
in ks
that minimizes the absolute value of the difference |t
− k
| between the two numbers). This will serve as a helper function for subsequent problems in this assignment.
findCoprime(m)
that takes a single positive integer argument m
and returns an integer b
where b
> 1 and b
is coprime with m
. Your implementation does not need to return exactly the same answers as you see in the example outputs. However, the output generated by your implementation must be coprime with the input. Hint: use facts about coprime numbers (e.g., this, this, this, this, and/or this); the efficiency of the probable prime generator you must assemble in the last problem will depend on the coprimes your algorithm finds not being on the "edges" of the range.
randByIndex(m, i)
that takes two positive integer arguments: m
represents the upper bound of random numbers to be generated, and i
represents an index specifying which random number in a the sequence should be generated. You may assume m
≥ 4 and that 1 ≤ i
≤ m
− 1. The function must return the i
th "random" number in a permutation of the numbers {0, ..., m
− 1}. Your implementation does not need to return exactly the same answers as you see in the example outputs. However, the output generated by your implementation must produce a permutation when used in a comprehension, as in the examples below.
//
when dividing;m.bit_length()
method to efficiently obtain the bit length of an integer.probablePrime(m)
that takes a single integer argument m
where m
>= 1. The function should return True
if m
is probably prime, and False
otherwise. Your code should employ the Fermat primality test by generating some number of random witnesses in the appropriate range and using them to test the primality of m
. You will need to determine what is a reasonable number of potential witnesses to test. Implementations that perform an exponentially large exhaustive search, even if the algorithm is mathematically correct, will not earn full credit.
makePrime(d)
that takes a single integer argument d
where d
>= 1 and returns a probably prime number that has exactly d
digits. Your implementation should be sufficiently efficient to produce an output for d
= 100
in a reasonably short amount of time. Implementations that perform an exponentially large exhaustive search, even if the algorithm is mathematically correct, will not earn full credit.
| ≡ |
| |||
≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
≡ |
|
| = |
| |||
⋮ | |||||
| = |
|
| ≡ |
| |||
⋮ | |||||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
|
| = |
|
| ≡ |
|
efficient modular arithmetic |
||||
⇓ | ||||
Chinese remainder theorem |
⇐ | CRT solver | ⇐ | range ambiguity resolution |
⇑ | ||||
Shamir secret sharing protocol |
| = |
|
| = |
|
| := |
| |||
| := |
| |||
| := |
| |||
| := |
| |||
| := |
| |||
⋮ |
| := |
| |||
| := |
| |||
| := |
| |||
| := |
| |||
| := |
| |||
⋮ |
| > |
| |||
≥ |
| ||||
| = |
| |||
⋮ | |||||
| = |
|
| ≡ |
| |||
⋮ | |||||
| ≡ |
|
| = |
|
greatest common divisor algorithm |
Fermat's little theorem |
Euler's theorem |
||||
⇑ | ⇑ | ⇑ | ||||
Bézout's identity |
⇐ | extended Euclidean algorithm |
⇐ | algorithm for finding multiplicative inverses |
⇒ | Euler's totient function φ |
⇑ | ||||||
Chinese remainder theorem |
⇐ | CRT solver for two equations |
⇑ | |||
induction | ⇐ | CRT solver for n equations |
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ||||||
| ≡ |
|
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| = |
| |||
| ≡ |
|
| ≡ |
|
| ||||||
| ≡ |
|
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
| ≡ |
| |||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| = |
|
| = |
|
| = |
|
| = |
| |||
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
|
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
| < |
|
| < |
| < |
| |||||
| < |
| < |
|
| = |
|
| = |
| |||
| = |
| |||
| ≡ |
| |||
| = |
|
| = |
| |||
= |
| ||||
= |
|
| = |
|
| = |
| |||
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
⋮ | |||||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
| ≡ |
| |||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
|
|
| > |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| = |
| |||
| = |
|
| ≥ |
| |||
| ≥ |
| |||
| ≥ |
| |||
| ≥ |
|
|
| ≡ |
| ||||||
|
| ≡ |
| ||||||
|
| ≡ |
|
| |
| |
| |
| |
|
| = |
| |||
| = |
| |||
= |
| ||||
= |
|
| = |
| |||
= |
| ||||
= |
|
| = |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
|
| = |
|
| = |
| |||
= |
|
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
|
|
| = |
|
| = |
|
| ≡ |
| |||
= |
| ||||
| = |
| |||
= |
| ||||
= |
|
| = |
|
| = |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
= |
| ||||
= |
| ||||
= |
|
| ≡ |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
|
| = |
| |||
| = |
|
| = |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
= |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| = |
|
| = |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
| ≡ |
| |||
≡ |
| ||||
≡ |
|
hw3/hw3.py
. Please follow the gsubmit directions.
pow()
function can compute modular exponents efficiently (as in, ak mod n can be written in Python as pow(a,k,n)
);sum()
function returns the sum of a list of integers (e.g., sum(1,2,3,4)
returns 10
).'''
...'''
, in hw3.py
. You may use the =
ascii character to represent the ≡ relational operator on congruence classes.
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
invPrime(a, p)
that takes two integers a
and p
> 1 where p
is prime. The function should return the multiplicative inverse of a
∈ ℤ/p
ℤ (if a
≡ 0, it should return None
). Your solution must use Fermat's little theorem.
a
and b
, egcd(a, b)
returns a solution (s, t)
to the following instance of Bézout's identity:
| = |
|
egcd()
, implement a function inv(a, m)
that takes two integers a
and m
> 1. If a
and m
are coprime, it should return the multiplicative inverse of a
∈ ℤ/m
ℤ. If a
and m
are not coprime, it should return None
.
solveOne(c, a, m)
that takes three integers c
, a
, and m
≥ 1. If c
and m
are coprime, the function should return the solution x ∈ {0, ..., m
-1} to the following equation:
| ≡ |
|
c
and m
are not coprime, the function should return None
.
solveTwo(e1, e2)
that takes two tuples e1
and e2
as inputs, each of the form (c, a, m)
(i.e., containing three integer elements). Each tuple (c, a, m)
corresponds to an equation of the form:
| ≡ |
|
(c, a, m)
and (d, b, n)
, correspond to a system of equations of the form:
| ≡ |
| |||
| ≡ |
|
solveTwo()
should return the unique solution x to the above system of equations. If either equation cannot be solved using solveOne()
, or n
and m
are not coprime, the function should return None
.
solveAll(es)
that takes a list of one or more equations, each of the form (c, a, m)
. The list corresponds to the system of equations (assume all the mi are mutually coprime):
| ≡ |
| |||
⋮ | |||||
| ≡ |
|
solveAll()
should return the unique solution x to the above system of equations. If any individual equation cannot be solved using solveOne()
, or if the moduli are not all mutually coprime, the function should return None
.
[(2,4),(3,5),(-6,3)]
represents the sum of powers 24 + 35 + (−6)3.
sumOfPowers(nes, ps)
that takes a list of one or more tuples nes
(i.e., nes
is of the form [(a1,n1),...,(ak,nk)]
) as its first argument, and a list of one or more primes ps
(i.e., of the form [p1,...,pm]
) as its second argument. The function should return the correct result of the sum of powers as long as the following is true (e.g., on a computer with unlimited memory and time):
| ≤ |
| < |
|
sumOfPowers()
so that it can handle inputs even if the exponents themselves are extremely large. You must use Euler's theorem to accomplish this; you may not assume that any particular patterns will exist in the bases or exponents.
|
|
|
|
| ≡ |
| |||
≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
|
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
|
|
| ≡ |
| |||
| ≡ |
|
| = |
| = |
|
|
|
| = |
|
|
| = |
| |||
= |
| ||||
| = |
| |||
= |
| ||||
= |
| ||||
| = |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
|
|
|
| = |
| |||
| = |
| |||
| = |
|
| = |
| |||
= |
|
| = |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
| = |
|
| < |
| ≤ |
|
| = |
| |||
= |
| ||||
= |
| ||||
< |
| ||||
< |
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
= |
|
solver for problem B |
⇒ ⇒ ⇒ |
conversion from output(s) from B to output from A |
⇑⇑⇑ | ⇓ | |
conversion from input for A to input(s) for B |
⇐ | solver for problem A |
problem B | ⇐ | problem A |
finding multiplicative inverses |
⇐ | solving two-equation systems using CRT |
problem B premise: can be solved in polynomial time B ∈ P |
⇐ | problem A conclusion: can be solved in polynomial time A ∈ P |
problem B conclusion: cannot be solved in polynomial time B ∉ P |
⇐ | problem A premise: cannot be solved in polynomial time A ∉ P |
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
| |||
= |
| ||||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| ∈ |
| |||
| = |
|
computing φ(n) conclusion: cannot be solved in polynomial time computing φ(n) ∉ P |
⇐ | factoring n conjecture: cannot be solved in polynomial time factoring ∉ P |
| = |
|
| ≡ |
|
| = |
|
| ||||||
| ∈ |
|
| ||||||
| = |
|
|
| = |
| = |
|
| ∈ |
| |||||||
| ∈ |
| |||||||
| = |
|
|
| = |
| = |
|
| |
| |
| |
| |
| |
| |
|
| |
| |
| |
| |
|
| = |
|
| = |
| |||
= |
| ||||
= |
| ||||
| = |
| |||
| = |
| |||
= |
| ||||
| |
| |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
|
| = |
| |||
| = |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
| = |
| |||
= |
| ||||
| = |
| |||
= |
| ||||
= |
| ||||
= |
|
| ≡ |
| |||
| ≡ |
| |||
≡ |
| ||||
| ≡ |
| |||
≡ |
|
| ≡ |
| |||
| ≡ |
| |||
≡ |
| ||||
| ≡ |
| |||
≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
|
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| | |
|
| | |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
| ||||
≡ |
|
| ≡ |
| |||
≡ |
| ||||
≡ |
|
| ≡ |
|
| = |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
|
| = |
| |||
| = |
| |||
= |
| ||||
| | |
|
congruent squares (square roots of congruence classes) |
||||
⇑ | ⇑ | |||
computing φ(n) for n = p ⋅ q |
⇐ ⇒ |
factoring n = p ⋅ q |
||
⇑ | ⇑ | |||
RSA problem (eth roots of congruence classes) |
||||
discrete logarithm (logarithms of congruence classes) |
forging private identifier for n conclusion: cannot be solved in polynomial time forging ∉ P |
⇐ | factoring n conjecture: cannot be solved in polynomial time factoring ∉ P |
alternative efficient algorithm |
⇐ | forging private identifier for n |
⇒ | factoring n |
| ≡ |
| |||
= |
| ||||
| = |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
= |
|
| ≡ |
| |||
| ≡ |
|
breaking Rabin encryption |
⇐ | congruent squares (square roots of congruence classes) |
||||
⇑ | ⇑ | |||||
finding RSA secret key |
⇐ | computing φ(n) for n = p ⋅ q |
⇐ ⇒ |
factoring n = p ⋅ q |
||
⇑ | ⇑ | |||||
decrypting individual RSA messages |
⇐ | RSA problem (eth roots of congruence classes) |
||||
breaking Diffie-Hellman |
⇐ | discrete logarithm (logarithms of congruence classes) |
hw4.py
(submitted to the location hw4/hw4.py
). Please follow the gsubmit directions.
'''
...'''
, in hw4.py
. You may use the =
ascii character to represent the ≡ relational operator on congruence classes.
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
|
factorsFromPhi(n, phi_n)
that takes two integers n
and phi_n
. You may assume (i.e., you do not need to verify in your code) that n
is a product of two distinct positive prime numbers and that phi_n
= φ(n
). The function should return both prime factors of n
as a tuple.
factorsFromRoots(n, x, y)
that takes three integers n
, x
, and y
. You may assume that n
is a product of two distinct positive prime numbers, and that the following is true:
| ≡ |
| |||
| ≢ |
|
n
as a tuple.
phiFromPhiFour(n)
for the existing intractable problem of computing φ that uses a solver for φ-four (call it phi_four()
) as a subroutine. Note: remember that the four primes must be distinct; your reduction must work for all possible instances of the intractable problem.
generate(k)
that takes a single integer input k
and returns a tuple (n,e,d)
corresponding to the public values n
and e
and private key d
in the RSA cryptographic protocol. The output n
must be the product of two distinct, randomly chosen k
-digit primes. You may import and use the Python random number generator (from random import random
or from random import randint
), and you may want to reuse the extended Euclidean algorithm implementation provided in the previous homework assignment.encrypt(m, t)
that takes two inputs: an integer m
and a tuple (n,e)
representing an RSA public key. It should return a single integer: the RSA ciphertext c
.decrypt(c, t)
that takes two inputs: an integer c
representing the ciphertext and a tuple of two integers (n,d)
representing an RSA private key. It should decrypt c
and return the original message m
.sqrtsPrime(a, p)
that takes two arguments: an integer a
and a prime number p
. You may assume that a
and p
are coprime. If p
is not in 3 + 4ℤ or a
has no square roots in ℤ/p
ℤ, the function should return None
. Otherwise, it should return the two congruence classes in ℤ/p
ℤ that solve the following equation:
| ≡ |
|
sqrtsPrimePower(a, p, k)
that takes three arguments: an integer a
, a prime number p
, and a positive integer k
. You may assume that a
and p
are coprime. If p
is not in 3 + 4ℤ or a
has no square roots in ℤ/p
k
ℤ, the function should return None
. Otherwise, it should return the congruence classes in ℤ/p
k
ℤ that solve the following equation:
| ≡ |
|
sqrts(a, pks)
that takes two arguments: an integer a
and a list of tuples pks
in which each tuple is a distinct positive prime number paired with a positive integer power. You may assume that a
and n
are coprime. You may assume that all the primes in pks
are in 3 + ℤ/4ℤ (if any are not, the function should return None
). Let n
be the product of all the prime powers in the list pks
. Then the function should return a set of all the distinct square roots of a
in ℤ/n
ℤ that are solutions to the following equation:
| ≡ |
|
n
ℤ to look for square roots), and it must work for any positive number of entries in pks
.
roots(a, n)
that takes two integers a
and n
and returns all four square roots of a
in ℤ/n
ℤ as a tuple. You may assume that n
is the product of two distinct positive prime numbers. Your algorithm in this problem must work on all possible inputs under the assumption that decryptMsgRabin()
also works on all inputs (not just the fake inputs handled by the definitions above) and that an encrypted message c is never represented by the same congruence class as the original, unencrypted message m or − m (i.e., the implementation follows the guideline regarding good ranges for messages at the end of the definition of the Rabin protocol).
|
|
| = |
|
|
|
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
S2 | ℤ/2ℤ |
[0,1] | 0 |
[1,0] | 1 |
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 |
+ 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] |
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 |
| = |
| |||
| = |
|
(ℤ/2ℤ, +) | ((ℤ/3ℤ)*, ⋅) |
0 + 0 = 0 | 1 ⋅ 1 = 1 |
0 + 1 = 1 | 1 ⋅ 2 = 2 |
1 + 0 = 1 | 2 ⋅ 1 = 2 |
1 + 1 = 0 | 2 ⋅ 2 = 1 |
(ℤ/2ℤ, +) | ((ℤ/6ℤ)*, ⋅) |
0 + 0 = 0 | 1 ⋅ 1 = 1 |
0 + 1 = 1 | 1 ⋅ 5 = 5 |
1 + 0 = 1 | 5 ⋅ 1 = 5 |
1 + 1 = 0 | 5 ⋅ 5 = 1 |
| ≡ |
|
| ≡ |
|
ℤ/3ℤ | ℤ/3ℤ |
0 | 0 |
1 | 2 |
2 | 1 |
ℤ/3ℤ | ℤ/3ℤ |
0 + 0 = 0 | 0 + 0 = 0 |
0 + 1 = 1 | 0 + 2 = 2 |
0 + 2 = 2 | 0 + 1 = 1 |
1 + 0 = 1 | 2 + 0 = 2 |
1 + 1 = 2 | 2 + 2 = 1 |
1 + 2 = 0 | 2 + 1 = 0 |
2 + 0 = 2 | 1 + 0 = 1 |
2 + 1 = 0 | 1 + 2 = 0 |
2 + 2 = 1 | 1 + 1 = 2 |
| = |
| |||
| = |
| |||
| = |
|
| = |
|
| ≡ |
|
| = |
|
| = |
|
| ≡ |
| ≡ |
|
| = |
|
| = |
|
| ≡ |
| ≡ |
|
| ≡ |
|
| ≡ |
|
| = |
|
| = |
|
| = |
|
| = |
|
| = |
| |||
| = |
| |||
| ⊂ |
| |||
| ⊂ |
| |||
| = |
| |||
hw5.py
(submitted to the location hw5/hw5.py
). Please follow the gsubmit directions.
'''
...'''
, in hw5.py
.
|
|
|
|
permute(p, l)
that takes two arguments: a permutation p
(represented as a Python list of integers) and a list l
of the same length as the permutation. It should return the list after it has been permuted according to the permutation.
C(k, m)
that takes two integers k
and m
where k
< m
and returns the cyclic permutation in Cm that shifts all elements up by k.
M(a, m)
that takes two coprime integers a
and m
where 0
< a
< m
and returns the multiplication-induced permutation in Mm that corresponds to multiplication by a modulo m:
sort(l)
that takes a list of integers of some length n and returns:
None
otherwise.http://cs-people.bu.edu/lapets/235/unreliable.php
(e.g., the result of ((2 ⋅ 3 ⋅ 4) mod 7) can be obtained at http://cs-people.bu.edu/lapets/235/unreliable.php?n=7&data=2,3,4
). You can use the Python function below to invoke this script (this Python code needs to run on a computer connected to the internet).
http://cs-people.bu.edu/lapets/235/reliable.php
.privateProduct(xs, p, q)
that takes three inputs: a non-empty list of integers xs
, a prime p
, and another distinct prime q
. The function must compute the product modulo p
of all the integers in the list xs
(assuming the web service performs its job correctly, which it may sometimes not do):
| = |
|
xs
on its own; it must use unreliableUntrustedProduct()
to do so, and at the same time it must not send the actual integers in xs
over the web or reveal them to the web service. Your implementation should leak no information about the entries in xs
or the product obtained by multiplying them to anyone (unless they can solve an intractable problem in modular arithmetic).q
to create public and private RSA keys, and then encrypt all the integers in xs
(you will need to encrypt them modulo n
instead of modulo p
because RSA needs a composite modulus). Next, use unreliableUntrustedProduct()
to compute the product of the RSA-encrypted integers modulo n
(i.e., take advantage of this isomorphism as in this homomorphic encryption example). Finally, your privateProduct()
implementation should decrypt the result and return the product modulo p
.
validPrivateProduct(xs, p, q)
that takes three inputs: a non-empty list of integers xs
, a prime p
, and another distinct prime q
. The function must always correctly compute the product modulo p
of all the integers in the list xs
:
| = |
|
xs
on its own; it must use unreliableUntrustedProduct()
to do so, and at the same time it must not send the actual integers in xs
over the web or reveal them to the web service.r
in ℤ/q
ℤ. For each integer xs[i]
in the list, convert the pair (xs[i], r)
into a value in ℤ/n
ℤ via the CRT isomorphism. Then encrypt all these ℤ/n
ℤ values using RSA and use unreliableUntrustedProduct()
to compute their product. Finally, your validPrivateProduct()
implementation should decrypt the result and convert it back to an answer modulo p
via the opposite direction of the CRT isomorphism.
unreliableUntrustedProduct()
is actually correct, determine whether the decrypted value modulo q
has the expected value (i.e., is it really r
len(xs)
modulo q
). If this check fails, keep repeating the entire process from the beginning until it succeeds.
isomorphism(A, B)
that takes two tuples A
and B
as inputs. Each tuple consists of two entries: the first is an ordered list of elements from an algebraic structure, and the second is a function on elements of that binary structure. Thus, the tuple A
represents an algebraic structure (A, ⊕), and the tuple B
represents an algebraic structure (B, ⊗). You may assume that the list of elements is closed under the operation represented by the function. You may also assume that the bijection between the sets A and B is already provided by the order of the elements in each list (i.e., the ith entry in the first list corresponds to the ith entry in the second). The isomorphism()
function should return True
if there is indeed an isomorphism between (A, ⊕) and (B, ⊗), and False
otherwise.
| ≅ |
|
| ≅ |
|
| ≅ |
| ≅ |
|
| = |
| = |
| = |
|
| = |
| |||
| = |
|
| ≡ |
|
| = |
| |||
| = |
| |||
| = |
| |||
| ≡ |
|
| = |
|
| = |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| = |
|
|
|
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
≡ |
|
| = |
|
ℤ/2ℤ × ℤ/3ℤ | ℤ/6ℤ |
(0,0) | 0 |
(0,1) | 4 |
(0,2) | 2 |
(1,0) | 3 |
(1,1) | 1 |
(1,2) | 5 |
|
|
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
|
| = |
| |||
| = |
|
| = |
|
| ≡ |
| |||
| ≡ |
|
| = |
| |||
| = |
|
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| ||||||||||
| ≡ |
|
| ≡ |
| ||||||||||
≡ |
| |||||||||||
≡ |
|
| ≡ |
| ||||||||||
| ≡ |
| ||||||||||
| ≡ |
|
| ≡ |
|
greatest common divisor algorithm |
Fermat's little theorem |
Euler's theorem |
||||
⇑ | ⇑ | ⇑ | ||||
Bézout's identity |
⇐ | extended Euclidean algorithm |
⇐ | algorithm for finding multiplicative inverses |
⇒ | Euler's totient function φ |
⇑ | ||||||
Chinese remainder theorem |
⇐ | CRT solver for two equations |
⇑ | |||
linear congruence theorem |
⇐ | general CRT solver for two equations |
⇑ | |||
induction | ⇐ | general CRT solver for n equations |
formula for 3+4ℤ primes |
⇐ | square roots modulo p |
⇑ | |||
Hensel's lemma | ⇐ | square roots modulo pk |
⇑ | |||
CRT solver for two equations |
⇐ | square roots modulo n ⋅ m |
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
""
be the empty string. Then (S, +) is an algebraic structure that is a monoid because string concatenation is associative and ""
is the identity with respect to string concatenation.
[]
be the empty list. Then (L, +) is an algebraic structure that is a monoid because list concatenation is associative and []
is the identity with respect to list concatenation.
[]
.
abstract algebraic structure | concrete data structure |
element in set of generators S | individual character, string, or data object |
set of generators S | base cases; alphabet; data containers |
operator ⊕ | constructor for node with children; operator/function/method on data items |
element in closure of S under ⊕ | individual data object |
closure of S under ⊕ | set of all possible data objects |
magma | commutative magma |
semigroup | commutative semigroup |
monoid | group | abelian group |
|
typical data structures |
binary trees under node constructor |
binary trees with unordered branches under node constructor |
lists with list concatenation; strings with string concatenation |
sets with duplicates |
lists with list concatenation and empty list; strings with string concatenation and empty string |
||
distributed computation |
must operate on data in its original ordering and hierarchization |
must operate on data in its original hierarchization |
must operate over original ordering |
can operate on data in any order |
can employ identity as a base case; can ignore identity entries |
can "cancel" pairs of adjacent inverses |
can "cancel" all elements that can be paired with an inverse |
distributed storage |
must store original ordering and hierarchization |
must store original hierarchization |
must store original ordering | can store in any order |
no need to store identities |
||
compression | common subtrees | common hierarchies | run-length encoding | distinct elements with quantities |
can ignore identity entries |
can "cancel" pairs of adjacent inverses; can apply invertible transformations |
can "cancel" all elements that can be paired with an inverse |
example/ test case enumeration |
can enumerate examples/test cases automatically | ||||||
proving implementation works correctly for all inputs |
can show this by structural induction |
| = |
|
| ≡ |
| |||
| ≡ |
|
| = |
|
| = |
|
|
| ≡ |
|
| ≡ |
|
| = |
| |||
| = |
|
| ≅ |
|
| = |
|
| = |
|
| ||||||
| = |
|
| ||||||
| = |
|
|
hw6.py
(submitted to the location hw6/hw6.py
). Please follow the gsubmit directions.
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
solveOne(c, a, m)
that takes three integers c
, a
, and m
≥ 1. If it exists, the function should return the solution x ∈ {0, ..., m
-1} to the following equation:
| ≡ |
|
None
. The function must work correctly for all possible equations (you should use the linear congruence theorem).
solveTwo(e1, e2)
that takes two tuples e1
and e2
as inputs, each of the form (c, a, m)
(i.e., containing three integer elements). Each tuple (c, a, m)
corresponds to an equation of the form:
| ≡ |
|
(c, a, m)
and (d, b, n)
, correspond to a system of equations of the form:
| ≡ |
| |||
| ≡ |
|
solveTwo()
should return the unique solution x to the above system of equations. If either equation cannot be solved using solveOne()
, the function should return None
.
solveAll(es)
that takes a list of one or more equations, each of the form (c, a, m)
. The function should return the unique solution x to the system of equations represented by the list of equations. If the system of equations has no solution, the function should return None
.
factor(n)
that finds a non-trivial factor of a composite number input n
by calling quantum()
. Solutions that use exhaustive search will receive no credit.+
anywhere in your solutions to this problem. You may assume you are given access to a function plus256unreliable(x, y)
that returns an answer that is at most 4 away from the true sum modulo 256
(assume there is no chance of this error causing the answer to wrap around):
| < |
|
plus16(x, y)
that reliably returns (x + y) % 16
with 100% accuracy. You may use //
, *
, plus256unreliable()
, and numerical constants, but you may not use anything else in your definition. Hint: you can call plus256unreliable()
more than once.plus256(x, y)
that reliably returns (x + y) % 256
with 100% accuracy. Your solution must use solveAll()
, and you are allowed to use %
, but you may not use the addition or subtraction operators: choose four appropriate prime or mutually coprime moduli, perform the addition operations modulo those moduli, then restore the original result using solveAll()
.decompose()
that decomposes a given element in the algebra into a list in which each generator from {a, b, c, d, e, f, g} that occurs in the input element is paired with exactly one integer. The integer should be chosen so that reassemble()
below can work correctly. Your output should look something like the following (the full output is not revealed as it is part of the problem):
reassemble()
that takes a randomly rearranged output from decompose()
and reassembles an equivalent element within the algebraic structure.
| = |
| |||
| = |
| |||
| = |
|
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
|
| ≡ |
|
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ∈ |
| |||
| ∈ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ∈ |
| |||
| ∈ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ∈ |
| |||
| ∈ |
|
| ∈ |
|
| ≡ |
|
| |
|
| = |
| |||
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
| = |
|
| = |
|
|
| = |
|
| = |
| |||
| = |
| |||
| ≡ |
|
| → |
| |||
| → |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
gsubmit
. This section reproduces and extends some of the instructions already made available by the BU Computer Science Department.csa
machines maintained by the CS Dept. You will need to physically visit the undergraduate computing lab located at 730 Commonwealth Avenue, on the third floor in room 302.csa
home directory. If you are using Windows, you will also need an SSH client (such as PuTTY).
local device
|
your csa2 /csa3 home directory |
your gsubmit directory for CS 235 |
csa2
or csa3
using an SCP or SSH client and create a directory for your submission in your CS account home directory. Note that in the examples below %>
represents a terminal prompt, which may look different on your system.
local device
|
your csa2 /csa3 home directory
|
your gsubmit directory for CS 235 |
csa2
or csa3
using an SCP client and copy your completed file(s) into that directory.
local device
|
⇒ |
your csa2 /csa3 home directory
|
your gsubmit directory for CS 235 |
csa2
or csa3
using an SSH client and run the gsubmit
commands to copy the files from your CS account home directory to the gsubmit
directories to which the course staff has access.
local device
|
⇒ |
your csa2 /csa3 home directory
|
⇒ |
your gsubmit directory for CS 235
|
csa2/csa3
..py
. For example, suppose the following is contained within a file called example.py
:
python3
, python3.2
, python3.3
, etc. depending on the Python installation you're using). Note that in the examples below %>
represents a terminal prompt, which may look different on your system.
True
and False
.and
, or
, and not
.+
, *
, -
, and /
. The infix operator //
represents integer division, and the infix operators **
represents exponentiation. Negative integers are prefixed with the negation operator -
.==
, !=
, <
, >
, <=
, >=
are available.int()
function can convert a string that looks like an integer into an integer.'
or "
characters. Strings can be treated as lists of 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).''
or ""
.+
.len()
returns the length of a string.s[i]
). These characters are also strings themselves.[
and ]
, with the individual list entries separated by commas. Lists cannot be members of sets.[]
.+
.len()
returns the length of a list.a[i]
).in
relational operator.(
and )
, with entries separated by commas. The main distinction between lists and tuples is that tuples are hashable (i.e., they can be members of sets).()
.x
is denoted using (x, )
.+
.list()
function.tuple()
function.len()
returns the length of a tuple.t[i]
).in
relational operator.set()
..union()
and .intersect
correspond to the standard set operations.set()
function.list()
or list()
function, respectively.len()
returns the size of a set.in
relational operator.frozenset()
function.
{}
.list(d.keys())
.list(d.values())
.len()
returns the number of entries in the dictionary.d[key]
).example()
is defined as follows:
*
-operator, the scatter operator, or the splat operator) involves providing a list to the function, preceded by the *
symbol; the arguments will be drawn from the elements in the list.
**
-operator) involves providing a dictionary to the function, preceded by the **
symbol; each named paramter in the function definition will be looked up in the dictionary, and the value associated with that dictionary key will be used as the argument passed to that parameter.
for
clause. This will filter which combinations are actually used to add a value to the resulting list.
type()
can be used to determine the type of a value. Below, we provide examples of how to check whether a given expression has one of the common Python types:
if
, else
, and/or elif
), an iteration construct (i.e., a for
or while
loop), a return
statement, or a break
or continue
statement.def
keyword, followed by the name of the function or procedure, and then by one or more arguments (delimited by parentheses and separated by commas).
else
). The body of each branch is an indented sequence of statements.
if
). The body is executed over and over until the expression in the condition evaluates to False
, or a break
statement is encountered.