Decoding the Role of Number Theory in Cryptography
Number Theory
Number theory
Number Theory plays an important role in encryption algorithm. Cryptography is the practice of hiding information, converting some secret information to not readable texts. The paper aims to introduce the reader to applications of Number Theory in cryptography. We will briefly talk about an idea of encryption in Caesar ciphering and RSA public key cryptography. Many tools in Number Theory like primes, divisors, congruencies and Euler’s ‘’ function are used in cryptography for security.
INTRODUCTION
For thousands of years people have searched for the way to send a message secretly. There is a story that, in ancient time, a king needed to send a secret message to his general in battle. The king took a servant, shaved his head and wrote the message on his head. He waited for the servant’s hair to grow back and then sent the servant to the general. The general then shaved the servant’s head and read the message. If the enemy had captured the servant, they presumably would not have known to shave his head and message would have been safe. Cryptography is the study of methods to send and receive the secret messages. In general we have a sender who is trying to send a message to receiver. There is also an adversary, who wants to steal the message. We are successful if sender is able to communicate a message to the receiver without adversary learning what the message was.
Number theory, as the name indicates, is a theory that focuses on numbers. The notion of number and arithmetic first appeared about 3,000 years ago. In the early time, the word for number theory was arithmetic, which was replaced by “number theory” in the early twentieth century. Mathematicians study number theory.
Many science and engineering fields are built on the basis of mathematics, which is built on number theory. Number theory is concerned largely with the nature of integers. Number theory problems are brief, and the key to answering them is unique factor decomposition. Furthermore, in reconstructing the unique factorization, several new notions, such as complex integers, ideal numbers, and ideals, are introduced, which also give benefits.
Important concepts in Number Theory
Prime Numbers- A positive integer p is said to be a prime if it has only two factors namely 1 and p itself.
For Example: Primes are 2, 3, 5, 7, 11, 13, 17 …
Divisors: A positive integer a is said to divide an integer b if there exist an integer
c such that b a.c and written as a | b .
For Example
2 |10 as 10 = 2.5 but 3 do not divide 10 as there does not exist any integer c
such that 10 = 3. c
Greatest Common Divisor: Let a and b be two positive integers then an integer d is called greatest common divisor of a and b if d | a and d | b i.e. d is common divisor of a and b . And if any integer c is such that c | a and c | b then c | d i.e. any other common divisor of a and b will divide d it is denoted by d (a,b) For Example: 6 (24,30)
Two numbers a and b are said to relatively prime or co prime if their greatest common divisor is 1 i.e. (a,b) 1 For Example: 10 and 11 are co prime
Congruence: Let a and b be two integers and m is any positive integer then a is said to congruent to b modulo m if m divide difference of a and b i.e m| a b. It is denoted by
a b(modm)For Example:
27 13(mod 4)
Euler’s ‘’ Function : An arithmetic function Euler’s Toitent function ‘’ is defined as n = number of positive integers less than or equal to n and co prime to n i.e. n = number of positive integers ‘ a ’ such that 1 a n and g.c.d. a,n 1
For Example: 15 8 as primes relative to 15 are given by 1, 2, 4, 7, 8, 11, 13, and 14. And
(mn) (m)(n) where m and n are relatively prime.
Some simple properties of congruence are given below:
(1) a b(modm) iff b a(mod m)
(2) a b c (modm) iff a c b(modm)
(3) (mod ) a1 b1 m and (mod ) a2 b2 m then (mod ) a1 a2 b1 b2 m
(4) a b(modm) and c is any integer then ca cb(modm)
(5) a mk a(modm) where k is any integer
The Subdivisions of Number Theory
- Elementary number theory :- Elementary number theory is a branch of number theory based on elementary method. In essence, it applies divisible property to mainly study divisible theory and congruence theory. The typical conclusions in this theory include the familiar congruence theorem, Euler’s theorem, Chinese residual theorem and so on.
2. Analytic number theory :- Analytic number theory studies the integers with calculus and complex analysis. Some analytic functions, such as the Riemann function ζ which studies the properties of integers and primes, can also be employed to understand number theory.
3. Algebraic number theory :- Algebraic number theory is more inclined to study the nature of various rings of integers from the perspective of algebraic structure.
4.Geometric number theory :- Geometric number theory studies the distribution of the integers from the perspective of geometry.
Other Applications of Number Theory!
Computer Animation:- Linear transformation is usually used to make images, and computer graphics are to build graphics on display devices through algorithms and programs, so linear transformation technology can be used to make computer animation. Computer graphics mainly consist of image representation, storage and computation. With the improvement of software capabilities, linear transformation technology is commonly used in computer animation.
Machine Translation :- The main algorithm of machine translation is based on the statistical method, with the accuracy of 90%. In addition, this algorithm is also used in image search technology. The core of this method is that the language units of source language and target language can be represented by vectors, and the lexical vectors of different languages can be projected onto a two-dimensional plan for analysis. Experimental results show that the lexical vectors of different languages do have some relations similar to linear relations, so it is of significance to classify machine translation as a linear transformation.
Other Basic Fields Number theory also plays a surprising role in other theories. In quantum theory, Hermite operator is one of the most basic concepts. Apart from that, number theory is also widely used in non-mathematical disciplines, such as information science, theoretical physics, quantum chemistry, and so on.
Conclusion:-
Cryptography has been in practice for thousands of years, and many different ciphers and cryptosystems have been used throughout history. These ciphers and cryptosystems have also evolved over time, from primitive and insecure methods to those which employ advanced mathematics to secure information. Number theory is one of the more important mathematical fields that has influenced the evolution of cryptography. The early ciphers, like the shift and Vigenere cipher, were ` created and used without the knowledge that number theory was present in both of their encryption and decryption processes. However, number theory is used extensively in modern day public key cryptosystems like the RSA and ElGamal systems. While these cryptosystems are significantly more secure than their symmetric key predecessors, technology’s continual advancements will eventually make these cryptosystems insecure and obsolete. This is why the exploration of the history, evolution, and mathematical concepts behind cryptography is so important.
Authors:-
Aditya Dere
Anushka Ahire
Mandar Ambulkar
Daksh Dagariya
Anurag Saraf
References
1.“Applications of Number Theory in Cryptography .” Science and Its Times: Understanding the Social Significance of Scientific Discovery. . Encyclopedia.com. 10 Jun. 2022 <https://www.encyclopedia.com>.
2. https://www.kaspersky.com/resource-center/definitions/what-is-cryptography
3.https://science.jrank.org/pages/4775/Number-Theory-Current-applications.html
