University Assignment: ICT101 - Euclidean Algorithm and Cryptography

This report delves into the Euclidean Algorithm, a method for calculating the greatest common divisor (GCD) of two numbers, and its profound impact on modern cryptography. The report begins with an introduction to the algorithm and its historical context, highlighting its significance in the digital world, especially in the realm of secure data transmission and cryptographic systems like RSA and El Gamal. It defines the problem, explaining the GCD and its role in modular arithmetic and encryption/decryption processes. The report explores the algorithm's real-world applications, including simplifying fractions and finding modular inverses, crucial for key generation in cryptographic systems. It provides a detailed explanation of how the algorithm works, including the iterative process for finding the GCD. The report also analyzes the computational efficiency of the algorithm, discussing its time complexity and its place as an effective method for calculating GCD and modular inverses. Finally, it concludes by emphasizing the algorithm's importance in maintaining the security and stability of our online world, supported by references to relevant literature.

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

2DISCRETE MATHEMATICS
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

3DISCRETE MATHEMATICS
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∨theequivalent 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.

4DISCRETE MATHEMATICS
Solution to the problem:
How the inverse is found will be detailed here beginning with how the Euclidean algorithm
works for two numbers. Basically Euclidean Algorithm is a set of instructions for finding out
the g.c.d of two positive integers. It is possible to factorise the numbers and manually
calculate the g.c.d but the process becomes convoluted as the numbers grow bigger in size.
For example, the Euclidean algorithm for finding the gcd of two numbers a and b(a <b ) is as
follows:
If a=bq+ r, such that 0<r<b
Then the Euclidean algorithm states that, G.C.D (a, b) = G.C.D (b, r)
A iteration of this process yields the g.c.d as the number gets smaller and smaller.
Given two integers, x and y, with 0 < y < x, the repeated application of division algorithm
yields a series of division equations, which finally ends with a zero remainder.
x=q1 y +r1, 0 < r1 < y
y=r1 q2+ r2 ,0 < r2 <r1
r1=r2 q3 +r3 ,0 < r3 <r2
……..
r1=r2 q3 +r3 ,0 < r3 <r2
r j−2=r j−1 q j +r j ,0 < r j< r j−1
r j−1=r j q j +1
Here, the g.cd of the positive integers x and y is r j, the final nonzero remainder in the
division process.
The multiplicative inverse algorithm again follows from the Euclidean algorithm:
Rewriting the equations for integers x and y in reverse direction we have:
r1=q1 y−x, 0 < r1 < y
r2 ,=r1 q2− y ,0 < r2 <r1
r3 ,=r2 q3 −r10 < r3 <r2
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
r j−1=r j−3 −r j−2 q j−1

5DISCRETE MATHEMATICS
r j ,=r j−1 q j−r j−20 < r j< r j−1
In this last equation, r j ,=r j−1 q j−r j−2 replacing r j−1 from the earlier equations in terms of
r j−2 and r j−3 and continuing the process yields the final form of the equation:
r j=xm+ yn, where m and n are integers.
When g.c.c (x,y) = 1 the equation reduces to 1=mx+ny.
And 1 ≡mx mod y i.e the multiplicative inverse of x modulo y is n.
Computational Efficiency:
The efficiency of Euclid’s algorithm has been a matter of much study as it is an
integral part of many algorithms with significant impact on real world. Technically, the
efficiency of an algorithm can be denoted by the number of steps used for division required
by the algorithm and multiplying it with the computational expense of each step.
A.A.L Reynauld , did the first study of Euclid’s Algorithm and found that with input
(u,v) the number of division step is bounded by v/2+ 2. Later it was improved by P.J.E Finck
and he proved that the number of division steps is at most 2log2 v +1 . Finck’s analysis was
again refined by the French mathematician, Gabriel Lame, in 1844 and he showed that the
total number of steps needed for running the algorithm was at most five times the number h
of base-10 digits of the smaller number b.
It is seen with current analysis that Euclid's algorithm is in general the most effective
method to compute the g.c.d or the modular inverse of two numbers.
Conclusion:
Thus, it is apparent that as most of our life online depends on secure transmission of data,
methods to transmit these data relies on advanced cryptographical systems. And an integral of
many cryptographic systems involves finding the modular inverses of numbers involved
which can computed efficiently by using Euclidean algorithm. Part of the fascination for the
whole process can be understood by noticing how an ancient algorithm used by a Greek
mathematician is so integral to keeping our enormously complex online world stable.

6DISCRETE MATHEMATICS
References:
Aggarwal, C.C. ed., 2014. Data classification: algorithms and applications. CRC press.
Bennett, C.H. and Brassard, G., 2014. Quantum cryptography: public key distribution and
coin tossing. Theor. Comput. Sci., 560(12), pp.7-11.
Bierbrauer, J., 2016. Introduction to coding theory. Chapman and Hall/CRC.
Bos, J.W., Halderman, J.A., Heninger, N., Moore, J., Naehrig, M. and Wustrow, E., 2014,
March. Elliptic curve cryptography in practice. In International Conference on Financial
Cryptography and Data Security (pp. 157-175). Springer, Berlin, Heidelberg.
Iliev, A. and Kyurkchiev, N., 2018. A Note on Euclidean and Extended Euclidean
Algorithms for Greatest Common Divisor for Polynomials. International Journal of Pure
and Applied Mathematics, 118(3), pp.713-721.
Joshi, M.R. and Karkade, R.A., 2015. Network security with cryptography. International
Journal of Computer Science and Mobile Computing, 4(1), pp.201-204.
Katz, J. and Lindell, Y., 2014. Introduction to modern cryptography. Chapman and
Hall/CRC.
Knopfmacher, J., 2015. Abstract analytic number theory. Courier Dover Publications.
Kraft, J. and Washington, L., 2018. An introduction to number theory with cryptography.
Chapman and Hall/CRC.
Kumar, S.N., 2015. Review on network security and cryptography. International Transaction
of Electrical and Computer Engineers System, 3(1), pp.1-11.
Van Tilborg, H.C. and Jajodia, S. eds., 2014. Encyclopedia of cryptography and security.
Springer Science & Business Media.
Vinogradov, I.M., 2016. Elements of number theory. Courier Dover Publications

7DISCRETE MATHEMATICS

8DISCRETE MATHEMATICS
Introduction: