Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Prime Numbers and Prime Factorisation are essential concepts in cryptography. They are related to the idea of dividing numbers into smaller parts called factors. To understand these concepts better, we need to learn some basic terms and definitions. Let’s start with natural numbers.
What are natural numbers?
Natural numbers are the numbers that we use to count things in our everyday life. They start from 1 and go on forever: 1, 2, 3, 4, 5, 6, … and so on. We can write them using the symbol ∞ (infinity) to show that there is no end to them: {1, 2, 3, … ∞}.
Why are natural numbers called natural numbers?
The name natural numbers comes from our natural tendency to count things using these numbers. For example, we can say that we have 1 book, 2 pens, or 5 trees. That’s why sometimes natural numbers are also called counting numbers. Natural things are always positive, so natural numbers do not include negative numbers or zero.
Any number can be divided into its factors. So our next question is:
What are factors?
Factors are the numbers that we multiply together to get another number. For example, if we multiply 5 and 8, we get 40. So we can say that 5 and 8 are factors of 40. We can write this using the symbol x (times) like this: 5 x 8 = 40.
One way to find the factors of a number is to use trial division, which means dividing the number by smaller numbers until we get a remainder of zero. For example, to find the factors of 40, we can do:
40 / 2 = 20 (no remainder)
40 / 4 = 10 (no remainder)
40 / 5 = 8 (no remainder)
40 / 8 = 5 (no remainder)
40 /10 =4 (no remainder)
40 /20 =2 (no remainder)
40 /40 =1 (no remainder)
So the factors of 40 are: 1, 2, 4, 5, 8,10 ,20 , and 40.
We can see that some factors of a number can be divided further into smaller factors. For example, we can divide 4 into 2 and 2. These smaller factors are called prime factors.
What are prime factors?
Prime factors are the factors of a number that are prime numbers. Prime numbers are the numbers that have only two factors: one and themselves. For example, 2 is a prime number because it has only two factors: one and two. We can write this like this:
2 =1 x2
Some other prime numbers are:
3 =1 x3
5 =1 x5
7 =1 x7
11=1 x11
13=1 x13
17=1 x17
19=1 x19
and so on.
We can use a special symbol called π (pi) to show how many prime numbers there are up to a certain number. For example,
π(10) =4
means that there are four prime numbers up to ten:
2 ,3 ,5 ,and7
We can also use a special symbol called Ω (omega) to show how many prime factors a number has. For example,
Ω(12) =3
means that there are three prime factors of twelve:
12=2 x2 x3
What are composite numbers?
Composite numbers are the numbers that have more than two factors. They are not prime numbers because they can be divided further into smaller factors. For example,
4 =1 x4
4 =2 x2
So four is a composite number because it has more than two factors: one ,two ,and four.
Some other composite numbers are:
6 =1 x6
6 =2 x3
8 =1 x8
8 =2 x4
8 =2 x2 x2
9 =1 x9
9 =3 x3
10=1 x10
10=2 x5
and so on.
We can use a special symbol called σ (sigma) to show how many factors a number has. For example,
σ(12) =6
means that there are six factors of twelve:
1 ,2 ,3 ,4 ,6 ,and12
Prime numbers are the basic building blocks of any composite number. We can write any composite number as a product of prime numbers. This is called prime factorization.
What is prime factorization?
Prime factorization is the process of writing a composite number as a product of prime numbers. For example,
12=2 x2 x3
This means that twelve is equal to two times two times three.
We can also write the prime factorization using exponents to show how many times a prime number is repeated. For example,
12=22×3
This means that twelve is equal to two squared times three.
We can also write the prime factorization using a special symbol called ∏ (product) to show the multiplication of all the prime factors. For example,
12=∏(22×3)
This means that twelve is equal to the product of two squared and three.
Note:
- A number has only one prime factorization.
- No two numbers have the same prime factorization.
- One is not a prime or composite number because it has only one factor.
I hope this story helps you understand what prime numbers and prime factorization are and why they are important for cryptography.