Kalkulator pierwiastka pierwotnego

Witaj w kalkulatorze pierwiastka pierwotnego, potężnym darmowym narzędziu online, które znajduje wszystkie pierwiastki pierwotne modulo dowolna dodatnia liczba całkowita n. Ten kalkulator zapewnia weryfikację krok po kroku, tabele potęg oraz animowaną wizualizację grupy cyklicznej, aby pomóc Ci zrozumieć, w jaki sposób pierwiastki pierwotne generują grupy multiplikatywne. Niezależnie od tego, czy studiujesz teorię liczb, przygotowujesz się do egzaminów z kryptografii, czy pracujesz z arytmetyką modularną w programowaniu konkurencyjnym, to narzędzie dostarcza natychmiastowe, dokładne wyniki wraz z edukacyjnymi spostrzeżeniami.

Co to jest pierwiastek pierwotny?

Pierwiastek pierwotny modulo n to liczba całkowita g, której potęgi generują wszystkie liczby całkowite względnie pierwsze z n. Formalnie, g jest pierwiastkiem pierwotnym mod n, jeśli rząd multiplikatywny g modulo n jest równy funkcji totient Eulera \(\varphi(n)\). Oznacza to, że zbiór

zawiera dokładnie wszystkie \(\varphi(n)\) liczb całkowitych od 1 do n-1, które są względnie pierwsze z n. Pierwiastek pierwotny jest zasadniczo generatorem grupy cyklicznej \((\mathbb{Z}/n\mathbb{Z})^*\).

Szybki przykład

Rozważmy n = 7. Ponieważ 7 jest liczbą pierwszą, \(\varphi(7) = 6\). Sprawdźmy, czy g = 3 jest pierwiastkiem pierwotnym:

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

Potęgi dają {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}, czyli wszystkie liczby całkowite względnie pierwsze z 7. Zatem 3 jest pierwiastkiem pierwotnym modulo 7.

Kiedy istnieją pierwiastki pierwotne?

Pierwiastki pierwotne modulo n istnieją wtedy i tylko wtedy, gdy n ma jedną z tych form:

• n = 1, 2 lub 4
• n = p^k, gdzie p jest nieparzystą liczbą pierwszą, a k ≥ 1
• n = 2p^k, gdzie p jest nieparzystą liczbą pierwszą, a k ≥ 1

Na przykład pierwiastki pierwotne istnieją dla 7, 9, 11, 13, 14, 18, 23, 25, 27, 46, ale nie dla 8, 12, 15, 16, 20, 21, 24.

Jak znaleźć pierwiastki pierwotne

1. Wprowadź moduł: Wpisz dodatnią liczbę całkowitą n (od 2 do 100 000) w pole wejściowe.
2. Oblicz: Kliknij "Znajdź pierwiastki pierwotne" lub naciśnij Enter.
3. Zobacz wszystkie pierwiastki: Zobacz pełną listę pierwiastków pierwotnych wraz z funkcją totient Eulera i statystykami.
4. Przeanalizuj tabelę potęg: Sprawdź, jak najmniejszy pierwiastek pierwotny generuje wszystkie reszty względnie pierwsze.
5. Wizualizuj grupę cykliczną: Dla małych modułów zobacz animowane koło pokazujące strukturę cykliczną.

Ile pierwiastków pierwotnych ma n?

Jeśli pierwiastki pierwotne modulo n istnieją, ich liczba wynosi:

Na przykład dla n = 13: \(\varphi(13) = 12\) i \(\varphi(12) = 4\), więc istnieją dokładnie 4 pierwiastki pierwotne modulo 13 (które wynosą 2, 6, 7, 11).

Algorytm weryfikacji

Aby skutecznie sprawdzić, czy g jest pierwiastkiem pierwotnym modulo n:

1. Oblicz \(\varphi(n)\) przy użyciu faktoryzacji liczby n
2. Znajdź wszystkie różne czynniki pierwsze \(p_1, p_2, \ldots, p_k\) liczby \(\varphi(n)\)
3. Dla każdego czynnika pierwszego \(p_i\) sprawdź: \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. Jeśli WSZYSTKIE testy przejdą pomyślnie, g jest pierwiastkiem pierwotnym

