Euklidiska algoritmer (grundläggande och utökade)
Den euklidiska algoritmen är ett sätt att hitta den största gemensamma delaren av två positiva heltal. GCD av två tal är det största talet som delar dem båda. Ett enkelt sätt att hitta GCD är att faktorisera båda talen och multiplicera vanliga primtalsfaktorer.
Grundläggande euklidisk algoritm för GCD:
Algoritmen är baserad på nedanstående fakta.
- Om vi subtraherar ett mindre tal från ett större (vi minskar ett större tal), ändras inte GCD. Så om vi fortsätter att subtrahera upprepade gånger den största av två, slutar vi med GCD.
- Nu istället för subtraktion, om vi dividerar det mindre talet, stannar algoritmen när vi hittar resten 0.
Nedan finns en rekursiv funktion för att utvärdera gcd med Euklids algoritm:
C
// C program to demonstrate Basic Euclidean Algorithm> #include> // Function to return gcd of a and b> int> gcd(> int> a,> int> b)> {> > if> (a == 0)> > return> b;> > return> gcd(b % a, a);> }> // Driver code> int> main()> {> > int> a = 10, b = 15;> > > // Function call> > printf> (> 'GCD(%d, %d) = %d
'> , a, b, gcd(a, b));> > a = 35, b = 10;> > printf> (> 'GCD(%d, %d) = %d
'> , a, b, gcd(a, b));> > a = 31, b = 2;> > printf> (> 'GCD(%d, %d) = %d
'> , a, b, gcd(a, b));> > return> 0;> }> |
CPP
// C++ program to demonstrate> // Basic Euclidean Algorithm> #include> using> namespace> std;> // Function to return> // gcd of a and b> int> gcd(> int> a,> int> b)> {> > if> (a == 0)> > return> b;> > return> gcd(b % a, a);> }> // Driver Code> int> main()> {> > int> a = 10, b = 15;> > > // Function call> > cout < <> 'GCD('> < < a < <> ', '> < < b < <> ') = '> < < gcd(a, b)> > < < endl;> > a = 35, b = 10;> > cout < <> 'GCD('> < < a < <> ', '> < < b < <> ') = '> < < gcd(a, b)> > < < endl;> > a = 31, b = 2;> > cout < <> 'GCD('> < < a < <> ', '> < < b < <> ') = '> < < gcd(a, b)> > < < endl;> > return> 0;> }> |
Java
// Java program to demonstrate Basic Euclidean Algorithm> import> java.lang.*;> import> java.util.*;> class> GFG {> > // extended Euclidean Algorithm> > public> static> int> gcd(> int> a,> int> b)> > {> > if> (a ==> 0> )> > return> b;> > return> gcd(b % a, a);> > }> > // Driver code> > public> static> void> main(String[] args)> > {> > int> a => 10> , b => 15> , g;> > > // Function call> > g = gcd(a, b);> > System.out.println(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > a => 35> ;> > b => 10> ;> > g = gcd(a, b);> > System.out.println(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > a => 31> ;> > b => 2> ;> > g = gcd(a, b);> > System.out.println(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > }> }> // Code Contributed by Mohit Gupta_OMG> |
Python3
# Python3 program to demonstrate Basic Euclidean Algorithm> # Function to return gcd of a and b> def> gcd(a, b):> > if> a> => => 0> :> > return> b> > return> gcd(b> %> a, a)> # Driver code> if> __name__> => => '__main__'> :> > a> => 10> > b> => 15> > print> (> 'gcd('> , a,> ','> , b,> ') = '> , gcd(a, b))> > a> => 35> > b> => 10> > print> (> 'gcd('> , a,> ','> , b,> ') = '> , gcd(a, b))> > a> => 31> > b> => 2> > print> (> 'gcd('> , a,> ','> , b,> ') = '> , gcd(a, b))> # Code Contributed By Mohit Gupta_OMG> |
C#
// C# program to demonstrate Basic Euclidean Algorithm> using> System;> class> GFG {> > public> static> int> gcd(> int> a,> int> b)> > {> > if> (a == 0)> > return> b;> > return> gcd(b % a, a);> > }> > // Driver Code> > static> public> void> Main()> > {> > int> a = 10, b = 15, g;> > g = gcd(a, b);> > Console.WriteLine(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > a = 35;> > b = 10;> > g = gcd(a, b);> > Console.WriteLine(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > a = 31;> > b = 2;> > g = gcd(a, b);> > Console.WriteLine(> 'GCD('> + a +> ' , '> + b> > +> ') = '> + g);> > }> }> // This code is contributed by ajit> |
PHP
// php program to demonstrate Basic Euclidean Algorithm> // PHP program to demonstrate // Basic Euclidean Algorithm // Function to return // gcd of a and b function gcd($a, $b) { if ($a == 0) return $b; return gcd($b % $a, $a); } // Driver Code $a = 10; $b = 15; // Function call echo 'GCD(',$a,',' , $b,') = ', gcd($a, $b); echo '
'; $a = 35; $b = 10; echo 'GCD(',$a ,',',$b,') = ', gcd($a, $b); echo '
'; $a = 31; $b = 2; echo 'GCD(',$a ,',', $b,') = ', gcd($a, $b); // This code is contributed by m_kit ?>> |
Javascript
// JavaScript program to demonstrate> // Basic Euclidean Algorithm> // Function to return> // gcd of a and b> function> gcd( a, b)> {> > if> (a == 0)> > return> b;> > return> gcd(b % a, a);> }> // Driver Code> > let a = 10, b = 15;> > document.write(> 'GCD('> + a +> ', '> > + b +> ') = '> + gcd(a, b) +> ' '> );> > > a = 35, b = 10;> > document.write(> 'GCD('> + a +> ', '> > + b +> ') = '> + gcd(a, b) +> ' '> );> > > a = 31, b = 2;> > document.write(> 'GCD('> + a +> ', '> > + b +> ') = '> + gcd(a, b) +> ' '> );> // This code contributed by aashish1995> |
Produktion
GCD(10, 15) = 5 GCD(35, 10) = 5 GCD(31, 2) = 1
Tidskomplexitet: O(Logg min(a, b))
Hjälputrymme: O(Logg (min(a,b))
Utökad euklidisk algoritm:
Utökad euklidisk algoritm hittar också heltalskoefficienter x och y så att: ax + by = gcd(a, b)
Exempel:
Inmatning: a = 30, b = 20
Produktion: gcd = 10, x = 1, y = -1
(Observera att 30*1 + 20*(-1) = 10)Inmatning: a = 35, b = 15
Produktion: gcd = 5, x = 1, y = -2
(Observera att 35*1 + 15*(-2) = 5)
Den utökade euklidiska algoritmen uppdaterar resultaten av gcd(a, b) med hjälp av resultaten som beräknats av det rekursiva anropet gcd(b%a, a). Låt värdena på x och y beräknade av det rekursiva anropet vara x 1 och y 1 . x och y uppdateras med nedanstående uttryck.
Rekommenderad övning Utökad euklidisk algoritm Prova det!axe + by = gcd(a, b)
gcd(a, b) = gcd(b%a, a)
gcd(b%a, a) = (b%a)x 1 + är 1
ax + by = (b%a)x 1 + är 1
axe + by = (b – [b/a] * a)x 1 + är 1
axe + by = a(y 1 – [b/a] * x 1 ) + bx 1Jämföra LHS och RHS,
x = y 1 – ?b/a? * x 1
y = x 1
Nedan följer en implementering av ovanstående tillvägagångssätt:
C++
// C++ program to demonstrate working of> // extended Euclidean Algorithm> #include> using> namespace> std;> // Function for extended Euclidean Algorithm> int> gcdExtended(> int> a,> int> b,> int> *x,> int> *y)> {> > // Base Case> > if> (a == 0)> > {> > *x = 0;> > *y = 1;> > return> b;> > }> > int> x1, y1;> // To store results of recursive call> > int> gcd = gcdExtended(b%a, a, &x1, &y1);> > // Update x and y using results of> > // recursive call> > *x = y1 - (b/a) * x1;> > *y = x1;> > return> gcd;> }> // Driver Code> int> main()> {> > int> x, y, a = 35, b = 15;> > int> g = gcdExtended(a, b, &x, &y);> > cout < <> 'GCD('> < < a < <> ', '> < < b> > < <> ') = '> < < g < < endl;> > return> 0;> }> |
C
// C program to demonstrate working of extended> // Euclidean Algorithm> #include> // C function for extended Euclidean Algorithm> int> gcdExtended(> int> a,> int> b,> int> *x,> int> *y)> {> > // Base Case> > if> (a == 0)> > {> > *x = 0;> > *y = 1;> > return> b;> > }> > int> x1, y1;> // To store results of recursive call> > int> gcd = gcdExtended(b%a, a, &x1, &y1);> > // Update x and y using results of recursive> > // call> > *x = y1 - (b/a) * x1;> > *y = x1;> > return> gcd;> }> // Driver Program> int> main()> {> > int> x, y;> > int> a = 35, b = 15;> > int> g = gcdExtended(a, b, &x, &y);> > printf> (> 'gcd(%d, %d) = %d'> , a, b, g);> > return> 0;> }> |
Java
// Java program to demonstrate working of extended> // Euclidean Algorithm> import> java.lang.*;> import> java.util.*;> class> GFG {> > // extended Euclidean Algorithm> > public> static> int> gcdExtended(> int> a,> int> b,> int> x,> > int> y)> > {> > // Base Case> > if> (a ==> 0> ) {> > x => 0> ;> > y => 1> ;> > return> b;> > }> > int> x1 => 1> ,> > y1 => 1> ;> // To store results of recursive call> > int> gcd = gcdExtended(b % a, a, x1, y1);> > // Update x and y using results of recursive> > // call> > x = y1 - (b / a) * x1;> > y = x1;> > return> gcd;> > }> > // Driver Program> > public> static> void> main(String[] args)> > {> > int> x => 1> , y => 1> ;> > int> a => 35> , b => 15> ;> > int> g = gcdExtended(a, b, x, y);> > System.out.print(> 'gcd('> + a +> ' , '> + b> > +> ') = '> + g);> > }> }> |
Python3
# Python program to demonstrate working of extended> # Euclidean Algorithm> # function for extended Euclidean Algorithm> def> gcdExtended(a, b):> > # Base Case> > if> a> => => 0> :> > return> b,> 0> ,> 1> > gcd, x1, y1> => gcdExtended(b> %> a, a)> > # Update x and y using results of recursive> > # call> > x> => y1> -> (b> /> /> a)> *> x1> > y> => x1> > return> gcd, x, y> # Driver code> a, b> => 35> ,> 15> g, x, y> => gcdExtended(a, b)> print> (> 'gcd('> , a,> ','> , b,> ') = '> , g)> |
C#
// C# program to demonstrate working> // of extended Euclidean Algorithm> using> System;> class> GFG> {> > > // extended Euclidean Algorithm> > public> static> int> gcdExtended(> int> a,> int> b,> > int> x,> int> y)> > {> > // Base Case> > if> (a == 0)> > {> > x = 0;> > y = 1;> > return> b;> > }> > // To store results of> > // recursive call> > int> x1 = 1, y1 = 1;> > int> gcd = gcdExtended(b % a, a, x1, y1);> > // Update x and y using> > // results of recursive call> > x = y1 - (b / a) * x1;> > y = x1;> > return> gcd;> > }> > > // Driver Code> > static> public> void> Main ()> > {> > int> x = 1, y = 1;> > int> a = 35, b = 15;> > int> g = gcdExtended(a, b, x, y);> > Console.WriteLine(> 'gcd('> + a +> ' , '> +> > b +> ') = '> + g);> > }> }> |
PHP
// PHP program to demonstrate // working of extended // Euclidean Algorithm // PHP function for // extended Euclidean // Algorithm function gcdExtended($a, $b, $x, $y) { // Base Case if ($a == 0) { $x = 0; $y = 1; return $b; } // To store results // of recursive call $gcd = gcdExtended($b % $a, $a, $x, $y); // Update x and y using // results of recursive // call $x = $y - floor($b / $a) * $x; $y = $x; return $gcd; } // Driver Code $x = 0; $y = 0; $a = 35; $b = 15; $g = gcdExtended($a, $b, $x, $y); echo 'gcd(',$a; echo ', ' , $b, ')'; echo ' = ' , $g; ?>> |
Javascript
> // Javascript program to demonstrate> // working of extended> // Euclidean Algorithm> // Javascript function for> // extended Euclidean> // Algorithm> function> gcdExtended(a, b,> > x, y)> {> > // Base Case> > if> (a == 0)> > {> > x = 0;> > y = 1;> > return> b;> > }> > // To store results> > // of recursive call> > let gcd = gcdExtended(b % a,> > a, x, y);> > // Update x and y using> > // results of recursive> > // call> > x = y - (b / a) * x;> > y = x;> > return> gcd;> }> // Driver Code> let x = 0;> let y = 0;> let a = 35;> let b = 15;> let g = gcdExtended(a, b, x, y);> document.write(> 'gcd('> + a);> document.write(> ', '> + b +> ')'> );> document.write(> ' = '> + g);> > |
Utgång:
gcd(35, 15) = 5
Tidskomplexitet: O(log N)
Hjälputrymme: O(log N)
Hur fungerar utökad algoritm?
Som framgår ovan är x och y resultat för ingångarna a och b,
a.x + b.y = gcd —-(1)
Och x 1 och y 1 är resultat för ingångarna b%a och a
(b%a).x 1 + a.y 1 = gcd
När vi sätter b%a = (b – (?b/a?).a) ovan,
vi följer. Observera att ?b/a? är golv(b/a)(b – (?b/a?).a).x 1 + a.y 1 = gcd
Ovanstående ekvation kan också skrivas enligt nedan
b.x 1 + a.(och 1 – (?b/a?).x 1 ) = gcd —(2)
Efter att ha jämfört koefficienterna för 'a' och 'b' i (1) och
(2), vi följer,
x = y 1 – ?b/a? * x 1
y = x 1
Hur är utökad algoritm användbar?
Den utökade euklidiska algoritmen är särskilt användbar när a och b är coprime (eller gcd är 1). Eftersom x är den modulära multiplikativa inversen av en modulo b, och y är den modulära multiplikativa inversen av b modulo a. I synnerhet är beräkningen av den modulära multiplikativa inversen ett väsentligt steg i RSA-krypteringsmetoden med publik nyckel.
