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

f_{1} and f_{2}  only true if both f_{1} and f_{2} are true  True and False 
f_{1} or f_{2}  true if f_{1} or f_{2} (or both) are true  True or (False and True) 
f_{1} implies f_{2} 

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

True == False 
¬ f  true if f is false  not (True or (False and True)) 
( f )  true if f is true  (True and (not (False)) 
predicate example  depends on the definition of the predicate 
isPrime(7) 
isPrime(?)
that takes one argument, the meaning of isPrime(7)
should be true but the meaning of isPrime(4)
should be false.
meaning of lefthand side (premise) 
meaning of righthand side (conclusion) 
meaning of entire formula 
comments 
true  true  true  if the premise is true and the conclusion is true, the claim of implication is true; thus, the whole formula is true 
true  false  false  if the premise is true but the conclusion is false, the conclusion is not implied by the premise, so the claim of implication is false; thus, the formula is false 
false  true  true  if the conclusion is true on its own, it doesn't matter that the premise is false, because anything implies an independently true conclusion; thus, the claim of implication is true, and so is the entire formula 
false  false  true  if we assume that a false premise is true, then "false" itself is "true"; in other words, false implies itself, so the formula is true 

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

term  what it represents  example of one possible Python representation 
0  0  0 
1  1  1 
z_{1} + z_{2}  the integer sum of z_{1} and z_{2}  3 + 4

z_{1} − z_{2}  the integer difference of z_{1} and z_{2}  (1 + 2)  4

z_{1} ⋅ z_{2}  the integer product of z_{1} and z_{2}  3 * 5

z_{1} mod z_{2}  the remainder of the integer quotient z_{1} / z_{2} z_{1}  ⌊ z_{1}/z_{2} ⌋ ⋅ z_{2} 
17 % 5

z_{1}^{z2}  product of z_{2} instances of z_{1}  2**3 pow(2,3)

formula  what it represents  example of one possible Python representation 
z_{1} = z_{2}  true if z_{1} and z_{2} have the same meaning; false otherwise 
1 == 2 
z_{1} < z_{2}  true if z_{1} is less than z_{2}; false otherwise 
4 < 3 
z_{1} > z_{2}  true if z_{1} is greater than z_{2}; false otherwise 
4 > 3 
z_{1} ≤ z_{2}  true if z_{1} is less than or equal to z_{2}; false otherwise 
4 <= 3 
z_{1} ≥ z_{2}  true if z_{1} is greater than or equal to z_{2}; false otherwise 
4 >= 3 
z_{1} ≠ z_{2}  true if z_{1} is not equal to z_{2}; false otherwise 
4 != 3 
predicate definition  example of one possible Python representation 
P(x) iff x > 0 and x < 2  def P(x): return x > 0 and x < 2 
Q(x) iff x > 3  Q = lambda x: x > 3 
formula  what it represents  example of one possible Python representation 
P(1)  true  P(1) 
P(1) or P(2)  true  P(1) or P(2)

Q(1) and Q(2)  false  Q(1) and Q(2)

formula  what it represents 
x  y 

y is prime 

def divides(x, y):
return y % x == 0 # The remainder of y/x is 0.
def prime(y):
for x in range(2,y):
if divides(x,y):
return False
return True
False
. This is effectively the implementation of a quantifier, which we introduce further below.
def doesNotDivide(x, y):
return y % x != 0 # The remainder of y/x is nonzero.
def prime(y):
for x in range(2,y):
if not doesNotDivide(x,y):
return False
return True
def checkAll(S, P):
for x in S:
if not P(x):
return False
return True
prime()
by supplying appropriate arguments:
>>> checkAll(set(range(2,y)), lambda x: doesNotDivide(x,y))
term  what it represents  example of one possible Python representation 
∅  a set with no elements in it  set() 
{1,2,3}  {1,2,3}  {1,2,3} 
{2,..,5}  {2,3,4,5}  set(range(2,6)) 
{ x  x ∈ {1,2,3,4,5,6}, x > 3 }  {4,5,6}  {x for x in {1,2,3,4,5,6} if x > 3}

{1,2,3,4}  4  len({1,2,3,4})

term  what it represents  example of one possible Python representation 
S_{1} ∪ S_{2}  {z  z ∈ ℤ, z ∈ S_{1} or z ∈ S_{2}}  {1,2,3}.union({4,5}) {1,2,3}  {4,5} 
S_{1} ∩ S_{2}  {z  z ∈ ℤ, z ∈ S_{1} and z ∈ S_{2}}  {1,2,3}.intersection({2,3,5}) {1,2,3} & {2,3,5} 
S  the number of elements in S  len({1,2,3}) 
term  what it represents 
ℕ  {0, 1, 2, ...} 
ℤ  {..., 2, 1, 0, 1, 2, ...} 
def forall(S, P):
for x in S:
if not P(x):
return False
return True
def exists(S, P):
for x in S:
if P(x):
return True
return False
subset()
operation on sets.
def forall(X, P):
S = {x for x in X if P(x)}
return len(S) == len(X)
def exists(X, P):
S = {x for x in X if P(x)}
return len(S) > 0
def subset(X,Y):
return forall(X, lambda x: x in Y)
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 

# We provide two equivalent implementations.
def all(X, P):
return forall(X, P)
def all(X, P):
S = {x for x in X if P(x)}
return len(S) == len(X)
# We provide two equivalent implementations.
def none(X, P):
return forall(X, lambda x: not P(x))
def none(X, P):
S = {x for x in X if P(x)}
return len(S) == 0
def atMostOne(X, P):
S = {x for x in X if P(x)}
return len(S) <= 1
# We provide two equivalent implementations.
def atLeastOne(X, P):
return exists(X, P)
def atLeastOne(X, P):
S = {x for x in X if P(x)}
return len(S) >= 1
def prime(p):
return p > 1 and forall(set(range(2, p)), lambda n: p % n != 0)
formula  what it represents  example of one possible Python representation 
3 ∈ {1,2,3}  true  3 in {1,2,3} 
{1,2} ⊂ {1,2,3}  true  subset({1,2}, {1,2,3}) 
{4,5} ⊂ {1,2,3}  false  subset({4,5}, {1,2,3}) 
formula  what it represents 
z ∈ S  true if z is an element of S; false otherwise 
S_{1} ⊂ S_{2}  ∀ z ∈ S_{1}, z ∈ S_{2} 
S_{1} = S_{2}  S_{1} ⊂ S_{2} and S_{2} ⊂ S_{1} 
term  what it represents  example of one possible Python representation 
{1,2} × {5,6,7}  {(1,5),(1,6),(1,7),(2,5),(2,6),(2,7)}  { (x,y) for x in {1,2} for y in {4,5,6,7} } 
predicate  definition  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 (manytoone) map from X to Y 
R is a relation between X and Y and ∀ x ∈ X, there is at most one y ∈ Y s.t. (x,y) ∈ R 
!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')}) 
evens = { 2 * x for x in set(range(0,51)) }
evens = { x for x in set(range(0,101)) if x % 2 == 0 }
X
and Y
.
def product(X, Y):
return { (x,y) for x in X for y in Y }
def leq(S):
return { (x, y) for x in S for y in S if x <= y }
R
is a relation over a set X
.
# Using our definition of subset().
def relation(R, X):
return subset(R, product(X, X))
# Using the builtin set implementation.
def relation(R, X):
return R.issubset(product(X, 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 <=
.
def isAsymmetric(X, R):
return relation(R,X) and forall(X, lambda a: forall(X, lambda b: ((a,b) in R) <= (not ((b,a) in R))))
 = 

def quotient(X,R):
return {frozenset({y for y in X if (x,y) in R}) for x in X}
>>> quotient({1,2,3,4}, {(1,1),(2,2),(3,3),(2,3),(3,2),(4,4)})
{frozenset({4}), frozenset({2, 3}), frozenset({1})}
def quotientMap(X,R):
return {(x, frozenset({y for y in X if (x,y) in R})) for x in X}
 = 

{'Alice', 'Bob', 'Carl', 'Dan', and 'Eve'}
:
R = {\
('Alice', 'Alice'), ('Bob', 'Bob'), ('Carl', 'Carl'), ('Dan', 'Dan'), ('Eve', 'Eve'),\
('Alice', 'Carl'), ('Carl', 'Alice'), ('Dan', 'Eve'), ('Eve', 'Dan')\
}
families = quotient({'Alice', 'Bob', 'Carl', 'Dan', 'Eve'}, R)
 = 

 = 

 = 

 ∈ 
 
 ∈ 

 = 
 
 = 
 
 = 

term  what it represents 
z z mod m z + mℤ 
{z + (a ⋅ m)  a ∈ ℤ} 
c_{1} + c_{2}  {(x + y)  x ∈ c_{1}, y ∈ c_{2}} 
c_{1} − c_{2}  {(x − y)  x ∈ c_{1}, y ∈ c_{2}} 
c_{1} ⋅ c_{2}  {(x ⋅ y)  x ∈ c_{1}, y ∈ c_{2}} 
c^{z}  c ⋅ ... ⋅ c 
c!  c ⋅ (c1) ⋅ (c2) ⋅ ... ⋅ 1 
formula  what it represents 
c_{1} ≡ c_{2}  true only if c_{1} ⊂ c_{2} and c_{2} ⊂ c_{1}, i.e., set equality applied to the congruence classes c_{1} and c_{2}; false otherwise 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 


 ≡ 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
≡ 
 
≡ 

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

 = 
 
 = 
 
 = 
 
 ≡ 

 = 
 
 = 
 
 = 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

  
 
 = 
 
 ≡ 
 
 ≡ 

 = 
 
 = 
 
 = 
 
 ∈ 
 
  

  
 
 ∈ 
 
 = 
 
 = 
 
 = 
 
 = 


 ≡ 
 
  
 
  
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ∤ 
 
 ≢ 
 
 ∤ 
 
 ≢ 

 ≡ 
 
 ≡ 
 
 = 
 
 = 
 
  

  
 
 = 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 

 = 

 = 
 
= 

 ≠ 
 
 = 

 = 
 
 = 
 
 = 
 
  

 = 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 = 
 
 = 
 
 = 

 = 
 
 = 
 
 = 

 = 

 = 

 = 

 = 
 
 = 

 = 
 
 = 
 
 = 
 
= 
 
= 
 
= 

def gcd(x, y):
return max({z for z in range(0, min(x,y)) if x % z == 0 and y % z == 0})

 ≢ 
 
 ≢ 

 ≡ 

 ≡ 

 = 
 
 = 
 
 = 
 
 = 
 
 = 

 < 

 ≤ 
 
 ≤ 

 > 

 = 
 
 = 
 


 = 
 
= 
 
= 
 
≈ 

algorithm input  algorithm output  meaning  description 
actually a composite number (this is not known at time of input) 
composite  the input is composite  true negative 
actually a prime number (this is not known at time of input) 
prime  the input is prime  true positive 
algorithm input  algorithm output  meaning  description 
actually a composite number (this is not known at time of input) 
composite  the input is definitely composite 
true negative 
actually a composite number (this is not known at time of input) 
probably prime  the input is either composite or prime 
false positive 
actually a prime number (this is not known at time of input) 
probably prime  the input is either composite or prime 
true positive 
actually a prime number (this is not known at time of input) 
composite  impossible  false negative (we will not consider algorithms that return such outputs) 
input number 
perfect algorithm 
perfect probable prime algorithm 
less accurate probable prime algorithm 
very inaccurate probable prime algorithm 
2  prime  probably prime 
probably prime 
probably prime 
3  prime  probably prime 
probably prime 
probably prime 
4  composite  composite  probably prime 
probably prime 
5  prime  probably prime 
probably prime 
probably prime 
6  composite  composite  composite  probably prime 
7  prime  probably prime 
probably prime 
probably prime 
8  composite  composite  probably prime 
probably prime 
9  composite  composite  composite  probably prime 
10  composite  composite  probably prime 
probably prime 
 ≡ 

 = 
 
= 

 = 
 
 = 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
≡ 

 ≢ 
 
 ≢ 

for the chosen a we have... 
what it means  probability of this occurring if m is a nonCarmichael composite 
a  m  a is a nontrivial factor of m, so m is composite 
(# integers in {2,...,m1} that are factors with m) / (m2) 
gcd(a,m) ≠ 1  m and a have a nontrivial factor, so m is composite 
(# integers in {2,...,m1} that share factors with m) / (m2) 
a^{m1} mod m ≠ 1  a is a Fermat witness that m is composite 
at least 1/2 
m = 15 and a = ...  2  3  4  5  6  7  8  9  10  11  12  13  14 
a  m  PP  C  PP  C  PP  PP  PP  PP  PP  PP  PP  PP  PP 
gcd(a,m) ≠ 1  PP  C  PP  C  C  PP  PP  C  C  PP  C  PP  PP 
a^{m1} mod m = ...  4  9  1  10  6  4  4  6  10  1  9  4  1 
Euclid's lemma generalization 
⇐  multiples of coprime a in ℤ/mℤ are a permutation 
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 
 ≡ 
 
≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 

 = 
 
⋮  
 = 

 ≡ 
 
⋮  
 ≡ 

 ≡ 
 
 ≡ 

 = 
 
 = 

 = 

 ≡ 

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

 ≡ 
 
 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 
 ≡ 


 ≡ 
 
 ≡ 
 
 ≡ 
 
 = 
 
 ≡ 

 ≡ 

 
 ≡ 


 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 

 ≡ 

 = 

 = 

 = 

 = 
 
 = 
 
 = 

 = 
 
 = 
 
 = 

 = 

 = 
 
 = 

 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 

 < 

 < 
 < 
 
 < 
 < 

 = 

 = 
 
 = 
 
 ≡ 
 
 = 

 = 
 
= 
 
= 

 = 

 = 
 
 ≡ 
 
 ≡ 

 = 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 = 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
⋮  
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 


 > 

 ≡ 
 
 ≡ 
 
 ≡ 
 

 ≡ 
 

 ≡ 
 

 ≡ 

 = 
 
 = 
 
= 
 
= 

 = 
 
= 
 
= 

 = 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 

 = 

 = 
 
= 

 = 

 = 
 
 = 
 
 = 
 
= 
 
= 
 
= 
 


 = 

 = 

 ≡ 
 
= 
 
 = 
 
= 
 
= 

 = 

 = 

 ≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
= 
 
= 
 
= 

 ≡ 
 
= 
 
= 
 
= 
 
= 
 
= 

 = 
 
 = 

 = 
 
= 
 
= 
 
= 
 
= 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 = 

 = 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
= 
 
 ≡ 
 
≡ 
 
≡ 





 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 


 ≡ 
 
 ≡ 







 = 
 
 = 
 
 = 

 = 
 
= 

 = 
 
= 
 
= 
 
= 
 
= 
 
 = 

 < 
 ≤ 

 = 
 
= 
 
= 
 
< 
 
< 

 ≡ 
 
 ≡ 

solver for problem B 
⇒ ⇒ ⇒ 
conversion from output(s) from B to output from A 
⇑⇑⇑  ⇓  
conversion from input for A to input(s) for B 
⇐  solver for problem A 
problem B  ⇐  problem A 
finding multiplicative inverses 
⇐  solving twoequation systems using CRT 
problem B premise: can be solved in polynomial time B ∈ P 
⇐  problem A conclusion: can be solved in polynomial time A ∈ P 
problem B conclusion: cannot be solved in polynomial time B ∉ P 
⇐  problem A premise: cannot be solved in polynomial time A ∉ P 
 = 
 
 = 
 
 = 
 
 = 
 
 = 

 = 
 
 = 

 = 
 
 = 

 = 
 
 = 
 
= 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 ∈ 
 
 = 

computing φ(n) conclusion: cannot be solved in polynomial time computing φ(n) ∉ P 
⇐  factoring n conjecture: cannot be solved in polynomial time factoring ∉ P 
 = 

 ≡ 

 = 

 
 ∈ 

 
 = 


 = 
 = 

 ∈ 
 
 ∈ 
 
 = 


 = 
 = 

 
 
 
 
 
 

 
 
 
 

 = 

 = 
 
= 
 
= 
 
 = 
 
 = 
 
= 
 
 
 

 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 


 = 
 
 = 
 
= 
 
= 
 
= 
 
 = 
 
= 
 
 = 
 
= 
 
= 
 
= 

 ≡ 
 
 ≡ 
 
≡ 
 
 ≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
≡ 
 
 ≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 



 ≡ 

 ≡ 

 ≡ 

 = 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

  

  

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 = 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 

 = 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 = 

 = 
 
 = 
 
= 
 
  

congruent squares (square roots of congruence classes) 

⇑⇓  ⇑⇓  
computing φ(n) for n = p ⋅ q 
⇐ ⇒ 
factoring n = p ⋅ q 

⇑  ⇑  
RSA problem (eth roots of congruence classes) 

discrete logarithm (logarithms of congruence classes) 
forging private identifier for n conclusion: cannot be solved in polynomial time forging ∉ P 
⇐  factoring n conjecture: cannot be solved in polynomial time factoring ∉ P 
alternative efficient algorithm 
⇐  forging private identifier for n 
⇒  factoring n 
 ≡ 
 
= 
 
 = 
 
= 
 
= 
 
= 
 
= 
 
= 

 ≡ 
 
 ≡ 

breaking Rabin encryption 
⇐  congruent squares (square roots of congruence classes) 

⇑⇓  ⇑⇓  
finding RSA secret key 
⇐  computing φ(n) for n = p ⋅ q 
⇐ ⇒ 
factoring n = p ⋅ q 

⇑  ⇑  
decrypting individual RSA messages 
⇐  RSA problem (eth roots of congruence classes) 

breaking DiffieHellman 
⇐  discrete logarithm (logarithms of congruence classes) 
 = 

 ≡ 
 
≡ 
 
≡ 
 
≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 



 = 



 = 

 = 
 
 = 
 
 = 
 
S_{2}  ℤ/2ℤ 
[0,1]  0 
[1,0]  1 
S_{2}  ℤ/2ℤ 
[0,1] o [0,1] = [0,1]  0 + 0 = 0 
[0,1] o [1,0] = [1,0]  0 + 1 = 1 
[1,0] o [0,1] = [1,0]  1 + 0 = 1 
[1,0] o [1,0] = [0,1]  1 + 1 = 0 
+ o 
0 [0,1] 
1 [1,0] 
0 [0,1] 
0 [0,1] 
1 [1,0] 
1 [1,0] 
1 [1,0] 
0 [0,1] 
C_{3}  ℤ/3ℤ 
[0,1,2] o [0,1,2] = [0,1,2]  0 + 0 = 0 
[0,1,2] o [1,2,0] = [1,2,0]  0 + 1 = 1 
[0,1,2] o [2,0,1] = [2,0,1]  0 + 2 = 2 
[1,2,0] o [0,1,2] = [1,2,0]  1 + 0 = 1 
[1,2,0] o [1,2,0] = [2,0,1]  1 + 1 = 2 
[1,2,0] o [2,0,1] = [0,1,2]  1 + 2 = 0 
[2,0,1] o [0,1,2] = [2,0,1]  2 + 0 = 2 
[2,0,1] o [1,2,0] = [0,1,2]  2 + 1 = 0 
[2,0,1] o [2,0,1] = [1,2,0]  2 + 2 = 1 
 = 
 
 = 

(ℤ/2ℤ, +)  ((ℤ/3ℤ)*, ⋅) 
0 + 0 = 0  1 ⋅ 1 = 1 
0 + 1 = 1  1 ⋅ 2 = 2 
1 + 0 = 1  2 ⋅ 1 = 2 
1 + 1 = 0  2 ⋅ 2 = 1 
(ℤ/2ℤ, +)  ((ℤ/6ℤ)*, ⋅) 
0 + 0 = 0  1 ⋅ 1 = 1 
0 + 1 = 1  1 ⋅ 5 = 5 
1 + 0 = 1  5 ⋅ 1 = 5 
1 + 1 = 0  5 ⋅ 5 = 1 
 ≡ 

 ≡ 

ℤ/3ℤ  ℤ/3ℤ 
0  0 
1  2 
2  1 
ℤ/3ℤ  ℤ/3ℤ 
0 + 0 = 0  0 + 0 = 0 
0 + 1 = 1  0 + 2 = 2 
0 + 2 = 2  0 + 1 = 1 
1 + 0 = 1  2 + 0 = 2 
1 + 1 = 2  2 + 2 = 1 
1 + 2 = 0  2 + 1 = 0 
2 + 0 = 2  1 + 0 = 1 
2 + 1 = 0  1 + 2 = 0 
2 + 2 = 1  1 + 1 = 2 
 = 
 
 = 
 
 = 

 = 

 ≡ 

 = 

 = 

 ≡ 
 ≡ 

 = 

 = 

 ≡ 
 ≡ 

 ≡ 

 ≡ 

 = 

 = 

 = 

 = 

 = 
 
 = 
 
 ⊂ 
 
 ⊂ 
 
 = 
 
 ≅ 

 ≅ 

 ≅ 
 ≅ 

 = 
 = 
 = 

 = 
 
 = 

 ≡ 

 = 
 
 = 
 
 = 
 
 ≡ 

 = 

 = 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 = 
 
 = 

 = 




 ≡ 

 ≡ 

 ≡ 
 
≡ 

 = 

ℤ/2ℤ × ℤ/3ℤ  ℤ/6ℤ 
(0,0)  0 
(0,1)  4 
(0,2)  2 
(1,0)  3 
(1,1)  1 
(1,2)  5 



 ≡ 
 
 ≡ 

 = 
 
 = 

 ≡ 
 
 ≡ 

 = 
 
 = 

 = 
 
 = 

 ≡ 
 


 ≡ 
 
 ≡ 

 = 
 
 = 


 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 


 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
≡ 
 
≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

greatest common divisor algorithm 
Fermat's little theorem 
Euler's theorem 

⇑  ⇑  ⇑  
Bézout's identity 
⇐  extended Euclidean algorithm 
⇐  algorithm for finding multiplicative inverses 
⇒  Euler's totient function φ 
⇑  
Chinese remainder theorem 
⇐  CRT solver for two equations 

⇑  
linear congruence theorem 
⇐  general CRT solver for two equations 

⇑  
induction  ⇐  general CRT solver for n equations 
formula for 3+4ℤ primes 
⇐  square roots modulo p 

⇑  
Hensel's lemma  ⇐  square roots modulo p^{k} 

⇑  
CRT solver for two equations 
⇐  square roots modulo n ⋅ m 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 = 
 = 
 = 

 ≡ 

 = 
 
 = 


 = 

 = 
 
 = 

 = 
 
 = 
 = 
 = 
 
 = 
 = 
 = 
 
⋮  ⋮  ⋮ 
 = 



 ≡ 
 
 ≡ 

 

 = 

 ≡ 
 
 ≡ 

csa2/csa3
..py
. For example, suppose the following is contained within a file called example.py
:
# This is a comment in "example.py".
# Below is a Python statement.
print("Hello, world.")
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.
%> python example.py
Hello, world.
%> python
Python 3.2 ...
Type "help", "copyright", "credits" or "license" for more information.
>>> exec(open("example.py").read()) # Load "example.py" module.
Hello, world.
>>> x = "Hello." # Execute an assignment statement.
>>> print(x) # Execute a "print" statement.
Hello.
>>> x # Evaluate a string expression.
'Hello.'
>>> 1 + 2 # Evaluate a numerical expression.
3
True
and False
.and
, or
, and not
.
>>> True # A boolean constant.
True
>>> False # A boolean constant.
False
>>> True and False or True and (not False) # A boolean expression.
True
+
, *
, 
, 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.
>>> 123 # An integer constant.
True
>>> 1 * (2 + 3) // 4  5 # An integer expression.
4
>>> 4 * 5 >= 19 # A boolean expression involving integers.
True
>>> int("123") # A string being converted into an integer
123
'
or "
characters. Strings can be treated as lists of singlecharacter strings. Another way to look at this is that there is no distinction between a character and a string: all characters are just strings of length 1. Multiline strings can be delimited using """
or '''
(i.e., three quotation mark characters at the beginning and end of the string literal).''
or ""
.+
.len()
returns the length of a string.s[i]
). These characters are also strings themselves.
>>> 'Example.' # A string.
'Example.'
>>> "Example." # Alternate notation for a string.
'Example.'
>>> len("ABCD") # String length.
4
>>> "ABCD" + "EFG" # String concatenation.
'ABCDEFG'
>>> "ABCD"[2] # Third character in the string.
'C'
[
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.
>>> [1,2,"A","B"] # A list.
[1, 2, 'A', 'B']
>>> [1, 2] + ['A','B'] # Concatenating lists.
[1, 2, 'A', 'B']
>>> len([1,2,"A","B"] ) # List length.
4
>>> [1,2,"A","B"][0] # First entry in the list.
1
>>> 1 in [1, 2] # List containment check.
True
(
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.
>>> (1,2,"A","B") # A tuple.
(1, 2, 'A', 'B')
>>> (1,) # Another tuple.
(1,)
>>> (1, 2) + ('A','B') # Concatenating tuples.
(1, 2, 'A', 'B')
>>> list((1, 2, 'A','B')) # A tuple being converted into a list.
[1, 2, 'A', 'B']
>>> tuple([1, 2, 'A','B']) # A list being converted into a tuple.
(1, 2, 'A', 'B')
>>> len((1,2,"A","B")) # Tuple length.
4
>>> (1,2,"A","B")[0] # First entry in the tuple.
1
>>> 1 in (1, 2) # Tuple containment check.
True
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.
>>> {1,2,"A","B"} # A set.
{1, 2, 'A', 'B'}
>>> ({1,2}.union({3,4})).intersection({4,5}) # Set operations.
{4}
>>> set([1, 2]).union(set(('A','B'))) # Converting a list and a tuple to sets.
{'A', 1, 2, 'B'}
>>> len({1,2,"A","B"}) # Set size.
4
>>> 1 in {1,2,"A","B"} # Tuple containment check.
True
frozenset()
function.
>>> frozenset({1,2,3}) # A frozen set.
frozenset({1, 2, 3})
>>> {frozenset({1,2}), frozenset({3,4})} # Set of frozen sets.
{frozenset({3, 4}), frozenset({1, 2})}
set
data structure must be hashable so that it is easy to deduplicate elements in an unordered set (e.g., {1,1,2,2} == {1,2}
should be True
, and this would take O(n^{2}) steps to compute in the worst case because sets are not ordered). However, values of type set
are not hashable because they can change (e.g., it is possible to insert an element into a set and also to remove an element from a set), which means their hashes could change, as well. Values of type frozenset
cannot be changed; once their hash value is computed at the time of creation, it never changes. Thus, it is okay to include values of type frozenset
inside instances of set
without worrying about incurring a quadratic running time when deduplicating (or, e.g., computing a set union).{}
.list(d.keys())
.list(d.values())
.len()
returns the number of entries in the dictionary.d[key]
).
>>> {"A":1, "B":2} # A dictionary.
{'A': 1, 'B': 2}
>>> list({"A":1, "B":2}.keys()) # Dictionary keys.
['A', 'B']
>>> list({"A":1, "B":2}.values()) # Dictionary values.
[1, 2]
>>> len({"A":1, "B":2}) # Dictionary size.
2
>>> {"A":1, "B":2}["A"] # Obtain a dictionary value using a key.
1
example()
is defined as follows:
def example(x, y, z):
print("Invoked.")
return x + y + z
>>> example(1,2,3)
Invoked.
6
*
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.
>>> args = [1,2,3]
>>> example(*args)
Invoked.
6
**
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.
>>> args = {'z':3, 'x':1, 'y':2}
>>> example(**args)
Invoked.
6
def example(x = 1, y = 2, z = 3):
return x + y + z
>>> example(0, 0)
3
>>> example(0)
5
>>> example()
6
>>> [ x for x in [1,2,3] ]
[1, 2, 3]
>>> [ 2 * x for x in {1,2,3} ]
[2, 4, 6]
>>> [ x + y for x in {1,2,3} for y in (1,2,3) ]
[2, 3, 4, 3, 4, 5, 4, 5, 6]
for
clause. This will filter which combinations are actually used to add a value to the resulting list.
>>> [ x for x in {1,2,3} if x < 3 ]
[1, 2]
>>> [ x + y for x in {1,2,3} for y in (1,2,3) if x > 2 and y > 1 ]
[5, 6]
>>> { x for x in [1,2,3,1,2,3] }
{1, 2, 3}
>>> { key : 2 for key in ["A","B","C"] }
{'A': 2, 'C': 2, 'B': 2}
type()
can be used to determine the type of a value. Below, we provide examples of how to check whether a given expression has one of the common Python types:
>>> type(True) == bool
True
>>> type(123) == int
True
>>> type("ABC") == str
True
>>> type([1,2,3]) == list
True
>>> type(("A",1,{1,2})) == tuple
True
>>> type({1,2,3}) == set
True
>>> type({"A":1, "B":2}) == dict
True
if
, else
, and/or elif
), an iteration construct (i.e., a for
or while
loop), a return
statement, or a break
or continue
statement.
x = 10
(x, y) = (1, 2)
def
keyword, followed by the name of the function or procedure, and then by one or more arguments (delimited by parentheses and separated by commas).
def example(a, b, c):
return a + b + c
else
). The body of each branch is an indented sequence of statements.
def fibonacci(n):
# Computes the nth Fibonacci number.
if n <= 0:
return 0
elif n <= 2:
return 1
else:
return fibonacci(n1) + fibonacci(n2)
if
). The body is executed over and over until the expression in the condition evaluates to False
, or a break
statement is encountered.
def example1(n):
# Takes an integer n and returns the sum of
# the integers from 1 to n1.
i = 0
sum = 0
while i < n:
sum = sum + i
i = i + 1
return sum
def example2(n):
# Takes an integer n and returns the sum of
# the integers from 1 to n1.
i = 0
sum = 0
while True:
sum = sum + i
i = i + 1
if i == n:
break
return sum
def example3(n):
# Takes an integer n and returns the sum of
# the integers from 1 to n1.
sum = 0
for i in range(0,n):
sum = sum + i
return sum
def example4(d):
# Takes a dictionary d that maps keys to
# integers and returns the sum of the integers.
sum = 0
for key in d:
sum = sum + d[key]
return sum