Matematické Fórum

spacemaster · 11. 04. 2016 21:05

Zdravím.

Mohl by mi prosím někdo objasnit jak se počítá modulo pro číslo se záporným exponentem?

Příklad: 22^-10 (mod 41)

Objasnění principu a postup bych velmi ocenil. A prosím, vysvětlení jako pro blbečka, děkuji :)

vanok · 11. 04. 2016 21:22

Ahoj ↑ spacemaster:,
Staci konstatovat ze inverz modulo 41 cisla 22 je 28.
Zvysok je jednoduchy

byk7 · 11. 04. 2016 21:27

Platí $22^{-10}=$22^{10}$^{-1}$ , tzn. chceš najít takové číslo $a$ , pro které platí $22^{10}\cdot a\equiv1\pmod{41}$ (hledáš inverzi k $22^{10}$ ). To se udělá pomocí Bezoutovy věty a Euklidova algoritmu.

spacemaster · 11. 04. 2016 21:28

Díky za odpověď, ale to vůbec není vysvětlení pro blbečka :)

Můžeš to prosím rozvést? Jak jsi přišel na číslo 28?

byk7 · 11. 04. 2016 21:34

↑ spacemaster:

Pomocí Bezoutovy věty a (rozšířeného) Euklidova algoritmu, asi se to dělá v MB104 nebo MB204.

vanok · 11. 04. 2016 21:36

Jedna ina mozna metoda je skusobna, pocitac postupne mocny cisla 22 mod 41
( akoze 41 je prvocislo, je jasne ( = prednaska) ze existuje ten inverz.
Ale osobne to robim ako ↑ byk7: ( no ale ak nemas nastudovane vlasnosti ... Tak pouzi to co som popisal tu)

spacemaster

Bezout a Euklid už jsou odpovědi co jsem potřeboval sylšet. Ale pořád mám problém.

Spočítal jsem Euklida a vyšlo mi:

41 = 1 * 22 + 19
22 = 1 * 19 + 3
19 = 6 * 3 + 1
3 = 3 * 1 + 0

Z toho sem spočítal Bez. koeficienty:

1 = 19 - 6 * 3
1 = 7 * 19 - 6 * 22
1 = 7 * 41 - 13 * 22

Tudíž koeficinty mám a = 7, b = -13. Co dál? Koeficient 28 mi nevyšel, i když jsem si online kalkulátorem ověřil, že existuje pro kombinaci: (-15 * 41) + (28 * 22) = 1

EDIT: Btw probblém který se tímhle snažím vyřešit je ElGamal, kde potřebuju spočítat 6 / 22^10 mod 41. To jsem si převedl na 6 * 22^-10 mod 41. Předpokládám, že mi stačí spočítat 22^-10 mod 41 a pak jen vynásobím výsledek 6ti modulo 41 což zvládnu bez pomoci :)

vanok · 11. 04. 2016 22:13 — Editoval vanok (11. 04. 2016 22:13)

Vyssiel, vsak -13=28 mod 41

byk7 · 11. 04. 2016 22:13 — Editoval byk7 (11. 04. 2016 22:18)

↑ spacemaster:

$-13\equiv 28\pmod{41}$

Edit.: Ale osobně bych to dělal trochu jinak: $22^{10}\equiv\cdots\equiv9\pmod{41}$ a pak hledal inverzi k devítce, (ale nejsem schopný posoudit, co je efektivnější).

spacemaster · 11. 04. 2016 22:35

Ok, tak mám tedy 28. Co s tím dál? 6*28 je 168 mod 41 je 4, což není správný výsledek.

Omlouvám se, ale opravdu to potřebuji jako pro blbečka.

byk7 · 11. 04. 2016 22:38

↑ spacemaster:

28 je inverze k 22, ne k 22^10.

spacemaster · 11. 04. 2016 22:48

Aha jo, už mi to docvaklo :D Díky za trpělivost, už to chápu.

Matematické Fórum

#1 11. 04. 2016 21:05

Modulo čísla se záporným exponentem

#2 11. 04. 2016 21:22

Re: Modulo čísla se záporným exponentem

#3 11. 04. 2016 21:27

Re: Modulo čísla se záporným exponentem

#4 11. 04. 2016 21:28

Re: Modulo čísla se záporným exponentem

#5 11. 04. 2016 21:34

Re: Modulo čísla se záporným exponentem

#6 11. 04. 2016 21:36

Re: Modulo čísla se záporným exponentem

#7 11. 04. 2016 21:58 — Editoval spacemaster (11. 04. 2016 22:03)

Re: Modulo čísla se záporným exponentem

#8 11. 04. 2016 22:13 — Editoval vanok (11. 04. 2016 22:13)

Re: Modulo čísla se záporným exponentem

#9 11. 04. 2016 22:13 — Editoval byk7 (11. 04. 2016 22:18)

Re: Modulo čísla se záporným exponentem

#10 11. 04. 2016 22:35

Re: Modulo čísla se záporným exponentem

#11 11. 04. 2016 22:38

Re: Modulo čísla se záporným exponentem

#12 11. 04. 2016 22:48

Re: Modulo čísla se záporným exponentem

Zápatí