﻿ Trapdoor Functions
HOME Mathematics Computer Science
Trapdoor Functions
Prerequisites
Show All
Hide All
Sets
Show/Hide
﻿
Introduction
• A set is a collection of elements, such as:
• A = {1, 2, 3, 4, 5}
• A set does not have order:
• {1, 2, 3, 4, 5} is the same as {5, 4, 3, 2, 1}
• It is convenient to write the elements of a set in consecutive order, but this is only for convenience.
• Every element in a set is unique, multiples of the same element are ignored:
• The set {1, 2, 2} has a size of 2, and is the same as {1, 2}
Notation
• It is common for sets to be denoted by a uppercase letter, and for its elements to be wrapped in curly braces:k

LaTeX: \mathbf{A} = \{ 1, 2, 3, 4, 5 \}
• Sets can also be defined using set builder notation:
• A rule is used to show which elements are members of the set:
• The set A defined above would contain all even integers between 0 and 2000.
• The format of the rule is: (formula: conditions) or (formula| conditions).
• If it is not specified as a condition, then it is assumed that a is a real number.
Elements in a set
• Elements in a set are usually represented by a lowercase letter.
• To demonstrate that an element is part of a set, we use the set membership symbol:

LaTeX: \mathbf{a} \in \mathbf{A}
• This can also be done with proper elements:

LaTeX: \1 \in \{ 1, 2, 3, 4, 5 \}
• To show that an element is not part of a set, we use the 'not member of' symbol:

LaTeX: 6 \notin \{ 1, 2, 3, 4, 5 \}
The Empty Set

The Empty Set (or Null Set) is a set containing no items. It is represented by the empty set symbol:

LaTeX: \varnothing = \{\}
Code
A = frozenset([1, 2, 3, 4, 5])

print(1 in A) # prints 'True'
print(6 not in A) # prints 'True'

Ordered Pairs
Show/Hide
﻿
Introduction
• An ordered pair is simply a pair of objects, e.g. (a, b)
• In an ordered pair, the order matters:
LaTeX:
(\mathbf{a}, \mathbf{b})\neq (\mathbf{b}, \mathbf{a})
\text{ unless }
\mathbf{a} = \mathbf{b}

• This contrasts with the unordered pair, in which (a, b) = (b, a) regardless of the values of a and b.
• An ordered pair is not a type of set. An ordered pair may contain duplicate elements, and its order is important.
Notation
Ordered Pairs are represented by a comma separated pair of elements wrapped in brackets:
a = (1, 2)
LaTeX: \mathbf{a} = (1, 2)
Code
a = (1, 2)
print(a)

Functions
Show/Hide
﻿
Introduction
• A function is mapping between two sets:
• The first set (denoted by X) is called the domain.
• The second set (denoted by Y) is called the codomain.
• Each mapping can be represented as an ordered pair, e.g. (a, 1). The set of all ordered pairs for the entire function is called the graph of the function, and is given the name G.
• For each element x in X, there exists a unique y in Y.
• X is called the 'argument', 'input', or 'preimage'
• y is called the 'value', 'ouput', or 'image'
• In the above example, not all elements of Y were mapped to from X. The subset of Y that has mappings from X is called the range.
• This is also called the image of the function, and is denoted:
Functional Notation
• One common way to denote functions is using the functional notation.

LaTeX: \mathbf{y} = f(\mathbf{x})
• This is pronounced 'F of X'
• It is commonly used in areas of Mathematics which do not have a basis in set theory (such as calculus).
Arrow Notation
• Another way to denote functions is using arrow notation.

LaTeX: f\colon \mathbf{X} \to \mathbf Y
• This is pronounced 'the function f from set X to set Y.
• It is commonly used in areas of Mathematics which have a basis in set theory.
Code
def f(x):
graph = {
'a': 1,
'b': 3,
'c': 1
}

return graph.get(x)

y = f('a')
print(y)

Injections, Surjections, and Bijections
Show/Hide
﻿
Introduction
• Functions can be classified by how they map elements between the domain and codomain.
• Three types of mappings are:
• Injective
• Surjective
• Bijective
Injective Mapping
• An injective mapping is when each element in the codomain is mapped to by at most one element from the domain.
• Another way of saying this is that no two elements in the domain map to the same element in the codomain.
• Example of an injective mapping:
• This type of mapping is also called 'one-to-one'.
Surjective Mapping
• A surjective mapping is when each element in the codomain is mapped to by at least one element from the domain.
• Another way of saying this is that the codomain and image (range) of the function are the same.
• Example of a surjective mapping:
• This type of mapping is also called 'onto'.
Bijective Mapping
• A bijective mapping is when the mapping is both injective and surjective.
• Another way of saying this is that each element in the codomain is mapped to by exactly one element in the domain.
• Example of a bijective mapping:
• This type of mapping is also called a 'one-to-one correspondence'.
Inverse Functions
Show/Hide
﻿
Introduction
• If f is a function, then its inverse function g is defined as the reverse of the mapping created by f.
• If g is an inverse of f then:
• and:
Example
• To find the inverse of a function given as an equation, we can simply solve for y
Notation
To denote that a function is an inverse of another, two different notations are commonly used:
• If the function is representedby the letter f then its inverse is can be denoted using a superscript of -1

