{"id":1453,"date":"2026-04-21T20:36:48","date_gmt":"2026-04-21T18:36:48","guid":{"rendered":"https:\/\/trzykody.pl\/?p=1453"},"modified":"2026-04-21T20:36:51","modified_gmt":"2026-04-21T18:36:51","slug":"rozszerzony-algorytm-euklidesa-w-praktyce-obliczeniowej-i-teorii-liczb-krok-po-kroku","status":"publish","type":"post","link":"https:\/\/trzykody.pl\/index.php\/2026\/04\/21\/rozszerzony-algorytm-euklidesa-w-praktyce-obliczeniowej-i-teorii-liczb-krok-po-kroku\/","title":{"rendered":"Rozszerzony algorytm Euklidesa w praktyce obliczeniowej i teorii liczb krok po kroku"},"content":{"rendered":"\n<p>W teorii liczb bardzo cz\u0119sto trzeba nie tylko znale\u017a\u0107 najwi\u0119kszy wsp\u00f3lny dzielnik dw\u00f3ch liczb, ale r\u00f3wnie\u017c wyznaczy\u0107 konkretne wsp\u00f3\u0142czynniki, kt\u00f3re pozwalaj\u0105 ten dzielnik zapisa\u0107 jako kombinacj\u0119 liniow\u0105 tych liczb. To nie jest detal akademicki \u2014 od tego zale\u017cy dzia\u0142anie odwrotno\u015bci modularnej, szyfrowania RSA, rozwi\u0105zywania r\u00f3wna\u0144 diofantycznych i wielu mechanizm\u00f3w u\u017cywanych w programowaniu systemowym oraz kryptografii. Najwygodniejszym narz\u0119dziem do takich oblicze\u0144 pozostaje <strong>Rozszerzony algorytm Euklidesa<\/strong>.<\/p>\n\n\n\n<div class=\"wp-block-rank-math-toc-block\" id=\"rank-math-toc\"><h2>Spis Tre\u015bci<\/h2><nav><ol><li><a href=\"#dlaczego-rozszerzony-algorytm-eukklidesa-jest-wazny-w-teorii-liczb-i-obliczeniach-modularnych\">Dlaczego Rozszerzony algorytm Eukklidesa jest wa\u017cny w teorii liczb i obliczeniach modularnych<\/a><\/li><li><a href=\"#jak-dziala-rozszerzony-algorytm-euklidesa-krok-po-kroku-podczas-wyznaczania-wspolczynnikow-bezouta\">Jak dzia\u0142a Rozszerzony algorytm Euklidesa krok po kroku podczas wyznaczania wsp\u00f3\u0142czynnik\u00f3w B\u00e9zouta<\/a><ol><li><a href=\"#cofanie-obliczen\">Cofanie oblicze\u0144<\/a><\/li><li><a href=\"#implementacja-w-jezyku-c\">Implementacja w j\u0119zyku C<\/a><\/li><li><a href=\"#implementacja-w-c\">Implementacja w C++<\/a><\/li><li><a href=\"#include\">include<\/a><\/li><\/ol><\/li><li><a href=\"#gdzie-rozszerzony-algorytm-euklidesa-pojawia-sie-w-praktyce-i-dlaczego-bledy-tutaj-sa-kosztowne\">Gdzie Rozszerzony algorytm Euklidesa pojawia si\u0119 w praktyce i dlaczego b\u0142\u0119dy tutaj s\u0105 kosztowne<\/a><ol><li><a href=\"#rownania-diofantyczne\">R\u00f3wnania diofantyczne<\/a><\/li><\/ol><\/li><li><a href=\"#typowe-pulapki-bledy-implementacyjne-i-rzeczy-ktore-psuja-wynik-mimo-poprawnego-wzoru\">Typowe pu\u0142apki, b\u0142\u0119dy implementacyjne i rzeczy kt\u00f3re psuj\u0105 wynik mimo poprawnego wzoru<\/a><\/li><li><a href=\"#faq\">FAQ<\/a><ol><li><a href=\"#czy-zawsze-mozna-znalezc-wspolczynniki-dla-dwoch-liczb-calkowitych\">Czy zawsze mo\u017cna znale\u017a\u0107 wsp\u00f3\u0142czynniki dla dw\u00f3ch liczb ca\u0142kowitych<\/a><\/li><li><a href=\"#czy-metoda-dziala-dla-bardzo-duzych-liczb\">Czy metoda dzia\u0142a dla bardzo du\u017cych liczb<\/a><\/li><li><a href=\"#czy-rekurencje-mozna-zastapic-wersja-iteracyjna\">Czy rekurencj\u0119 mo\u017cna zast\u0105pi\u0107 wersj\u0105 iteracyjn\u0105<\/a><\/li><li><a href=\"#czy-wynik-wspolczynnikow-jest-jednoznaczny\">Czy wynik wsp\u00f3\u0142czynnik\u00f3w jest jednoznaczny<\/a><\/li><li><a href=\"#dlaczego-ta-metoda-jest-wazna-w-rsa\">Dlaczego ta metoda jest wa\u017cna w RSA<\/a><\/li><\/ol><\/li><\/ol><\/nav><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"dlaczego-rozszerzony-algorytm-eukklidesa-jest-wazny-w-teorii-liczb-i-obliczeniach-modularnych\">Dlaczego Rozszerzony algorytm Eukklidesa jest wa\u017cny w teorii liczb i obliczeniach modularnych<\/h2>\n\n\n\n<p>Klasyczny algorytm Euklidesa odpowiada na pytanie: jaki jest najwi\u0119kszy wsp\u00f3lny dzielnik liczb <code>a<\/code> i <code>b<\/code>.<\/p>\n\n\n\n<p>Przyk\u0142ad:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>gcd(30, 18) = 6<\/code><\/li>\n<\/ul>\n\n\n\n<p>To jednak cz\u0119sto nie wystarcza. W praktyce potrzebujemy r\u00f3wnie\u017c liczb <code>x<\/code> oraz <code>y<\/code>, takich \u017ce:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Zale\u017cno\u015b\u0107 matematyczna<\/th><th>Znaczenie<\/th><\/tr><\/thead><tbody><tr><td><code>ax + by = gcd(a, b)<\/code><\/td><td>to\u017csamo\u015b\u0107 B\u00e9zouta<\/td><\/tr><tr><td><code>30x + 18y = 6<\/code><\/td><td>przyk\u0142ad dla konkretnych liczb<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Dla powy\u017cszego przyk\u0142adu jednym z rozwi\u0105za\u0144 jest:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Warto\u015b\u0107<\/th><th>Wynik<\/th><\/tr><\/thead><tbody><tr><td><code>x<\/code><\/td><td><code>-1<\/code><\/td><\/tr><tr><td><code>y<\/code><\/td><td><code>2<\/code><\/td><\/tr><tr><td>sprawdzenie<\/td><td><code>30\u00b7(-1) + 18\u00b72 = 6<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>To w\u0142a\u015bnie te wsp\u00f3\u0142czynniki s\u0105 najcenniejsze.<\/p>\n\n\n\n<p>Dlaczego s\u0105 tak wa\u017cne:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>pozwalaj\u0105 obliczy\u0107 odwrotno\u015b\u0107 modulo<\/li>\n\n\n\n<li>umo\u017cliwiaj\u0105 rozwi\u0105zanie r\u00f3wna\u0144 liniowych w liczbach ca\u0142kowitych<\/li>\n\n\n\n<li>s\u0105 podstaw\u0105 dzia\u0142ania RSA<\/li>\n\n\n\n<li>pomagaj\u0105 w analizie kongruencji<\/li>\n\n\n\n<li>wyst\u0119puj\u0105 w implementacjach bibliotek kryptograficznych<\/li>\n<\/ol>\n\n\n\n<p>Bez tych wsp\u00f3\u0142czynnik\u00f3w wiele zada\u0144 trzeba by\u0142oby rozwi\u0105zywa\u0107 r\u0119cznie lub metod\u0105 pr\u00f3b, co przy du\u017cych liczbach staje si\u0119 ca\u0142kowicie niepraktyczne.<\/p>\n\n\n\n<p>Warto te\u017c pami\u0119ta\u0107 o warunku:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Warunek<\/th><th>Wniosek<\/th><\/tr><\/thead><tbody><tr><td><code>gcd(a, m) = 1<\/code><\/td><td>istnieje odwrotno\u015b\u0107 <code>a mod m<\/code><\/td><\/tr><tr><td><code>gcd(a, m) \u2260 1<\/code><\/td><td>odwrotno\u015b\u0107 nie istnieje<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>To jest miejsce, gdzie ta metoda daje realn\u0105 przewag\u0119.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"jak-dziala-rozszerzony-algorytm-euklidesa-krok-po-kroku-podczas-wyznaczania-wspolczynnikow-bezouta\">Jak dzia\u0142a Rozszerzony algorytm Euklidesa krok po kroku podczas wyznaczania wsp\u00f3\u0142czynnik\u00f3w B\u00e9zouta<\/h2>\n\n\n\n<p>Podstaw\u0105 jest zwyk\u0142e dzielenie z reszt\u0105:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wz\u00f3r<\/th><th>Opis<\/th><\/tr><\/thead><tbody><tr><td><code>a = bq + r<\/code><\/td><td>dzielenie ca\u0142kowite<\/td><\/tr><tr><td><code>0 \u2264 r &lt; b<\/code><\/td><td>w\u0142asno\u015b\u0107 reszty<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Dla liczb <code>99<\/code> i <code>78<\/code>:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Krok<\/th><th>Obliczenie<\/th><\/tr><\/thead><tbody><tr><td>1<\/td><td><code>99 = 78\u00b71 + 21<\/code><\/td><\/tr><tr><td>2<\/td><td><code>78 = 21\u00b73 + 15<\/code><\/td><\/tr><tr><td>3<\/td><td><code>21 = 15\u00b71 + 6<\/code><\/td><\/tr><tr><td>4<\/td><td><code>15 = 6\u00b72 + 3<\/code><\/td><\/tr><tr><td>5<\/td><td><code>6 = 3\u00b72 + 0<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Ostatnia niezerowa reszta to:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wynik<\/th><th>Warto\u015b\u0107<\/th><\/tr><\/thead><tbody><tr><td><code>gcd(99, 78)<\/code><\/td><td><code>3<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Teraz najwa\u017cniejsza cz\u0119\u015b\u0107: cofanie podstawie\u0144.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"cofanie-obliczen\">Cofanie oblicze\u0144<\/h3>\n\n\n\n<p>Z kroku 4:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>R\u00f3wnanie<\/th><th>Przekszta\u0142cenie<\/th><\/tr><\/thead><tbody><tr><td><code>3 = 15 - 6\u00b72<\/code><\/td><td>pierwszy zapis<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Z kroku 3:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>R\u00f3wnanie<\/th><th>Podstawienie<\/th><\/tr><\/thead><tbody><tr><td><code>6 = 21 - 15<\/code><\/td><td>podstawiamy wy\u017cej<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Daje to:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wynik<\/th><th>Posta\u0107<\/th><\/tr><\/thead><tbody><tr><td><code>3<\/code><\/td><td><code>15 - 2(21 - 15)<\/code><\/td><\/tr><tr><td>uproszczenie<\/td><td><code>3 = 3\u00b715 - 2\u00b721<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Dalej:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>R\u00f3wnanie<\/th><th>Podstawienie<\/th><\/tr><\/thead><tbody><tr><td><code>15 = 78 - 21\u00b73<\/code><\/td><td>kolejny krok<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Po podstawieniu:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wynik<\/th><th>Posta\u0107<\/th><\/tr><\/thead><tbody><tr><td><code>3<\/code><\/td><td><code>3(78 - 21\u00b73) - 2\u00b721<\/code><\/td><\/tr><tr><td>uproszczenie<\/td><td><code>3 = 3\u00b778 - 11\u00b721<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Na ko\u0144cu:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>R\u00f3wnanie<\/th><th>Podstawienie<\/th><\/tr><\/thead><tbody><tr><td><code>21 = 99 - 78<\/code><\/td><td>ostatnie podstawienie<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Ostatecznie:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wynik ko\u0144cowy<\/th><th>Interpretacja<\/th><\/tr><\/thead><tbody><tr><td><code>3 = -11\u00b799 + 14\u00b778<\/code><\/td><td>wsp\u00f3\u0142czynniki B\u00e9zouta<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Zatem:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wsp\u00f3\u0142czynnik<\/th><th>Warto\u015b\u0107<\/th><\/tr><\/thead><tbody><tr><td><code>x<\/code><\/td><td><code>-11<\/code><\/td><\/tr><tr><td><code>y<\/code><\/td><td><code>14<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>To w\u0142a\u015bnie zwraca implementacja algorytmu.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"implementacja-w-jezyku-c\">Implementacja w j\u0119zyku C<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Kod<\/th><\/tr><\/thead><tbody><tr><td>&#8222;`c<\/td><\/tr><tr><td>#include &lt;stdio.h&gt;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>int exgcd(int a, int b, int *x, int *y)<br>{<br>if (b == 0)<br>{<br>*x = 1;<br>*y = 0;<br>return a;<br>}<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">int x1, y1;<br>int gcd = exgcd(b, a % b, &amp;x1, &amp;y1);*x = y1;<br>*y = x1 - (a \/ b) * y1;return gcd;<\/pre>\n\n\n\n<p>}<\/p>\n\n\n\n<p>int main()<br>{<br>int x, y;<br>int gcd = exgcd(99, 78, &amp;x, &amp;y);<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">printf(\"gcd = %d\\n\", gcd);<br>printf(\"x = %d, y = %d\\n\", x, y);return 0;<\/pre>\n\n\n\n<p>}<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"implementacja-w-c\">Implementacja w C++<\/h3>\n\n\n\n<p>| Kod |<br>|&#8212;|<br>| &#8222;`cpp<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"include\">include<\/h3>\n\n\n\n<p>using namespace std;<\/p>\n\n\n\n<p>int exgcd(int a, int b, int &amp;x, int &amp;y)<br>{<br>if (b == 0)<br>{<br>x = 1;<br>y = 0;<br>return a;<br>}<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int x1, y1;\nint gcd = exgcd(b, a % b, x1, y1);\n\nx = y1;\ny = x1 - (a \/ b) * y1;\n\nreturn gcd;<\/code><\/pre>\n\n\n\n<p>}<\/p>\n\n\n\n<p>int main()<br>{<br>int x, y;<br>int gcd = exgcd(99, 78, x, y);<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>cout &lt;&lt; gcd &lt;&lt; endl;\ncout &lt;&lt; x &lt;&lt; \" \" &lt;&lt; y &lt;&lt; endl;<\/code><\/pre>\n\n\n\n<p>}<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>### Implementacja w Pythonie\n\n| Kod |\n|---|\n| ```python\ndef exgcd(a, b):\n    if b == 0:\n        return a, 1, 0\n\n    gcd, x1, y1 = exgcd(b, a % b)\n\n    x = y1\n    y = x1 - (a \/\/ b) * y1\n\n    return gcd, x, y\n\n\ngcd, x, y = exgcd(99, 78)\n\nprint(gcd)\nprint(x, y)<\/code><\/pre>\n\n\n\n<p>|<\/p>\n\n\n\n<p>Rekurencja jest tu naturalna, bo ka\u017cda kolejna para liczb jest mniejsza od poprzedniej.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"gdzie-rozszerzony-algorytm-euklidesa-pojawia-sie-w-praktyce-i-dlaczego-bledy-tutaj-sa-kosztowne\">Gdzie Rozszerzony algorytm Euklidesa pojawia si\u0119 w praktyce i dlaczego b\u0142\u0119dy tutaj s\u0105 kosztowne<\/h2>\n\n\n\n<p>Najcz\u0119stsze praktyczne zastosowanie to odwrotno\u015b\u0107 modularna.<\/p>\n\n\n\n<p>Szukamy liczby <code>x<\/code>, dla kt\u00f3rej:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wz\u00f3r<\/th><th>Znaczenie<\/th><\/tr><\/thead><tbody><tr><td><code>ax \u2261 1 (mod m)<\/code><\/td><td>odwrotno\u015b\u0107 modularna<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Przyk\u0142ad:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Zadanie<\/th><th>Warto\u015b\u0107<\/th><\/tr><\/thead><tbody><tr><td>znale\u017a\u0107 odwrotno\u015b\u0107 <code>3 mod 11<\/code><\/td><td>szukamy <code>x<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Potrzebujemy:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>R\u00f3wnanie<\/th><th>Cel<\/th><\/tr><\/thead><tbody><tr><td><code>3x + 11y = 1<\/code><\/td><td>wsp\u00f3\u0142czynniki B\u00e9zouta<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Jedno z rozwi\u0105za\u0144:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wynik<\/th><th>Warto\u015b\u0107<\/th><\/tr><\/thead><tbody><tr><td><code>x<\/code><\/td><td><code>4<\/code><\/td><\/tr><tr><td>sprawdzenie<\/td><td><code>3\u00b74 = 12 \u2261 1 mod 11<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Zatem:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Odpowied\u017a<\/th><th>Wynik<\/th><\/tr><\/thead><tbody><tr><td>odwrotno\u015b\u0107 <code>3 mod 11<\/code><\/td><td><code>4<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>To dok\u0142adnie ten mechanizm wykorzystywany przy generowaniu kluczy RSA.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"rownania-diofantyczne\">R\u00f3wnania diofantyczne<\/h3>\n\n\n\n<p>Posta\u0107:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wz\u00f3r<\/th><th>Znaczenie<\/th><\/tr><\/thead><tbody><tr><td><code>ax + by = c<\/code><\/td><td>r\u00f3wnanie liniowe w liczbach ca\u0142kowitych<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Rozwi\u0105zanie istnieje tylko wtedy, gdy:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Warunek<\/th><th>Interpretacja<\/th><\/tr><\/thead><tbody><tr><td><code>gcd(a, b) | c<\/code><\/td><td>dzielnik musi dzieli\u0107 praw\u0105 stron\u0119<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Przyk\u0142ad:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>R\u00f3wnanie<\/th><th>Ocena<\/th><\/tr><\/thead><tbody><tr><td><code>12x + 18y = 30<\/code><\/td><td>rozwi\u0105zanie istnieje<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>bo:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Obliczenie<\/th><th>Wynik<\/th><\/tr><\/thead><tbody><tr><td><code>gcd(12,18)<\/code><\/td><td><code>6<\/code><\/td><\/tr><tr><td><code>30 mod 6<\/code><\/td><td><code>0<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Bez tego sprawdzenia \u0142atwo straci\u0107 du\u017co czasu na szukanie rozwi\u0105zania, kt\u00f3re matematycznie nie istnieje.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"typowe-pulapki-bledy-implementacyjne-i-rzeczy-ktore-psuja-wynik-mimo-poprawnego-wzoru\">Typowe pu\u0142apki, b\u0142\u0119dy implementacyjne i rzeczy kt\u00f3re psuj\u0105 wynik mimo poprawnego wzoru<\/h2>\n\n\n\n<p>Najcz\u0119stszy b\u0142\u0105d to za\u0142o\u017cenie, \u017ce odwrotno\u015b\u0107 modularna istnieje zawsze.<\/p>\n\n\n\n<p>Nie istnieje.<\/p>\n\n\n\n<p>Przyk\u0142ad:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Dane<\/th><th>Wynik<\/th><\/tr><\/thead><tbody><tr><td><code>a = 6<\/code><\/td><td><\/td><\/tr><tr><td><code>m = 9<\/code><\/td><td><\/td><\/tr><tr><td><code>gcd(6,9)<\/code><\/td><td><code>3<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Poniewa\u017c wynik nie jest r\u00f3wny <code>1<\/code>, odwrotno\u015b\u0107 nie istnieje.<\/p>\n\n\n\n<p>Drugi cz\u0119sty problem to znak liczby.<\/p>\n\n\n\n<p>Algorytm mo\u017ce zwr\u00f3ci\u0107:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wynik<\/th><th>Warto\u015b\u0107<\/th><\/tr><\/thead><tbody><tr><td><code>x<\/code><\/td><td><code>-7<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Dla modulo <code>11<\/code> poprawna reprezentacja zwykle powinna by\u0107 dodatnia:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wz\u00f3r<\/th><th>Wynik<\/th><\/tr><\/thead><tbody><tr><td><code>(-7 mod 11)<\/code><\/td><td><code>4<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>W praktyce stosuje si\u0119:<\/p>\n\n\n\n<p>| Kod |<br>|&#8212;|<br>| <code>python x = (x % m + m) % m<\/code> |<\/p>\n\n\n\n<p>Trzeci problem to przepe\u0142nienie typu.<\/p>\n\n\n\n<p>Dla kryptografii liczby s\u0105 ogromne i zwyk\u0142y <code>int<\/code> nie wystarcza. W C\/C++ trzeba u\u017cywa\u0107 wi\u0119kszych typ\u00f3w (<code>long long<\/code>) albo bibliotek big integer.<\/p>\n\n\n\n<p>Czwarty problem to b\u0142\u0119dne dzielenie przy liczbach ujemnych. W r\u00f3\u017cnych j\u0119zykach zachowanie operatora <code>%<\/code> mo\u017ce si\u0119 r\u00f3\u017cni\u0107, wi\u0119c trzeba to sprawdzi\u0107 przed implementacj\u0105.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"faq\">FAQ<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-zawsze-mozna-znalezc-wspolczynniki-dla-dwoch-liczb-calkowitych\">Czy zawsze mo\u017cna znale\u017a\u0107 wsp\u00f3\u0142czynniki dla dw\u00f3ch liczb ca\u0142kowitych<\/h3>\n\n\n\n<p>Tak. Dla dowolnych liczb ca\u0142kowitych <code>a<\/code> i <code>b<\/code> istniej\u0105 takie <code>x<\/code> i <code>y<\/code>, \u017ce:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Wz\u00f3r<\/th><\/tr><\/thead><tbody><tr><td><code>ax + by = gcd(a, b)<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>To jest w\u0142asno\u015b\u0107 wynikaj\u0105ca z to\u017csamo\u015bci B\u00e9zouta.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-metoda-dziala-dla-bardzo-duzych-liczb\">Czy metoda dzia\u0142a dla bardzo du\u017cych liczb<\/h3>\n\n\n\n<p>Tak, i w\u0142a\u015bnie wtedy jest najbardziej potrzebna. W kryptografii pracuje si\u0119 na liczbach maj\u0105cych setki lub tysi\u0105ce bit\u00f3w.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-rekurencje-mozna-zastapic-wersja-iteracyjna\">Czy rekurencj\u0119 mo\u017cna zast\u0105pi\u0107 wersj\u0105 iteracyjn\u0105<\/h3>\n\n\n\n<p>Tak. W systemach o ograniczonym stosie wersja iteracyjna bywa bezpieczniejsza i bardziej przewidywalna.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"czy-wynik-wspolczynnikow-jest-jednoznaczny\">Czy wynik wsp\u00f3\u0142czynnik\u00f3w jest jednoznaczny<\/h3>\n\n\n\n<p>Nie. Najwi\u0119kszy wsp\u00f3lny dzielnik jest jednoznaczny, ale par <code>(x, y)<\/code> mo\u017ce istnie\u0107 niesko\u0144czenie wiele.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"dlaczego-ta-metoda-jest-wazna-w-rsa\">Dlaczego ta metoda jest wa\u017cna w RSA<\/h3>\n\n\n\n<p>Poniewa\u017c podczas generowania klucza prywatnego trzeba znale\u017a\u0107 odwrotno\u015b\u0107 modularn\u0105 wyk\u0142adnika wzgl\u0119dem funkcji Eulera. Bez tego system nie dzia\u0142a poprawnie.<\/p>\n\n\n\n<p>Na poziomie szkolnym wygl\u0105da to jak zwyk\u0142e przekszta\u0142canie r\u00f3wna\u0144. W praktyce od poprawno\u015bci tych kilku krok\u00f3w zale\u017cy bezpiecze\u0144stwo transmisji danych, podpis\u00f3w cyfrowych i dzia\u0142ania ca\u0142ych system\u00f3w autoryzacji. Dlatego warto rozumie\u0107 nie tylko wz\u00f3r, ale r\u00f3wnie\u017c mechanizm cofania podstawie\u0144 i sens wsp\u00f3\u0142czynnik\u00f3w, kt\u00f3re algorytm zwraca.<\/p>\n\n\n\n<p><em>\u0179r\u00f3d\u0142o Foto: Freepik<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>W teorii liczb bardzo cz\u0119sto trzeba nie tylko znale\u017a\u0107 najwi\u0119kszy wsp\u00f3lny dzielnik dw\u00f3ch liczb, ale r\u00f3wnie\u017c wyznaczy\u0107 konkretne wsp\u00f3\u0142czynniki, kt\u00f3re pozwalaj\u0105 ten dzielnik zapisa\u0107 jako kombinacj\u0119 liniow\u0105 tych liczb. To nie jest detal akademicki \u2014 od tego zale\u017cy dzia\u0142anie odwrotno\u015bci modularnej, szyfrowania RSA, rozwi\u0105zywania r\u00f3wna\u0144 diofantycznych i wielu mechanizm\u00f3w u\u017cywanych w programowaniu systemowym oraz kryptografii. Najwygodniejszym narz\u0119dziem do takich oblicze\u0144 pozostaje Rozszerzony algorytm Euklidesa. Dlaczego Rozszerzony algorytm Eukklidesa jest wa\u017cny w teorii liczb i obliczeniach modularnych Klasyczny algorytm Euklidesa odpowiada na pytanie: jaki jest najwi\u0119kszy wsp\u00f3lny dzielnik liczb a i b. Przyk\u0142ad: To jednak cz\u0119sto nie wystarcza. W praktyce potrzebujemy r\u00f3wnie\u017c liczb x oraz y, takich \u017ce: Zale\u017cno\u015b\u0107 matematyczna Znaczenie ax + by = gcd(a, b) to\u017csamo\u015b\u0107 B\u00e9zouta 30x + 18y = 6 przyk\u0142ad dla konkretnych liczb Dla powy\u017cszego przyk\u0142adu jednym z rozwi\u0105za\u0144 jest: Warto\u015b\u0107 Wynik x -1 y 2 sprawdzenie 30\u00b7(-1) + 18\u00b72 = 6 To w\u0142a\u015bnie te wsp\u00f3\u0142czynniki s\u0105 najcenniejsze. Dlaczego s\u0105 tak wa\u017cne: Bez tych wsp\u00f3\u0142czynnik\u00f3w wiele zada\u0144 trzeba by\u0142oby rozwi\u0105zywa\u0107 r\u0119cznie lub metod\u0105 pr\u00f3b, co przy du\u017cych liczbach staje si\u0119 ca\u0142kowicie niepraktyczne. Warto te\u017c pami\u0119ta\u0107 o warunku: Warunek Wniosek gcd(a, m) = 1 istnieje odwrotno\u015b\u0107 a mod m gcd(a, m) \u2260 1 odwrotno\u015b\u0107 nie istnieje To jest miejsce, gdzie ta metoda daje realn\u0105 przewag\u0119. Jak dzia\u0142a Rozszerzony algorytm Euklidesa krok po kroku podczas wyznaczania wsp\u00f3\u0142czynnik\u00f3w B\u00e9zouta Podstaw\u0105 jest zwyk\u0142e dzielenie z reszt\u0105: Wz\u00f3r Opis a = bq + r dzielenie ca\u0142kowite 0 \u2264 r &lt; b w\u0142asno\u015b\u0107 reszty Dla liczb 99 i 78: Krok Obliczenie 1 99 = 78\u00b71 + 21 2 78 = 21\u00b73 + 15 3 21 = 15\u00b71 + 6 4 15 = 6\u00b72 + 3 5 6 = 3\u00b72 + 0 Ostatnia niezerowa reszta to: Wynik Warto\u015b\u0107 gcd(99, 78) 3 Teraz najwa\u017cniejsza cz\u0119\u015b\u0107: cofanie podstawie\u0144. Cofanie oblicze\u0144 Z kroku 4: R\u00f3wnanie Przekszta\u0142cenie 3 = 15 &#8211; 6\u00b72 pierwszy zapis Z kroku 3: R\u00f3wnanie Podstawienie 6 = 21 &#8211; 15 podstawiamy wy\u017cej Daje to: Wynik Posta\u0107 3 15 &#8211; 2(21 &#8211; 15) uproszczenie 3 = 3\u00b715 &#8211; 2\u00b721 Dalej: R\u00f3wnanie Podstawienie 15 = 78 &#8211; 21\u00b73 kolejny krok Po podstawieniu: Wynik Posta\u0107 3 3(78 &#8211; 21\u00b73) &#8211; 2\u00b721 uproszczenie 3 = 3\u00b778 &#8211; 11\u00b721 Na ko\u0144cu: R\u00f3wnanie Podstawienie 21 = 99 &#8211; 78 ostatnie podstawienie Ostatecznie: Wynik ko\u0144cowy Interpretacja 3 = -11\u00b799 + 14\u00b778 wsp\u00f3\u0142czynniki B\u00e9zouta Zatem: Wsp\u00f3\u0142czynnik Warto\u015b\u0107 x -11 y 14 To w\u0142a\u015bnie zwraca implementacja algorytmu. Implementacja w j\u0119zyku C Kod &#8222;`c #include &lt;stdio.h&gt; int exgcd(int a, int b, int *x, int *y){if (b == 0){*x = 1;*y = 0;return a;} int x1, y1;int gcd = exgcd(b, a % b, &amp;x1, &amp;y1);*x = y1;*y = x1 &#8211; (a \/ b) * y1;return gcd; } int main(){int x, y;int gcd = exgcd(99, 78, &amp;x, &amp;y); printf(&#8222;gcd = %d\\n&#8221;, gcd);printf(&#8222;x = %d, y = %d\\n&#8221;, x, y);return 0; } Implementacja w C++ | Kod ||&#8212;|| &#8222;`cpp include using namespace std; int exgcd(int a, int b, int &amp;x, int &amp;y){if (b == 0){x = 1;y = 0;return a;} } int main(){int x, y;int gcd = exgcd(99, 78, x, y); } | Rekurencja jest tu naturalna, bo ka\u017cda kolejna para liczb jest mniejsza od poprzedniej. Gdzie Rozszerzony algorytm Euklidesa pojawia si\u0119 w praktyce i dlaczego b\u0142\u0119dy tutaj s\u0105 kosztowne Najcz\u0119stsze praktyczne zastosowanie to odwrotno\u015b\u0107 modularna. Szukamy liczby x, dla kt\u00f3rej: Wz\u00f3r Znaczenie ax \u2261 1 (mod m) odwrotno\u015b\u0107 modularna Przyk\u0142ad: Zadanie Warto\u015b\u0107 znale\u017a\u0107 odwrotno\u015b\u0107 3 mod 11 szukamy x Potrzebujemy: R\u00f3wnanie Cel 3x + 11y = 1 wsp\u00f3\u0142czynniki B\u00e9zouta Jedno z rozwi\u0105za\u0144: Wynik Warto\u015b\u0107 x 4 sprawdzenie 3\u00b74 = 12 \u2261 1 mod 11 Zatem: Odpowied\u017a Wynik odwrotno\u015b\u0107 3 mod 11 4 To dok\u0142adnie ten mechanizm wykorzystywany przy generowaniu kluczy RSA. R\u00f3wnania diofantyczne Posta\u0107: Wz\u00f3r Znaczenie ax + by = c r\u00f3wnanie liniowe w liczbach ca\u0142kowitych Rozwi\u0105zanie istnieje tylko wtedy, gdy: Warunek Interpretacja gcd(a, b) | c dzielnik musi dzieli\u0107 praw\u0105 stron\u0119 Przyk\u0142ad: R\u00f3wnanie Ocena 12x + 18y = 30 rozwi\u0105zanie istnieje bo: Obliczenie Wynik gcd(12,18) 6 30 mod 6 0 Bez tego sprawdzenia \u0142atwo straci\u0107 du\u017co czasu na szukanie rozwi\u0105zania, kt\u00f3re matematycznie nie istnieje. Typowe pu\u0142apki, b\u0142\u0119dy implementacyjne i rzeczy kt\u00f3re psuj\u0105 wynik mimo poprawnego wzoru Najcz\u0119stszy b\u0142\u0105d to za\u0142o\u017cenie, \u017ce odwrotno\u015b\u0107 modularna istnieje zawsze. Nie istnieje. Przyk\u0142ad: Dane Wynik a = 6 m = 9 gcd(6,9) 3 Poniewa\u017c wynik nie jest r\u00f3wny 1, odwrotno\u015b\u0107 nie istnieje. Drugi cz\u0119sty problem to znak liczby. Algorytm mo\u017ce zwr\u00f3ci\u0107: Wynik Warto\u015b\u0107 x -7 Dla modulo 11 poprawna reprezentacja zwykle powinna by\u0107 dodatnia: Wz\u00f3r Wynik (-7 mod 11) 4 W praktyce stosuje si\u0119: | Kod ||&#8212;|| python x = (x % m + m) % m | Trzeci problem to przepe\u0142nienie typu. Dla kryptografii liczby s\u0105 ogromne i zwyk\u0142y int nie wystarcza. W C\/C++ trzeba u\u017cywa\u0107 wi\u0119kszych typ\u00f3w (long long) albo bibliotek big integer. Czwarty problem to b\u0142\u0119dne dzielenie przy liczbach ujemnych. W r\u00f3\u017cnych j\u0119zykach zachowanie operatora % mo\u017ce si\u0119 r\u00f3\u017cni\u0107, wi\u0119c trzeba to sprawdzi\u0107 przed implementacj\u0105. FAQ Czy zawsze mo\u017cna znale\u017a\u0107 wsp\u00f3\u0142czynniki dla dw\u00f3ch liczb ca\u0142kowitych Tak. Dla dowolnych liczb ca\u0142kowitych a i b istniej\u0105 takie x i y, \u017ce: Wz\u00f3r ax + by = gcd(a, b) To jest w\u0142asno\u015b\u0107 wynikaj\u0105ca z to\u017csamo\u015bci B\u00e9zouta. Czy metoda dzia\u0142a dla bardzo du\u017cych liczb Tak, i w\u0142a\u015bnie wtedy jest najbardziej potrzebna. W kryptografii pracuje si\u0119 na liczbach maj\u0105cych setki lub tysi\u0105ce bit\u00f3w. Czy rekurencj\u0119 mo\u017cna zast\u0105pi\u0107 wersj\u0105 iteracyjn\u0105 Tak. W systemach o ograniczonym stosie wersja iteracyjna bywa bezpieczniejsza i bardziej przewidywalna. Czy wynik wsp\u00f3\u0142czynnik\u00f3w jest jednoznaczny Nie. Najwi\u0119kszy wsp\u00f3lny dzielnik jest jednoznaczny, ale par (x, y) mo\u017ce istnie\u0107 niesko\u0144czenie wiele. Dlaczego ta metoda jest wa\u017cna w RSA Poniewa\u017c podczas generowania klucza prywatnego trzeba znale\u017a\u0107 odwrotno\u015b\u0107 modularn\u0105 wyk\u0142adnika wzgl\u0119dem funkcji Eulera. Bez tego system nie dzia\u0142a poprawnie. Na poziomie szkolnym wygl\u0105da to jak zwyk\u0142e przekszta\u0142canie r\u00f3wna\u0144. W praktyce od poprawno\u015bci tych kilku krok\u00f3w zale\u017cy bezpiecze\u0144stwo transmisji danych, podpis\u00f3w cyfrowych i dzia\u0142ania ca\u0142ych system\u00f3w autoryzacji. Dlatego warto rozumie\u0107 nie tylko wz\u00f3r, ale r\u00f3wnie\u017c mechanizm cofania podstawie\u0144 i sens wsp\u00f3\u0142czynnik\u00f3w, kt\u00f3re algorytm zwraca. \u0179r\u00f3d\u0142o Foto: Freepik<\/p>\n","protected":false},"author":1,"featured_media":1454,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24],"tags":[],"class_list":["post-1453","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-kodowanie"],"_links":{"self":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1453","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/comments?post=1453"}],"version-history":[{"count":1,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1453\/revisions"}],"predecessor-version":[{"id":1455,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/posts\/1453\/revisions\/1455"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/media\/1454"}],"wp:attachment":[{"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/media?parent=1453"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/categories?post=1453"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/trzykody.pl\/index.php\/wp-json\/wp\/v2\/tags?post=1453"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}