Ask Your Question
1

Euklidův algoritmus na tomto případě

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

vasekj gravatar image

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

VojtechMyslivec gravatar image

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

1 Answer

Sort by » oldest newest most voted
2

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

VojtechMyslivec gravatar image

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 more

Comments

1

díky moc!

vasekj ( 2015-11-15 00:05:16 +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

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

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

Seen: 498 times

Last updated: Nov 16 '15