Rząd elementu w grupie

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Watari
Użytkownik
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

Post autor: Watari »

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?
Awatar użytkownika
Ponewor
Moderator
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

Post autor: Ponewor »

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}\)
Watari
Użytkownik
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

Post autor: Watari »

Podana przez Ciebie własność dotyczy jedynie sytuacji, gdy \(\displaystyle{ \alpha}\) jest liczbą pierwszą - w moim przypadku nie ma niestety takiego wymagania.
ODPOWIEDZ