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 |
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 |
|
False
. This is effectively the implementation of a quantifier, which we introduce further below.
prime()
by supplying appropriate arguments:
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 | visual example |
X × Y is the set product of X and Y | X × Y = { (x,y) | x ∈ X, y ∈ Y } | !relation({'a','b','c'}, {'x','y','z'}, {('a','x'),('a','y'),('a','z'),('b','x'),('b','y'),('b','z'),('c','x'),('c','y'),('c','z')}) |
R is a relation between X and Y | R ⊂ X × Y | !relation({'a','b','c'}, {'x','y','z'}, {('a','x'),('b','x'),('b','z'),('c','z')}) |
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 |
!relation({'a','b','c'}, {'x','y','z'}, {('a','x'),('b','x'),('c','z')}) |
R is an injection from X to Y |
R is a function from X to Y and ∀ y ∈ Y, there is at most one x ∈ X s.t. (x,y) ∈ R |
!relation({'a','b','c'}, {'x','y','z'}, {('a','x'),('b','y')}) |
R is a surjection from X to Y |
R is a function from X to Y and ∀ y ∈ Y, there is at least one x ∈ X s.t. (x,y) ∈ R |
!relation({'a','b','c','d'}, {'x','y','z'}, {('a','x'),('c','y'),('d','z')}) |
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 |
!relation({'a','b','c'}, {'x','y','z'}, {('a','y'),('b','z'),('c','x')}) |
R is a permutation on X |
R ⊂ X × X and R is a bijection between X and X |
!relation({'a','b','c'}, {('a','b'),('b','c'),('c','a')}) |
R is a reflexive relation on X | R ⊂ X × X and ∀ x ∈ X, (x,x) ∈ R |
!relation({'a','b','c'}, {('a','a'),('b','b'),('c','c')}) |
R is a symmetric relation on X | R ⊂ X × X and ∀ x ∈ X, ∀ y ∈ X, (x,y) ∈ R implies (y,x) ∈ R |
!relation({'a','b','c'}, {('a','b'),('b','a'),('c','c')}) |
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 |
!relation({'a','b','c'}, {('a','b'),('b','c'),('a','c')}) |
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 |
!relation({'a','b','c'}, {('a','a'),('b','b'),('a','b'),('b','a'),('c','c')}) |
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.
perfectSquares(n)
that takes a single positive integer argument n
and returns all positive perfect square integers less than or equal to n. You must use a set comprehension to receive credit. Efficiency is not important.
squareFree(n)
that takes a single positive integer argument n
and returns True
if and only if n
has no square factors. This happens only when the following logical formula is true for all integers k
greater than 1 but less than n
:
|
same(n, m)
that takes two positive integer arguments n
and m
and returns True
if both are perfect squares or if both are not perfect squares, and False
otherwise.
separate(S)
that takes any finite set of positive integers S
and returns a relation over S
in which any two numbers in S
that are both perfect squares are related to each other, and in which any two numbers in S
that are both not perfect squares are related to each other.
separate()
(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:
separate()
, simply assign None
to the corresponding variable. If a property does not apply to all outputs of separate()
, 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)
). You cannot use loops, and you must use quantifiers to receive credit; see this example.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.
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 formulas are satisfied:
R2
above so that R2
is an equivalence relation over X2
, and so that the following formulas are satisfied:
R3
above so that R3
is an equivalence relation over X3
, and so that the following formulas satisfied:
R3
. Solutions that use an explicitly defined set will receive no credit.
| = |
|
minimumFlights()
that takes a set of countries C and a relation on that set D representing reachability by driving, and returns an integer representing the minimum number of flights you will need to take to visit every country.
longestDrive()
that takes a set of countries C and a relation on that set D representing reachability by driving, and returns an integer representing the maximum number of countries you can visit on a single, uninterrupted drive.
| = |
|
| = |
|
| = |
|
| ∈ |
| |||
| ∈ |
|
| = |
| |||
| = |
| |||
| = |
|
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 |
gcd(m,m+1) = 1 | |||
⇑ | ⇑ | |||||
Fermat's little theorem |
random number generator |
⇒ | coprime generator |
|||
⇑ | ⇑ | |||||
greatest common divisor algorithm |
⇐ | Fermat primality test |
⇐ | probable prime detector |
||
⇑ | ||||||
probable prime generator |
hw2/hw2.py
. Please follow the gsubmit directions.
.bit_length()
method to efficiently obtain the bit length of an integer,pow()
function to compute modular exponents efficiently (i.e., ak mod n can be written in Python as pow(a,k,n)
),abs()
function for computing the absolute value of an integer,//
operator for integer division (you should avoid using /
because it does not work for very large integers).'''
...'''
, 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).
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} by implementing the simplified linear congruential generator with a well-chosen coprime.
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 to compute modular exponents efficiently (i.e., ak mod n can be written in Python as pow(a,k,n)
), andsum()
function that 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, b, a, m)
that takes four integers c
, b
, 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, b, a, m)
(i.e., containing four integer elements). Thus, the two tuples, if we call them (c, b, a, m)
and (t, s, r, 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, b, a, m)
. The list corresponds to the system of equations (assume all the mi are mutually coprime):
| ≡ |
| |||
⋮ | |||||
| ≡ |
|
solveAll()
should return the unique congruence class 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.sumPowsModPrime(nes, p)
that takes a list nes
representing a sum of powers and, as efficiently as possible, computes the sum modulo a prime p
. You may not assume that any particular patterns will exist in the bases or exponents (e.g., make sure that your function behaves correctly if a base is a multiple of the prime modulus p
).
pow()
to write a one-line body for this function.sumPowsModPrimes(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):
| ≤ |
| < |
|
makePrime(d, k)
function from Assignment #2 so that it uses Python's own random.randint()
function and returns a list of k
distinct primes, each of which is d
digits long.
|
|
|
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
|
| ≡ |
| |||
| ≡ |
|
|
|
|
|
|
|
| = |
| |||
| = |
| |||
| = |
|
| = |
| |||
= |
|
| = |
| |||
= |
| ||||
= |
| ||||
= |
| ||||
= |
| ||||
| = |
|
| < |
| ≤ |
|
| = |
| |||
= |
| ||||
= |
| ||||
< |
| ||||
< |
|
| ≡ |
| |||
| ≡ |
|
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.
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
| ≡ |
|
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
.
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.
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
.
|
|
| = |
|
|
|
| = |
|
| = |
| |||
| = |
| |||
| = |
| |||
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 |
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
| |||
| ≡ |
|
| ≡ |
|
| = |
| = |
| = |
|
| ≡ |
|
| = |
| |||
| = |
|
|
| = |
|
| = |
| |||
| = |
|
| = |
| |||||||||||
| = |
| = |
| = |
| |||||||
| = |
| = |
| = |
| |||||||
⋮ | ⋮ | ⋮ |
| = |
|
hw6.py
(submitted to the location hw6/hw6.py
). Please follow the gsubmit directions.
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
| ≡ |
| |||
| ≡ |
|
solveOne(c, b, a, m)
that takes four integers c
, b
, a
, and m
≥ 1. If it exists, the function should return the unique solution x ∈ ℤ/(m
/gcd(c
,m
))ℤ to the following equation:
| ≡ |
|
None
. The function must work correctly for all possible equations (you should use the linear congruence theorem).
solveOneSameMod(c, b, a, m)
that takes four integers c
, b
, a
, and m
≥ 1. If it exists, the function should return the set of all solutions x ∈ ℤ/m
ℤ to the following equation:
| ≡ |
|
None
. Your solution does not need to be efficient, but it must use solveOne()
as a subroutine.
solveTwo(e1, e2)
that takes two tuples e1
and e2
as inputs, each of the form (c, b, a, m)
(i.e., containing four integer elements). Each tuple (c, b, a, m)
corresponds to an equation of the form:
| ≡ |
|
(c, b, a, m)
and (t, s, r, 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, b, 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
.
+
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()
.n
∈ ℕ and a
∈ ℤ/nℤ, it returns the smallest non-zero congruence class r ∈ ℤ/φ(n)ℤ such that a
r ≡ 1 (mod n
). In other words, it returns |closure({a
}, ⋅)| where ⋅ is multiplication modulo n
.
factor(n)
that returns a non-trivial factor of a composite number input n
= p ⋅ q by calling quantum()
. Solutions that use exhaustive search will receive no credit.quantum()
. In this problem, you will implement an efficient version of quantum()
using another function. 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 efficiently computes the average of the following set of values:
|
k
∈ {k1
, ..., k2
}. An inefficient but equivalent implementation is provided below for testing purposes:
quantum(a, n)
that takes any composite n
that is the product of two distinct primes, and returns the smallest non-zero congruence class r ∈ ℤ/φ(n)ℤ such that ar ≡ 1 (mod n). Your implementation of quantum()
may make up to log2(n
) calls to blackbox()
, but not more than that.
|
|
| ≡ |
| |||
| ≡ |
|
| |
|
| = |
|
| ≡ |
| |||
| ≡ |
|
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.