Znajdź najmniejszy pierwiastek pierwotny modulo p

[jelonekrogacz]

Znajdź najmniejszy pierwiastek pierwotny modulo p (gdzie p - to liczba pierwsza).
Czy ktoś spotkał się z takim zagadnieniem? Czy istnieje jakiś algorytm lepszy niż sprawdzanie po kolei liczb korzystając z definicji pierwiastka pierwotnego?

[pawels]

Można jeszcze rozłożyć \(\displaystyle{ p-1}\) na czynniki i jeżeli \(\displaystyle{ d}\) jest dzielnikiem to sprawdzić dla jakich \(\displaystyle{ g}\) mamy \(\displaystyle{ g^d\equiv 1}\). Jeżeli dla żadnego, mniejszego od \(\displaystyle{ p-1}\), to \(\displaystyle{ g}\) jest generatorem.

Wydaje się, że samego sprawdzania jest mniej, jednak jeżeli jest to pytanie pod kątem szukania odpowiedniego algorytmu to dość duży problem może stanowić faktoryzacja.

[SaxoN]

Zauważ, że generatorów jest stosunkowo sporo, bo \(\displaystyle{ \varphi(p-1)}\). Nie ma na to żadnego wzorku, ale możemy losować kolejne liczby, sprawdzać, czy są generatorami, a jak natrafimy na jeden z nich to znaleźć wszystkie za pomocą tego co napisałem w 201862.htm Jak mamy wszystkie to dość łatwo stwierdzamy który jest najmniejszy ^^ Równie dobrze możemy sprawdzać po kolei... Efektywniejszego sposobu nie znam xD