Euklidův algoritmus na tomto případě

Question

1

Euklidův algoritmus na tomto případě

MI-MPI

asked Nov 14 '15

vasekj
13 ●1 ●1 ●3

updated Nov 16 '15

VojtechMyslivec

743 ●9 ●17 ●29

zasekl jsem se na spočítání tohoto příkladu (výsledek znám, ale nevím kde dělám chybu v postupu) - můžete sem prosím někdo napsat správné řešení?

Jedná se mi o spočítání inverze od $20$ , v $GF(3^2)$ mod $x^2+2x+2$ (pomocí rozšířeného euklidova algoritmu) Díky

Můj postup:

|           |       x^2 + 2x + 2 |      1 |      0 |
|           |                 -x |      0 |      1 |    (protože 2x = -x)
|    2x + 1 |                  2 |      1 |    x+2 |
|        x  |                  0 |     -x |     0  |

add a comment

Accepted Answer

2

answered Nov 14 '15

VojtechMyslivec

743 ●9 ●17 ●29

updated Nov 16 '15

Druhy krok je zbytecny. Jiz v 1. kroku algoritmu je nutne skoncit, protoze mas polynom nulteho stupne (tedy nasobek jednotkoveho prvku).

Problem je, ze nevysla $1$ , ale $2$ . Proto je nutne cely radek vynasobit inverzi $2$ , coz je opet $2$ . Celkova inverze by mela byt $2x + 1$

Jinymi slovy: radky u EEA predstavuji rovnice. hodnoty jsou koeficienty a "v zahlavi" tabulky jsou cleny, ktere se nasobi. Posledni radek predstavuje (Bezoutovu? prosim doplnit) rovnost:

$$2 = 1(2x^2 + 2x + 2) + (x + 2)(2x)$$

a kdyz vynasobis rovnici inverzi dvojky -- coz je opet 2, ziskas rovnost, kterou hledas:

$$1 = 2(2x^2 + 2x + 2) + (2x + 1)(2x)$$

Inverze prvku $2x$ je tedy $2x+1$

EDIT: Jeste radeji prepisu EEA:

|           |       x^2 + 2x + 2 |      1 |      0 |
|           |                 2x |      0 |      1 |
|    2x + 1 |                  2 |      1 |    x+2 |

* 2
|           |                  1 |      2 |   2x+1 |

link

Comments

1

díky moc!

vasekj (Nov 14 '15)

ano: https://cs.wikipedia.org/wiki/B%C3%A9zoutova_rovnost .

Miro Hrončok (Nov 16 '15)

OK, diky, snad to bude dostatecne kvalitni zdroj, chtel jsem byt exaktni a hlanvne se shodnout s tim, co se uci v MI-MPI ;]
diky i za prekopirovani pastebinu sem.

VojtechMyslivec (Nov 16 '15)

add a comment

Euklidův algoritmus na tomto případě

1 Answer

Comments

Your answer

Question tools

Stats

Related questions