Kalkulator Pierwiastka Pierwotnego

Znajdź wszystkie pierwiastki pierwotne modulo n - generatory grupy multiplikatywnej. Podaj liczbę dodatnią, by uzyskać pierwiastki pierwotne, funkcję Eulera, wizualizację grupy cyklicznej oraz weryfikację krok po kroku z tabelami potęg.

BezpłatneBez rejestracjiNatychmiastowe wyniki

Kalkulator Pierwiastka PierwotnegoWypróbuj teraz — za darmo ▼

Embed Kalkulator Pierwiastka Pierwotnego Widget

O Kalkulator Pierwiastka Pierwotnego

Kalkulator Pierwiastka Pierwotnego znajduje wszystkie pierwiastki pierwotne dla danego modułu n — liczby całkowite g, których potęgi \(g^1, g^2, \ldots, g^{\varphi(n)}\) generują każdy element grupy multiplikatywnej \((\mathbb{Z}/n\mathbb{Z})^*\). Wpisz dowolną dodatnią liczbę całkowitą, aby natychmiast zobaczyć wszystkie pierwiastki pierwotne, wartość funkcji Eulera \(\varphi(n)\), interaktywną wizualizację grupy cyklicznej, tabelę potęg oraz weryfikację najmniejszego pierwiastka pierwotnego krok po kroku.

Zastosowania pierwiastków pierwotnych

🔐

Diffie-Hellman

Protokół wymiany kluczy wykorzystuje pierwiastki pierwotne jako generatory

🔏

Szyfrowanie ElGamal

System kryptograficzny klucza publicznego oparty na logarytmach dyskretnych

✍

Podpisy cyfrowe

Podpisy DSA i Schnorra opierają się na generatorach grup cyklicznych

🎲

Liczby pseudolosowe

Liniowe generatory kongruencyjne wykorzystują właściwości pierwiastków pierwotnych

📡

Kody korekcyjne

Kody Reeda-Solomona i BCH wykorzystują generatory ciał skończonych

🧮

Teoria liczb

Rachunek indeksów, reszty kwadratowe i problemy logarytmu dyskretnego

Kluczowe pojęcia i wzory

Pojęcie	Wzór / Definicja	Opis
Pierwiastek pierwotny	\(\text{ord}_n(g) = \varphi(n)\)	Liczba całkowita g, której rząd mod n jest równy wartości funkcji Eulera
Funkcja Eulera	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	Liczba liczb całkowitych w [1, n] względnie pierwszych z n
Kryterium istnienia	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	Pierwiastki pierwotne istnieją tylko dla tych form (p - nieparzysta l. pierwsza)
Liczba pierwiastków	\(\varphi(\varphi(n))\)	Liczba pierwiastków pierwotnych, gdy one istnieją
Test pierwiastka pierwotnego	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) dla wszystkich liczb pierwszych \(p \| \varphi(n)\)	Warunek wystarczający: sprawdź tylko dla czynników pierwszych φ(n)
Generowanie wszystkich pierwiastków	\(g^k \bmod n\) gdzie \(\gcd(k, \varphi(n)) = 1\)	Po znalezieniu jednego pierwiastka g, pozostałe wynikają z tego wzoru

Zrozumienie pierwiastków pierwotnych

Pierwiastek pierwotny modulo n to liczba całkowita g taka, że zbiór \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) jest równy zbiorowi wszystkich liczb całkowitych od 1 do n−1, które są względnie pierwsze z n. W terminologii teorii grup, g jest generatorem cyklicznej grupy multiplikatywnej \((\mathbb{Z}/n\mathbb{Z})^*\). Na przykład 3 jest pierwiastkiem pierwotnym mod 7, ponieważ potęgi 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) dają każdy element zbioru {1, 2, 3, 4, 5, 6}.

Kiedy istnieją pierwiastki pierwotne?

Klasyczny wynik w teorii liczb (udowodniony przez Gaussa) mówi, że pierwiastki pierwotne modulo n istnieją wtedy i tylko wtedy, gdy n jest jedną z liczb: 1, 2, 4, p^k lub 2p^k, gdzie p jest nieparzystą liczbą pierwszą, a k ≥ 1. Dla innych wartości n grupa \((\mathbb{Z}/n\mathbb{Z})^*\) nie jest cykliczna — rozkłada się na produkt prosty grup cyklicznych zgodnie z chińskim twierdzeniem o resztach — więc żaden pojedynczy element nie może wygenerować całej grupy. Na przykład \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) nie posiada pierwiastka pierwotnego.

Jak efektywnie znaleźć pierwiastki pierwotne

Standardowy algorytm działa w dwóch fazach. Faza 1: znalezienie najmniejszego pierwiastka pierwotnego metodą prób. Dla każdego kandydata g zaczynając od 2, oblicz \(g^{\varphi(n)/p} \bmod n\) dla każdego czynnika pierwszego p liczby \(\varphi(n)\). Jeśli żaden z tych wyników nie jest równy 1, wówczas g jest pierwiastkiem pierwotnym. W praktyce najmniejszy pierwiastek pierwotny zazwyczaj jest małą liczbą — przypuszcza się, że wynosi \(O(n^\epsilon)\) dla dowolnego \(\epsilon > 0\). Faza 2: gdy znany jest jeden pierwiastek pierwotny g, wszystkie pozostałe pierwiastki to \(g^k \bmod n\), gdzie \(\gcd(k, \varphi(n)) = 1\), co daje łącznie dokładnie \(\varphi(\varphi(n))\) pierwiastków pierwotnych.

