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) 
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 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 
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, ...} 
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 
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')}) 
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'}
:
 = 

 = 

 = 

 ∈ 
 
 ∈ 

 = 
 
 = 
 
 = 

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

 = 
 
 = 
 
 = 
 
 ≡ 

 = 
 
 = 
 
 = 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

  
 
 = 
 
 ≡ 
 
 ≡ 

 = 
 
 = 
 
 = 
 
 ∈ 
 
  

  
 
 ∈ 
 
 = 
 
 = 
 
 = 
 
 = 


 ≡ 
 
  
 
  
 
 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 ∤ 
 
 ≢ 
 
 ∤ 
 
 ≢ 

 ≡ 
 
 ≡ 
 
 = 
 
 = 
 
  

  
 
 = 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 

 ≡ 
 
 ≡ 
 
 ≡ 

 ≡ 

 ≡ 

 ≡ 

 = 

 = 
 
= 

 ≠ 
 
 = 

 = 
 
 = 
 
 = 
 
  

 = 

 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 
 
 ≡ 

 = 
 
 = 
 
 = 

 = 
 
 = 
 
 = 

 = 

 = 

 = 

 = 
 
 = 

 = 
 
 = 
 
 = 
 
= 
 
= 
 
= 


 ≢ 
 
 ≢ 

 ≡ 

 ≡ 

 = 
 
 = 
 
 = 
 
 = 
 
 = 

 < 

 ≤ 
 
 ≤ 

 > 

 = 
 
 = 
 


 = 
 
= 
 
= 
 
≈ 

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
:
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 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.[
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.