Rząd elementu w grupie
-
- Użytkownik
- Posty: 171
- Rejestracja: 1 lis 2008, o 13:33
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 43 razy
- Pomógł: 3 razy
Rząd elementu w grupie
Witam, muszę napisać program wyliczający rząd elementu \(\displaystyle{ \alpha}\) w grupie \(\displaystyle{ Z_{p}*}\), gdzie \(\displaystyle{ p}\) jest liczbą pierwszą. Czy istnieje jakiś algorytm pozwalający na relatywne szybkie jego obliczenie, czy jedynym wyjściem jest liczenie potęg modulo ażdo skutku - otrzymania wyniku 1?
- Ponewor
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
Rząd elementu w grupie
Nad algorytmem jeszcze pomyślę, ale z MTF musisz sprawdzić (tylko) pierwsze \(\displaystyle{ p-1}\) potęg. A właściwie sprawdzić musisz \(\displaystyle{ p-2}\), bo \(\displaystyle{ p-1}\) jest już pewne.
EDIT
Żaden algorytm nie jest potrzebny:
jeśli dobrze czytam
\(\displaystyle{ x = ord_{p}(a) = p-1}\)
EDIT
Żaden algorytm nie jest potrzebny:
jeśli dobrze czytam
\(\displaystyle{ x = ord_{p}(a) = p-1}\)
-
- Użytkownik
- Posty: 171
- Rejestracja: 1 lis 2008, o 13:33
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 43 razy
- Pomógł: 3 razy
Rząd elementu w grupie
Podana przez Ciebie własność dotyczy jedynie sytuacji, gdy \(\displaystyle{ \alpha}\) jest liczbą pierwszą - w moim przypadku nie ma niestety takiego wymagania.