Jak używać Kalkulatora Pierwiastka Pierwotnego

Wprowadź moduł n: Wpisz dodatnią liczbę całkowitą w polu wejściowym lub kliknij jeden z przycisków szybkich przykładów, aby automatycznie wypełnić wartość.
Kliknij Znajdź Pierwiastki Pierwotne: Naciśnij przycisk, aby obliczyć wszystkie pierwiastki pierwotne modulo n.
Przejrzyj wyniki: Zobacz liczbę pierwiastków, kompletną listę pierwiastków pierwotnych, wartość funkcji Eulera, rząd grupy oraz informację, czy pierwiastki pierwotne istnieją dla Twojego n.
Eksploruj wizualizację: Dla n ≤ 100 interaktywne koło grupy cyklicznej pokazuje, jak każdy pierwiastek pierwotny generuje całą grupę poprzez swoje potęgi. Kliknij na dowolny kafelek pierwiastka, aby zobaczyć animację jego cyklu na kole.
Studiuj tabelę potęg: Siatka pokazuje g^k mod n dla k = 1, 2, …, φ(n), przy czym pierwiastki pierwotne i element neutralny są wyróżnione różnymi kolorami.

Pierwiastki pierwotne w kryptografii

Pierwiastki pierwotne odgrywają kluczową rolę w nowoczesnej kryptografii. W wymianie kluczy Diffie-Hellman dwie strony uzgadniają dużą liczbę pierwszą p i pierwiastek pierwotny g mod p, a następnie wymieniają klucze publiczne g^a mod p i g^b mod p. Wspólny sekret g^ab mod p jest praktycznie niemożliwy do wyznaczenia przez podsłuchującego, ponieważ obliczanie logarytmów dyskretnych w dużych grupach cyklicznych jest uważane za trudne obliczeniowo. Podobnie szyfrowanie ElGamal oraz algorytm podpisu cyfrowego (DSA) opierają się na trudności problemu logarytmu dyskretnego w grupach generowanych przez pierwiastki pierwotne.

FAQ

Co to jest pierwiastek pierwotny modulo n?

Pierwiastek pierwotny modulo n to liczba całkowita g taka, że potęgi g¹, g², …, g^φ(n) modulo n dają każdą liczbę całkowitą względnie pierwszą z n dokładnie raz. Równoważnie, g ma rząd multiplikatywny równy φ(n), co oznacza, że g generuje całą grupę multiplikatywną (Z/nZ)*.

Dla jakich wartości n istnieją pierwiastki pierwotne?

Pierwiastki pierwotne istnieją wtedy i tylko wtedy, gdy n wynosi 1, 2, 4, p^k lub 2p^k, gdzie p jest nieparzystą liczbą pierwszą, a k jest dodatnią liczbą całkowitą. Na przykład n = 7 (liczba pierwsza), n = 9 (3²) i n = 14 (2 × 7) mają pierwiastki pierwotne, ale n = 8, n = 12 i n = 15 ich nie posiadają.

Ile pierwiastków pierwotnych ma liczba n?

Jeśli n posiada pierwiastki pierwotne, to liczba pierwiastków pierwotnych modulo n wynosi φ(φ(n)), gdzie φ to funkcja Eulera. Na przykład n = 7 ma φ(φ(7)) = φ(6) = 2 pierwiastki pierwotne, którymi są 3 i 5.

Jak znaleźć pierwiastki pierwotne?

Aby znaleźć pierwiastki pierwotne n: najpierw oblicz φ(n) i rozłóż ją na czynniki. Następnie dla każdego kandydata g względnie pierwszego z n sprawdź, czy g^(φ(n)/p) nie przystaje do 1 mod n dla każdego czynnika pierwszego p liczby φ(n). Jeśli wszystkie testy przejdą pomyślnie, g jest pierwiastkiem pierwotnym. Pozostałe pierwiastki można znaleźć jako g^k mod n, gdzie nwd(k, φ(n)) = 1.

Dlaczego pierwiastki pierwotne są ważne w kryptografii?

Pierwiastki pierwotne są kluczowe dla wymiany kluczy Diffie-Hellman, szyfrowania ElGamal oraz algorytmów podpisu cyfrowego. Zapewniają one trudność problemu logarytmu dyskretnego, co stanowi podstawę bezpieczeństwa tych protokołów kryptograficznych. Pierwiastek pierwotny generuje wszystkie elementy grupy, maksymalizując przestrzeń poszukiwań dla atakujących.

Cytuj ten materiał, stronę lub narzędzie w następujący sposób:

"Kalkulator Pierwiastka Pierwotnego" na https://MiniWebtool.com/pl/kalkulator-pierwiastka-pierwotnego/ z MiniWebtool, https://MiniWebtool.com/

przez zespół miniwebtool. Aktualizacja: 2026-04-16

Dostępne API dla deweloperów: Uruchom to narzędzie z aplikacji, automatyzacji lub agenta za pomocą jednego żądania HTTP JSON. Zobacz dokumentację API

Możesz także wypróbować nasz AI Rozwiązywacz Matematyczny GPT, aby rozwiązywać swoje problemy matematyczne poprzez pytania i odpowiedzi w języku naturalnym.