###### Search By Tags

###### Featured Content:

###### Search by Date

December 2, 2018

January 31, 2018

November 22, 2017

October 9, 2017

*Application of Fermat's Little Theorem*

*Application of Fermat's Little Theorem*

November 22, 2017

URL codes for numerous websites will often begin with the letters “https,” which are used to secure websites on the internet. In more precise terms, the letters “https” literally stand for “hypertext protocol transfer secure.” These letters are used to protect websites and pages through RSA cryptography, a form of encryption to deter security breaches. The security of the website lies within the RSA cryptography, because it is very difficult to continuously factor the large prime integers used in its algorithm. One of the tests often used in RSA cryptography is Fermat’s Little Theorem.

A background on modular mathematics is needed to understand Fermat’s Little Theorem. In simple division, a dividend divided by the divisor will yield the quotient and (sometimes) a remainder. For example, 13÷ 8 =1 r 5, since 8 does not divide through 13 in a number of integers. That equation can be rearranged into 13 mod 8 = 5. However, since Fermat’s Little Theorem deals with the congruence modulo, based off simple modular mathematics, the theorem will instead state that 13 ≡ 37(mod 8). Shown above,13 mod 8 ≡ 5, while 37 mod 8 5. Thus, because the mod of both numbers are 5, the modulo can be called congruent, forming the congruence modulo 13 ≡ 37(mod 8). It can be easily visualized using a clock or a number line. The mod of any number n is {0, n-1}. Likewise, when mod 2 is plotted on a number line, the values for each number alternate between 0 and 1. Thus, when the modulo values for each number are plotted, it can be easily determined that 4 (mod 2) ≡ -2 , since both have a value of 0.

Fermat’s Little Theorem is part of elementary number theory. It states that if p is any prime number p (and cannot divide a), and a is any integer, then a^p ≡ a(mod p) . For example, if p=2, a=3, then 3^2 ≡ 3(mod 2). This also equals 3^2 - 3, which is a multiple of 2. A second and more relevant part of Fermat’s Little Theorem states that a^p-1 ≡ 1(mod p) . An example would be if a=5, p=2, then 5^2-1 ≡ 1(mod2). Or, 5^1-1 is a multiple of 2.

The theorem is most notably used in encryption algorithms, or cryptography, which secures the safety of information during transmissions. One specific case, called private key cryptography, involves a one-way path from the sender to the receiver. In sending encrypted messages through private keys, the sender, A, might integrate Fermat’s Little Theorem into the message for the receiver, B, to decode. The security measure in this RSA cryptography system lies in the difficulty for outside hackers to run multiple prime numbers through the problem, which incorporates Fermat’s theorem in a part of the problem. For the receiver, B, to decode the message, he or she must specifically run the exact number sender A used in building the encryption, since randomly generating number to run through Fermat’s is very time-consuming and inefficient. In fact, research has shown that running 200 numbers would take nearly a thousand years to complete, with a very slim chance that any of those 200 numbers was in fact the correct number. Thus, using Fermat’s Little Theorem or other primality tests often helps deter hackers from attempting to decrypt security codes or messages. Websites encrypt the “https” of an URL with a series of primality tests, like Fermat’s, which contain problems involving the theorem to encrypt the password. Consequently, the likelihood of a cybersecurity breach is significantly diminished. Popular websites like Google will direct users who log into their emails or other accounts to a URL containing “https,” which contains RSA cryptography to secure user information and privatize user searches. While Fermat’s Little Theorem was developed centuries ago, its fundamental basis as a primality test is still practical in building cybersecurity in today’s age of digital technology.

Source: https://blog.flaunt7.com/wp-content/uploads/2017/04/content-https-2x.jpg

About the Author:

Alina Feng, Class of 2019, is from California, USA.