Prime Numbers in Cryptography | Network Security Concepts

[00:00:06]hello everyone welcome back in this presentation we will focus on prime numbers as usual let's start the session with the outcomes upon the completion of the session the learner will be able to outcome number one we will understand about prime numbers and composite numbers outcome number two we will know some facts about prime numbers and outcome number three we will know the role of prime numbers in cryptography why waiting let's directly dive into the topic of the day the prime numbers what is a prime number actually these prime numbers are numbers that has exactly two divisors say if we have a number n then that number n will have exactly two divisors what are all the two divisors if the number n is prime then the divisors are 1 and n only it means if n is a prime number then the prime number n can be divided by 1 and n only it means if the number n is divided by 1 it will give the remainder 0 and if the number n which is divided by n itself then it will give the remainder 0. for other numbers it will not give 0 as the remainder and that's why i told prime numbers has exactly two divisors one is number one and the other one is the number itself and if we talk about any number every number will have prime factors so obviously all numbers have prime factors so if you take any number say 10 so 10 will have prime factors like 2 and 5. if you don't understand this let's see an example say if we have a number 10 then how can we factor this number 10 this 10 can be 1 into 10 or 10 into 1 right so that is by default i am ignoring 1 and that number itself say any number will have factors one and the same number any number you take like two thousand so two thousand divided by one we will get the remainder zero and two thousand when it is divided by two thousand we will get the remainder zero so i am ignoring 1 and the same number itself so what all the other numbers we have say if we have a number 10 this 10 can be 2 power 1 into 5 power 1 right or simply 2 into 5 right so here 2 and 5 are the prime factors can you see here this is prime factorization and the prime numbers involved here are 2 and 5.

[00:02:27]so that's what i told you all numbers have prime factors any number you take obviously 10 is not a prime number why if 10 is divided by only by 1 and 10 only but here this 10 can be divided by 2 as well as 10 can be divided by 5 so 10 has factors such as 1 2 5 and 10. is it having exactly two divisors no here it is having four divisors and that's why 10 is not a prime number but it has prime factors can you see here the prime factors are 2 and 5. let's take another number 11 this 11 can be written as 1 into 11 right do we have any other factors for 11 except 1 and 11 no we don't have any other factors except 1 and 11 so 11 can be written as 1 into 11. what are the factors involved here 1 and 11 right so 1 and 11 so here 11 is a prime number because this number that is this number can be divisible by 1 and the same number itself which is 11.

[00:03:28]let's take another number 100 this 100 can be written as 2 power 2 into 5 power 2. we can write 100 as 10 power 1 into 10 power 1 also it is 10 into 10 but 10 how can we write 10 can be written as 2 into 5 right so ultimately we will have prime factors at the end say for example 100 can be written as 2 power 2 into 5 power 2 so 2 power 2 is what 4 it can also be written as 4 into 25 right 4 into 25 is also 100 only but ultimately at the end if you note there will be only prime numbers what are the prime numbers that are involved here 2 and 5.

[00:04:06]is 100 a prime number no definitely it is not a prime number because it is divisible by 1 it is divisible by 2 4 5 10 20 25 50 and 100 there are multiple divisors and this number 100 is not having exactly two divisors then moving on to 37 37 can be written as 1 power 1 into 37 power 1 or simply 1 into 37 and this 37 cannot be written in other ways and that's why 37 is a prime number because it has only two divisors 1 and 37 and coming to 3 not 8 3 not 8 can be written as 2 power 2 into 7 power 1 into 11 power 1 the prime numbers involved here are 2 7 and 11 right and coming to another number which is 14 688 which can be written as 2 power 5 into 3 power 3 into 17 power 1 where 2 3 17 all these are prime numbers so from this slide what we can understand is any number it will have prime factors and that's what this point says all numbers have prime factors let's see how prime numbers are formally defined so a prime number is a number which is greater than one with only two factors or two divisors what are these two devices one is itself and the other one is one and it cannot be divided further by any other number without leaving a remainder i hope this point is clear for you let's see some examples now here 2 is a prime number 3 is a prime number 5 is a prime number 7 is a prime number 9 is not a prime number i'll tell you why 9 is not a prime number when a number is not a prime number then that number will be a composite number so 9 is not a prime number so it is a composite number and 33 is a composite number let's start with 2 2 is a prime number because 2 can be divided by 1 and 2 can be divided by 2 so a number is said to be a prime number if it is divided by 1 and it is also divided by the same number only on these two occasions we'll get the remainder as 0 so the divisors of 2 are 1 and 2 as per the formal definition of prime numbers we have exactly 2 divisors so 2 is a prime number similarly 3 is also a prime number because 3 can be divisible by 1 and 3 can be divisible by 3 only so the divisors for 3 are 1 and 3 so we can confirm that 3 is also a prime number coming to 5 so 5 is also a prime number because 5 can be divided by 1 and 5 only and there are no other factors coming to 7 7 is also a prime number 9 is not a prime number because 9 can be divided by 1 9 can be divided by 3 and 9 can be divided by 9. are we having exactly 2 divisors no we have 3 divisors so obviously 9 is not a prime number so we refer 9 as a composite number and finally 33 is not a prime number because it has factors such as 1 3 11 and 33 since we have 4 factors obviously 33 is not a prime number i hope prime numbers are clear now the important question is why we are dealing this prime number and mainly why we are dealing this prime number in cryptography before answering this question let's see some facts about prime numbers actually 2 is the only even prime number if you note here all prime numbers are odd in nature and 2 is the smallest prime number as well so you may be asking is one a prime number no 1 is not a prime number now another interesting fact is that except for 2 and 5 all prime numbers end in the digit 1 3 7 or 9 so mostly the prime numbers will be ending with 1 3 7 or 9 but if a number is ending with 2 or 5 obviously that number will not be a prime number why because when a number ends with 2 obviously it can be divided by 2 right at the same time when a number ends with 5 that can also be divided by 5. so obviously a number which is ending with 2 or 5 it cannot be a prime number let's now focus on why prime numbers are important in cryptography actually many encryption algorithms are based on prime numbers only you may be asking why prime numbers are having more significance in cryptography the reason is generally multiplying two large prime numbers can be very fast so this is one of the reasons for having a prime numbers so if you are given with two prime numbers then you can multiply these two prime numbers very fast but it is extremely difficult to do the reverse it means it is extremely computer intensive to do the reverse if a big or a large number is given and finding the prime factors of that large number will be a tough job so that is factoring very large prime numbers is very hard very hard means it may not be possible or computers take a long time to do the processing and that's where the real security relies in a nutshell let's take x and y are two prime numbers and we are getting the product of these two prime numbers x y as n for example multiplying x and y to generate n is easy in case if you are given with n and you want to find x and y that is extremely difficult our computer takes longer time to do that calculation and that's one of the reasons for having prime numbers in cryptography before we conclude let's see are they prime numbers is 5393 a prime number maybe this one or this one is this a prime number or finally is this a prime number so cryptographic algorithms or encryption algorithms uses large prime numbers only anyway don't worry about this now in order to find whether these numbers are prime numbers or not we have some algorithms to do that anyway i will talk about that while dealing with the topic testing for primality and that's it guys i hope now you understood about prime numbers and composite numbers we have seen some facts about prime numbers and we understood the role of prime numbers in cryptography i hope you guys enjoyed this presentation and thank you for watching [Music] [Applause] [Music] you