Otóż znamy dokładny rozkład liczby \(\displaystyle{ n-1}\), nawet został tak ładnie kanonicznie wypisany wyżej.
Więc możemy skorzystać z testu pierwszości Lucasa ()
Jak czytamy w definicji testu, musimy znaleźć liczbę całkowitą \(\displaystyle{ a: 1<a<n}\), która:
1. po pierwsze da
\(\displaystyle{ a^{n-1}\equiv1\pmod{n}}\)
2. a dla każdego dzielnika \(\displaystyle{ q}\) liczby \(\displaystyle{ n-1}\) da
\(\displaystyle{ a^{\frac{n-1}{q}}\not\equiv1\pmod{n}}\)
Taka liczba \(\displaystyle{ a}\) jest po prostu generatorem grupy multiplikatywnej \(\displaystyle{ (\mathbb{Z}/n\mathbb{Z})*}\).
Każda liczba pierwsza ma sporo takich generatorów (tyle co niereszt kwadratowych czyli \(\displaystyle{ \frac{n-1}{2}}\)), więc jest spora szansa że trafimy losując jakieś \(\displaystyle{ a}\). Spróbujmy np. \(\displaystyle{ a=5}\):
no niestety, co prawda \(\displaystyle{ 5^{n-1}\equiv1\pmod{n}}\), ale \(\displaystyle{ 5^{\frac{n-1}{2}}\equiv1\pmod{n}}\) wbrew temu co ma być.
Swoją drogą warto zauważyć, że dla liczb \(\displaystyle{ n=k!+1}\) nie trzeba sprawdzać wszystkich dzielników liczby \(\displaystyle{ n-1}\) a tylko te z zakresu od \(\displaystyle{ 2}\) do \(\displaystyle{ k}\). Pomyślcie dlaczego
Ponadto wystarczy sprawdzać tylko dzielniki pierwsze, a więc dla naszego przypadku będzie to zbiór \(\displaystyle{ A=\{2,3,5,7,11\}}\). Oczywiście mam na myśli obliczanie wartości \(\displaystyle{ a^{\frac{n-1}{q}}: q\in A}\).
Ukryta treść:
