logo

TechCodeview

Euklidovské algoritmy (základní a rozšířené)

Euklidovský algoritmus je způsob, jak najít největšího společného dělitele dvou kladných celých čísel. GCD dvou čísel je největší číslo, které je dělí obě. Jednoduchý způsob, jak najít GCD, je rozklad obou čísel a násobení společných prvočinitelů.

GCD



Základní euklidovský algoritmus pro GCD:

Algoritmus je založen na níže uvedených skutečnostech.

  • Pokud odečteme menší číslo od většího (větší číslo snížíme), GCD se nezmění. Takže pokud budeme opakovaně odečítat větší ze dvou, skončíme s GCD.
  • Nyní namísto odčítání, pokud vydělíme menší číslo, algoritmus se zastaví, když najdeme zbytek 0.

Níže je uvedena rekurzivní funkce pro vyhodnocení gcd pomocí Euklidova algoritmu:

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;> }> 

>

c kód pole řetězců 
>

Jáva




// 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> 

>

>

Výstup 

GCD(10, 15) = 5 GCD(35, 10) = 5 GCD(31, 2) = 1>

Časová náročnost: O(Log min(a, b))
Pomocný prostor: O(Log (min(a,b))

Rozšířený euklidovský algoritmus:

Rozšířený euklidovský algoritmus také najde celočíselné koeficienty x a y takové, že: ax + by = gcd(a, b)

Příklady:

Vstup: a = 30, b = 20
Výstup: gcd = 10, x = 1, y = -1
(Všimněte si, že 30*1 + 20*(-1) = 10)

Vstup: a = 35, b = 15
Výstup: gcd = 5, x = 1, y = -2
(Všimněte si, že 35*1 + 15*(-2) = 5)

Rozšířený euklidovský algoritmus aktualizuje výsledky gcd(a, b) pomocí výsledků vypočítaných rekurzivním voláním gcd(b%a, a). Nechť hodnoty x a y vypočítané rekurzivním voláním jsou x1a y1. x a y se aktualizují pomocí níže uvedených výrazů.

ax + by = gcd(a, b)
gcd(a, b) = gcd(b%a, a)
gcd(b%a, a) = (b%a)x1+ je1
ax + by = (b%a)x1+ je1
ax + by = (b – [b/a] * a)x1+ je1
ax + by = a(y1– [b/a] * x1) + bx1

python zápis json do souboru

Porovnání LHS a RHS,
x = y1– ?b/a? * X1
y = x1

Doporučená praxe Rozšířený euklidovský algoritmus Vyzkoušejte to!

Níže je uvedena implementace výše uvedeného přístupu:

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;> }> 

>

>

Jáva




// 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; ?>> 

>

setinterval javascript 
>

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);> > 

>

>

Výstup : 

gcd(35, 15) = 5>

Časová náročnost: O(log N)
Pomocný prostor: O(log N)

Jak funguje rozšířený algoritmus?

Jak je vidět výše, x a y jsou výsledky pro vstupy a a b,

a.x + b.y = gcd —-(1)

A x1a y1jsou výsledky pro vstupy b%a a a

(b%a).x1+ a.y1= gcd

Když výše vložíme b%a = (b – (?b/a?).a),
sledujeme. Všimněte si, že ?b/a? je podlaha (b/a)

(b – (?b/a?).a).x1+ a.y1= gcd

Výše uvedená rovnice může být také zapsána jako níže

b.x1+ a. (a1– (?b/a?).x1) = gcd — (2)

Po porovnání koeficientů „a“ a „b“ v (1) a
(2), sledujeme,
x = y1– ?b/a? * X1
y = x1

Jak je rozšířený algoritmus užitečný?

Rozšířený euklidovský algoritmus je zvláště užitečný, když aab jsou coprime (nebo gcd je 1). Protože x je modulární multiplikativní inverze k a modulo b, ay je modulární multiplikativní inverze k b modulo a. Zejména výpočet modulární multiplikativní inverze je zásadním krokem v metodě šifrování RSA veřejným klíčem.