LaTeX: f^{-1}(x)
• If the function is represented by the letter f then its inverse is can be denoted using the letter g

LaTeX: g(x)
Properties
• If the original function is a bijection then its inverse will also be a bijection.
• If the original function is not a bijection then there is no guarantee that it has an inverse.
• If it is not injective then there may be two elements in the domain that map to the same element in the codomain.
• If it is not surjective then there may be an element in the codomain that is not mapped to from the domain.
One-way Functions
Show/Hide
﻿
Introduction
• One way functions are a special subset of functions in which it is easy to compute y given x but very hard to compute x given y
• For example:

LaTeX: f(x) = 7^x \mod 23
We can calculate values for f(x) very easily:
However given a specific value for y it is difficult to find a corresponding x without computing each possible value of x and seeing if it results in a matching y.
Code
Notice in the code below, the function f() has a much smaller complexity than function g()
def f(_x):
return 7**_x % 23

def g(_y):
for i in range(10*1000):
if f(i) == _y:
return i

raise Exception("x is not in testable domain")

x = 8
y = f(x)
print("The image of " + str(x) + " is " + str(y))  # prints The image of 8 is 12

y = 12
x = g(y)

print("The preimage of " + str(y) + " is " + str(x))  # prints The preimage of 12 is 8

Important Sets
Show/Hide
﻿
Introduction
• Some sets are used so often in mathematics that they are given their own names.
• Z: The set of all integers.
• R: The set of all real numbers.
Integers
• The set of all integers contains all the whole numbers, including negative numbers and 0.
• It is represented by an uppercase bold (or blackboard bold) Z:

LaTeX: \mathbb{Z} = \{ ..., -3, -2, -1, 0, 1, 2, 3, ... \}
Code
i = 1
print(type(i))  # prints <class 'int'>

Real Numbers
• The set of all real numbers contains every number that is not imaginary. This includes:
• Integers: e.g. 0, 1, 2
• Rational Numbers: Those which can be represented as a fraction, e.g. 0.5, 1.1
• Irrational Numbers: Those which cannot be represented by a fraction, e.g.
• It is represented by an uppercase bold (or blackboard bold) R:

LaTeX: \mathbb{R} = \{ -1, 1.4, \pi \}
Code
Unfortunately we cannot represent irrational numbers using code. Instead we can approximate them as floating point numbers:
r = 1.41421356237
print(type(r))  # prints <class 'float'>

Sets of Ordered Pairs
Show/Hide
﻿
Introduction
• We have special symbols denoting the set of all integers and the set of all real numbers: Z and R respectively.
• These can be modified to denote the set of all ordered pairs:
• Z2 denotes the set of all ordered pairs of integers.
• R2 denotes the set of all ordered pairs of real numbers.
The set of all ordered pairs of integers
• Z2 contains every possible pair of integers, e.g.
• We can define Z2 in terms of Z using set builder notation:

LaTeX: \mathbb{Z}^2 = \{ (z_1, z_2)\colon z_1, z_2 \in \mathbb{Z} \}
The set of all ordered pairs of real numbers
• R2 contains every possible pair of real numbers, e.g.
• We can define R2 in terms of R using set builder notation:

LaTeX: \mathbb{R}^2 = \{ (r_1, r_2)\colon r_1, r_2 \in \mathbb{R} \}
Higher dimensions
• R and Z can also be extended to higher dimensions:
• To represent the set of all triplets of integers, you can use a superscript of 3:

Trapdoor Functions
﻿
Introduction
• Trapdoor functions are very similiar to one-way functions in that their inverse is computationally infeasible.
• However they have an additional property such that they contain a trapdoor.
• A trapdoor is an extra piece of information which makes it easy to invert the function.
Example
• A common one-way function is semi-prime factorization:
• Given x1 and x2 it is easy to find y (you can just multiply them together).
• However given only y, it becomes computationally infeasible to find x1 and x2, especially if they are very large.
• The trapdoor in this function is when you know one of the values of X. For example: if you know that x1 is always equal to 23:
Code
def f(_x1, _x2):
return _x1 * _x2

def g(_y, _x1):
return _x1, _y // x1

x1, x2 = 7, 13

y = f(x1, x2)
print("The image of " + str((x1, x2)) + " is " + str(y))  # prints: The image of (7, 13) is 91

x1 = 7
y = 91

x1, x2 = g(y, x1)
print("The preimage of " + str(y) + " is " + str((x1, x2)))  # prints: The preimage of 91 is (7, 13)