Matematické Fórum

scortyak47 · 26. 11. 2009 13:55

Zdravim vedel by mi niekto poradit ako urcim ci je x parne (sude) alebo nie z tohoto

g^(x*(p-1)/2) mod p

kde g je generatorom multiplikativnej grupy Zp*, p je prvocislo
vopred dakujem za odpoved.

Kondr · 26. 11. 2009 17:56

Po umocnění na druhou to musí dát 1 (Malá Fermatova věta, resp. Lagrangeova http://en.wikipedia.org/wiki/Lagrange%2 … _theory%29).

Protože to samo o sobě nemůže být 1 (jinak by g nebyl generátor), musí to být -1.

scortyak47

ako viem ze g^(p-1) (mod p) je jedna ale ako mi to pomoze pri urceni parnosti alebo neparnosti toho x?

Kondr · 26. 11. 2009 20:53 — Editoval Kondr (26. 11. 2009 22:28)

↑ scortyak47:
$g^{p-1}=1$ to je přímo malá Fermatova věta (speciální případ Lagrangeovy).
Pak $g^{(p-1)/2}=\pm 1$ . Kdyby bylo $g^{(p-1)/2}=1$ , nebyl by g generátor. Proto $g^{(p-1)/2}=-1$ , takže $g^{(p-1)x/2}=(-1)^x$ .