Matematické Fórum

Torpy · 04. 09. 2011 16:47

Zdravím,
mohl by mi někdo dát hint jak na tuhle úlohu?
Najít v $\mathbb Z_{256}^*$ prvek řádu 32.
Řekl bych, že by se mohlo hodit použít izomorfismus $\mathbb Z_{256}^* \simeq \mathbb Z_{64} \times \mathbb Z_{2}$ ale nenapadá mě jak.

Díky za radu.

Torpy · 21. 09. 2011 19:44

Opravdu nikdo nevíte?

check_drummer · 21. 09. 2011 20:01

↑ Torpy:
A z čeho plyne, že jsou obě struktury izomorfní?

Torpy · 22. 09. 2011 00:00

Na to mám přímo větu -

pokud p je liché prvočíslo, pak platí $\mathbb Z_{p^e}^*$ je cyklická řádu $(p-1)p^{e-1}$ pro každé e>0

pokud p=2, pak $\mathbb Z_{2^e}^* \simeq \mathbb Z_{2^{e-2}} \times Z_2$ pro každé e>2

musixx · 22. 09. 2011 08:43 — Editoval musixx (22. 09. 2011 08:47)

Idea v aditivní terminologii: najít prvek řádu 32 v cyklické grupě řádu 64 nebude až takový problém (dvojnásobek generátoru?), pak k tomu vzít nulu ze ${\mathbb Z}_2$ a podívat se, kam to pošle ten tou tvou větou zaručený izomorfismus.

EDIT: Jediný potenciální problém je ten izomorfismus. Ale umím si představit, že důkaz té zmíněné věty není existenční, ale konstruktivní, takže tam je vhodné hledat návod. Je tak?

and · 22. 09. 2011 11:16

Plati vztah $5^{2^{e-3}}\equiv1+2^{e-1} mod 2^e$ , ak $e\ge3$

Mnozina $P=\{1+2a;0\le a<2^{e-1}\}$ je radu $2^{e-1}$
nech $M=\{1+4a;0\le a<2^{e-2}\}$ jej rad je $2^{e-2}$ , potom $M$ je podmnozina $P$
$5\in M$ , z vyssie uvedeneho vztahu plynie ze prvok $5$ je radu $2^{e-2}$ , pretoze $5^{2^{e-3}}\not\equiv1 mod 2^e$
v nasom pripade $e=7$
Teraz staci zobrat vhodnu mocninu $5$ , tj. hladany prvok radu $32$ je $5^2$

check_drummer · 23. 09. 2011 16:11

and napsal(a):
... z vyssie uvedeneho vztahu plynie ze prvok $5$ je radu $2^{e-2}$

O jaké grupě v tomto případě mluvíme? Díky.

and · 23. 09. 2011 16:49

v $\mathbb Z_{256}^*$

Torpy · 24. 09. 2011 23:29

Aha, tak už je mi to jasné.
Já nevěděl jak se poprat s tím izomorfismem. Ale je pravda, že z důkazu toho tvrzení se to dá vyčíst, ten důkaz je založen přesně na tom, co psal And.
Takže velké díky vám všem za rady!

check_drummer · 26. 09. 2011 21:17

Torpy napsal(a):
Na to mám přímo větu -

pokud p je liché prvočíslo, pak platí $\mathbb Z_{p^e}^*$ je cyklická řádu $(p-1)p^{e-1}$ pro každé e>0

pokud p=2, pak $\mathbb Z_{2^e}^* \simeq \mathbb Z_{2^{e-2}} \times Z_2$ pro každé e>2

Čistě ze zvědavosti - máš prosím odkaz na důkaz této věty? Díky

Torpy · 27. 09. 2011 20:46

Důkaz je v těchto skriptech, kapitola 2.10:
http://www.karlin.mff.cuni.cz/~holub/so … ptaRSA.pdf

Nebo tady, kapitola 7.5:
http://shoup.net/ntb/ntb-v2.pdf

Matematické Fórum

#1 04. 09. 2011 16:47

Prvek daného řádu v grupě

#2 21. 09. 2011 19:44

Re: Prvek daného řádu v grupě

#3 21. 09. 2011 20:01

Re: Prvek daného řádu v grupě

#4 22. 09. 2011 00:00

Re: Prvek daného řádu v grupě

#5 22. 09. 2011 08:43 — Editoval musixx (22. 09. 2011 08:47)

Re: Prvek daného řádu v grupě

#6 22. 09. 2011 11:16

Re: Prvek daného řádu v grupě

#7 23. 09. 2011 16:11

Re: Prvek daného řádu v grupě

and napsal(a):

#8 23. 09. 2011 16:49

Re: Prvek daného řádu v grupě

#9 24. 09. 2011 23:29

Re: Prvek daného řádu v grupě

#10 26. 09. 2011 21:17

Re: Prvek daného řádu v grupě

Torpy napsal(a):

#11 27. 09. 2011 20:46

Re: Prvek daného řádu v grupě

Zápatí