Pierwiastki pierwotne

[Poszukujaca]

Jak szybko znaleźć wszystkie pierwiastki pierwotne dla dużych liczb modulo? Na przykład dla \(\displaystyle{ m=11^{2}}\)?

Mogę skorzystać z twierdzenia, że jeżeli \(\displaystyle{ r}\) jest pierwiastkiem pierwotnym modulo \(\displaystyle{ p}\), to \(\displaystyle{ r}\) lub \(\displaystyle{ p+r}\) jest pierwiastkiem pierwotnym dla \(\displaystyle{ p^{2}}\).

Ale to i tak nie za wiele mi pomoże.

Wszystkich pierwiastków pierwotnych modulo \(\displaystyle{ 121}\) jest aż \(\displaystyle{ \varphi (\varphi(121))=\varphi(110)=40}\).

Mogę znaleźć pierwiastki pierwotne dla \(\displaystyle{ m =11}\) i istotnie są to liczby \(\displaystyle{ 2,6,7,8}\) w związku z tym pierwiastkami pierwotnymi dla \(\displaystyle{ m=121}\) mogą być liczby \(\displaystyle{ 2,6,7,8,13,17,18,19}\), ale to tylko osiem możliwych pierwiastków. Jak znaleźć pozostałe bez liczenia rzędów kolejnych liczb?