Euclidean-Algorithm

The code provided calculates the greatest common divisor (GCD) of two integers, N1 and N2, with N1>N2.

When the two numbers N1 and N2 are coprime, i.e., their GCD is 1, the code calculates the modular multiplicative inverse of N2 module N1, i.e., it calculates the integer N such that

N2 * N $\equiv$ 1 (mod N1).

Example 1

N1 = 59, N2 = 19

( 1 )	 59 = 0 (mod 59 )
( 2 )	 19 =  19  (mod 59 )
		 2 =  59 - 3 * 19  (mod N1)
( 3 )	 2 =  -3 * 19  (mod N1)
		 1 =  19 - 9 * 2  (mod N1)
( 4 )	 1 =  28 * 19  (mod N1)

The inverse multiplicative of 19 (mod 59) is 28
i.e., 19 * 28 = 1 (mod 59)

Example 2 with large numbers

In August 1977, Rivest, Shamir, and Adleman posed a challenge in Martin Gardner’s Mathematical Games column in Scientific American. Whitin the RSA encrypting algorithm Alice broadcasts her public exponent e and her modulus N where e = 9007 and

N = RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429

RSA-129 has 129 decimal digits (426 bits)

In 1994, a team consisting of Derek Atkins, Michael Graff, Arjen Lenstra, and Paul Leyland succeeded in factoring RSA-129 into

p = 3490529510847650949147849619903898133417764638493387843990820577

and

q = 32769132993266709549961988190834461413177642967992942539798288533.

To find the private key d, we need to compute

e * d $\equiv$ 1 (mod (p-1)*(q-1))

Therefore N1 = (p-1) * (q-1) = 114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432

N2 = e = 9007

( 1 )	 114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432 = 0 (mod 114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432 )
( 2 )	 9007 =  9007  (mod 114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432 )
		 5166 =  114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432 - 12699192379026187151019849003680094594228743945957850845182840335233404323483905554733794354748567282379667762974681874441038 * 9007  (mod N1)
( 3 )	 5166 =  -12699192379026187151019849003680094594228743945957850845182840335233404323483905554733794354748567282379667762974681874441038 * 9007  (mod N1)
		 3841 =  9007 - 1 * 5166  (mod N1)
( 4 )	 3841 =  12699192379026187151019849003680094594228743945957850845182840335233404323483905554733794354748567282379667762974681874441039 * 9007  (mod N1)
		 1325 =  5166 - 1 * 3841  (mod N1)
( 5 )	 1325 =  -25398384758052374302039698007360189188457487891915701690365680670466808646967811109467588709497134564759335525949363748882077 * 9007  (mod N1)
		 1191 =  3841 - 2 * 1325  (mod N1)
( 6 )	 1191 =  63495961895130935755099245018400472971143719729789254225914201676167021617419527773668971773742836411898338814873409372205193 * 9007  (mod N1)
		 134 =  1325 - 1 * 1191  (mod N1)
( 7 )	 134 =  -88894346653183310057138943025760662159601207621704955916279882346633830264387338883136560483239970976657674340822773121087270 * 9007  (mod N1)
		 119 =  1191 - 8 * 134  (mod N1)
( 8 )	 119 =  774650735120597416212210789224485770247953380703428901556153260449237663732518238838761455639662604225159733541455594340903353 * 9007  (mod N1)
		 15 =  134 - 1 * 119  (mod N1)
( 9 )	 15 =  -863545081773780726269349732250246432407554588325133857472433142795871493996905577721898016122902575201817407882278367461990623 * 9007  (mod N1)
		 14 =  119 - 7 * 15  (mod N1)
( 10 )	 14 =  6819466307537062500097658914976210797100835498979365903863185260020338121710857282892047568499980630637881588717404166574837714 * 9007  (mod N1)
		 1 =  15 - 1 * 14  (mod N1)
( 11 )	 1 =  -7683011389310843226367008647226457229508390087304499761335618402816209615707762860613945584622883205839698996599682534036828337 * 9007  (mod N1)

The inverse multiplicative of 9007 (mod 114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432) is 106698614368578024442868771328920154780709906633937862801226224496631063125911774470873340168597462306553968544513277109053606095
i.e., 9007 * 106698614368578024442868771328920154780709906633937862801226224496631063125911774470873340168597462306553968544513277109053606095 = 1 (mod 114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432)

Therefore the private key d is d = 106698614368578024442868771328920154780709906633937862801226224496631063125911774470873340168597462306553968544513277109053606095

Example 3

N1 = 48, N2 = 18

( 1 )	 48 = 0 (mod 48 )
( 2 )	 18 =  18  (mod 48 )
		 12 =  48 - 2 * 18  (mod N1)
( 3 )	 12 =  -2 * 18  (mod N1)
		 6 =  18 - 1 * 12  (mod N1)
( 4 )	 6 =  3 * 18  (mod N1)
		 0 =  12 - 2 * 6  (mod N1)
( 5 )	 0 =  -8 * 18  (mod N1)

The greatest common divisor (GCD) of  48  and  18  is  6

lvillasen / euclidean-algorithm Goto Github PK