Discrete Mathematics Report 2022

Running head: DISCRETE MATHEMATICS
Discrete Mathematics
Name of the Student:
Name of University:

DISCRETE MATHEMATICS2
Table of Contents
Introduction:...............................................................................................................................3
Problem Definition:....................................................................................................................3
Real World Application of Euclidean Algorithm:.....................................................................3
Solution to the problem:.............................................................................................................4
Computational Efficiency:.........................................................................................................5
Conclusion:................................................................................................................................5
References:.................................................................................................................................6

DISCRETE MATHEMATICS3
Introduction:
The modern world functions a lot online. In fact, there are dystopian films made
exploring what might happen if the stable complex world we have built online
collapses. Euclidean Algorithm finds its uses in many surprising disciplines but
perhaps the most impact is felt in its use in cryptography. For example, The RSA
is one of the earliest public key cryptosystems that has been widely used for safe
data transmission. RSA works by letting the encryption key public but the
decryption key is kept as a secret. This involves calculating the modular inverse
which is done by the Euclidean algorithm. In El Gamal, finding modular inverse
using Euclidean algorithm is used as a step in decryption.
Problem Definition:
The RSA algorithm was invented to safe transaction online and in this report we
will explore one of the many algorithms that makes it work. Euclidean Algorithm
is a method used for calculating the greatest common divisor of two numbers.
Abbreviated as G.C.D it is the biggest number that divides both of the numbers
without leaving any remainder. The Greek mathematician, Euclid, first described
it in his classic book Elements. Anytime information needs to be securely shared
over the internet, roughly speaking, the method involves sending the information
with an encryption key that is publicly available but can only be accessed by the
receiver who knows how the decryption works.
Real World Application of Euclidean Algorithm:
Euclidean Algorithm has many practical and theoretical applications being one of the
foundations of mathematics. It can be used for simplifying fractions to their lowest forms,
solving Diophantine equations, constructing continued fractions and many important
applications in number theory such proving the Lagrange four square theorem or proving that
the factorization of the primes are unique.
An important use of Euclidean algorithm is for finding modular inverses. A modification of
the algorithm makes it possible, given two integers a,n to calculate integers x , y such that
ax + yn=g . c . d (a , n). In case g.c.d (a,n)=1 , this will enable us to find integers so that,
ax + yn=1 i.e ax ≡1 mod n. Therefore with the Euclidean algorithm it is possible to find the
inverse of a modulo n.
A part of RSA involves solving the congruence equation
ax ≡1 mod n∨the equivalent linear diophantine equation ax +ny=1.
In fact, many cryptography systems need finding modular inverses as a foundation to do
further computations. In RSA we mainly need to find a modular inverse as a key generation.
In this report it will be explored how the algorithm works by taking a few examples.