Euklidův algoritmus na tomto případě

Question

1

Euklidův algoritmus na tomto případě

MI-MPI

asked 2015-11-14 19:26:59 +0100

vasekj
13 ●1 ●1 ●3

updated 2015-11-16 19:29:57 +0100

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  |

edit retag flag offensive close delete

Accepted Answer

2

answered 2015-11-14 22:07:14 +0100

VojtechMyslivec

743 ●9 ●17 ●29

updated 2015-11-16 19:24:27 +0100

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 |

edit flag offensive delete publish link

Comments

1

díky moc!

vasekj ( 2015-11-15 00:05:16 +0100 )edit

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

Miro Hrončok ( 2015-11-16 17:05:15 +0100 )edit

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 ( 2015-11-16 19:28:48 +0100 )edit

Euklidův algoritmus na tomto případě

1 Answer

Comments

Your answer

Question tools

Stats

Related questions