Two of the skills a cryptographer must master are:
Knowing his way and being comfortable to work with numbers.
Understanding and manipulating abstract objects.
This chapter of fundamentals proposes to prepare you for understanding the basics of number theory and abstract algebra .We will start with the most basic concepts such as division and build up knowledge until you, future cryptographer, are able to follow and understand the proofs and intricacies of the cryptosystems that make our everyday life secure.
We will provide examples and snippets of code and be sure to play with them. If math is not your strongest suit, we highly suggest to pause and ponder for each concept and take it slow.
For the math-savy people we cover advanced topics in specific chapters on the subjects of number theory and group theory.
So what are we waiting for? Let's jump right in!
Let be the set denoting the integers.
Definition - Divisibility
For we say that divides if there is some such that
For we have because we can find such that .
Example: Let and
and . We can find such that
if and then
Definition - Division with remainder
Let with ,
There exists unique such that and
is called the quotient and the remainder
To find python offers us the
divmod() function that takes as arguments
q, r = divmod(6, 2)print(q, r)# 3 0q, r = divmod(13, 5)print(q, r)# 2 3# Note that 13 = 2 * 5 + 3
If we want to find only the quotient we can use the
If we want to find the remainder we can use the modulo
q = 13 // 5print(q)# 2r = 13 % 5print(r)# 3
Now it's your turn! Play with the proprieties of the division in Python and see if they hold.
Let be 2 integers. The greatest common divisor is the largest integer such that and
# In python we can import math to get the GCD algoimport mathprint(math.gcd(18, 12)) # -> 6# Sage has it already!print(gcd(18, 12)) # -> 6
for all other common divisors of we have
What can we say about numbers with ? How are their divisors?