Ta metoda jest znacznie szybsza niż obliczanie wszystkich potęg g, ponieważ musimy przetestować tylko \(k\) potęgowań zamiast \(\varphi(n)\).

Pierwiastki pierwotne w kryptografii

Wymiana kluczy Diffiego-Hellmana

Protokół Diffiego-Hellmana wykorzystuje dużą liczbę pierwszą p i pierwiastek pierwotny g modulo p. Alicja wybiera sekret a, wysyła \(g^a \bmod p\). Bob wybiera sekret b, wysyła \(g^b \bmod p\). Oboje obliczają wspólny sekret \(g^{ab} \bmod p\). Bezpieczeństwo opiera się na tym, że problem logarytmu dyskretnego jest trudny obliczeniowo.

Szyfrowanie ElGamal

ElGamal również wykorzystuje pierwiastek pierwotny jako generator. Klucz publiczny to \((p, g, g^x \bmod p)\), gdzie x jest prywatne. Fakt, że g generuje wszystkie elementy, gwarantuje, że każda wiadomość może zostać zaszyfrowana.

Podpisy cyfrowe

DSA (Digital Signature Algorithm) i powiązane schematy wykorzystują pierwiastki pierwotne w podgrupach \((\mathbb{Z}/p\mathbb{Z})^*\) do tworzenia i weryfikacji podpisów cyfrowych.

Tabela referencyjna: Najmniejsze pierwiastki pierwotne

Często zadawane pytania

Co to jest pierwiastek pierwotny modulo n?

Pierwiastek pierwotny modulo n to liczba całkowita g taka, że potęgi \(g^1, g^2, \ldots, g^{\varphi(n)}\) dają wszystkie liczby całkowite względnie pierwsze z n, gdy są brane modulo n. Innymi słowy, g generuje całą grupę multiplikatywną \((\mathbb{Z}/n\mathbb{Z})^*\). Rząd multiplikatywny g modulo n jest równy funkcji totient Eulera \(\varphi(n)\).

Dla jakich wartości n istnieją pierwiastki pierwotne?

Pierwiastki pierwotne modulo n istnieją wtedy i tylko wtedy, gdy n wynosi 1, 2, 4, p^k lub 2p^k, gdzie p jest nieparzystą liczbą pierwszą, a k ≥ 1. Na przykład pierwiastki pierwotne istnieją dla n = 7 (liczba pierwsza), n = 9 (3²), n = 14 (2×7), ale NIE dla n = 8, 12, 15 lub 16.

Ile pierwiastków pierwotnych ma n?

Jeśli pierwiastki pierwotne modulo n istnieją, liczba pierwiastków pierwotnych jest równa \(\varphi(\varphi(n))\), gdzie \(\varphi\) to funkcja totient Eulera. Na przykład dla n = 13 (liczba pierwsza), \(\varphi(13) = 12\) i \(\varphi(12) = 4\), więc istnieją dokładnie 4 pierwiastki pierwotne modulo 13.

Dlaczego pierwiastki pierwotne są ważne w kryptografii?

Pierwiastki pierwotne są fundamentalne dla protokołu wymiany kluczy Diffiego-Hellmana oraz systemu szyfrowania ElGamal. W tych protokołach kryptograficznych pierwiastek pierwotny g modulo duża liczba pierwsza p jest używany jako generator. Bezpieczeństwo opiera się na trudności problemu logarytmu dyskretnego: mając \(g^x \bmod p\), obliczenie x jest trudne obliczeniowo.

Jak sprawdzić, czy g jest pierwiastkiem pierwotnym modulo n?

Aby zweryfikować, czy g jest pierwiastkiem pierwotnym mod n: (1) Oblicz \(\varphi(n)\). (2) Znajdź wszystkie czynniki pierwsze \(p_1, p_2, \ldots, p_k\) liczby \(\varphi(n)\). (3) Sprawdź, czy \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) dla każdego czynnika pierwszego \(p_i\). Jeśli wszystkie testy przejdą pomyślnie, g jest pierwiastkiem pierwotnym. Jest to znacznie szybsze niż obliczanie wszystkich potęg g.

Powiązane narzędzia