Kalkulator teorii liczb — liczby pierwsze, NWD/NWW, arytmetyka modularna i inne
Kalkulator teorii liczb
Badaj liczby pierwsze, rozkład na czynniki, największe wspólne dzielniki, arytmetykę modularną i inne. Wszystkie obliczenia są wykonywane lokalnie w przeglądarce — Dane nigdy nie są wysyłane.
Tryb:
Sprawdzanie liczb pierwszych
Wpisz liczbę i kliknij „Sprawdź”
Wskazówka: używa deterministycznego testu Millera-Rabina dla liczb do 264. Kliknij „Następna liczba pierwsza” lub „Poprzednia liczba pierwsza”, aby znaleźć pobliskie liczby pierwsze.
Rozkład na czynniki pierwsze
Wpisz liczbę i kliknij „Rozłóż na czynniki”
Wskazówka: obsługuje liczby całkowite do 1015. Dekompozycja drzewa czynników z przedstawieniem w postaci potęg liczb pierwszych.
Kalkulator NWD i NWW
Wpisz liczby i kliknij NWD, NWW lub Oba
Wskazówka: wpisz 2 lub więcej liczb całkowitych oddzielonych przecinkami. NWD liczy algorytmem Euklidesa; NWW jest obliczane jako |a*b|/(a,b).
Arytmetyka modularna
Wpisz a, b, m i kliknij operację
Wskazówka: potęgowanie modularne używa szybkiego potęgowania (kwadrat-i-mnóż). Odwrotność modularna istnieje tylko wtedy, gdy a i m są względnie pierwsze.
Dzielniki i funkcje dzielników
Wpisz liczbę i kliknij „Oblicz”
Wskazówka: wypisuje wszystkie dodatnie dzielniki, liczbę dzielników d(n), sumę dzielników σ(n) i dzielniki właściwe. Obsługuje liczby do 1012.
Funkcja Eulera i funkcje arytmetyczne
Wpisz liczbę i kliknij „Oblicz”
Wskazówka: oblicza funkcję Eulera φ(n), funkcję Möbiusa μ(n), σ(n), d(n) i pokrewne funkcje arytmetyczne.
Liczby pierwsze i kongruencje
Liczba pierwsza ma dokładnie dwa dzielniki: 1 i samą siebie; każda liczba całkowita większa od 1 rozkłada się na czynniki pierwsze dokładnie na jeden sposób (zasadnicze twierdzenie arytmetyki). Kongruencja a ≡ b (mod n) oznacza, że n dzieli a−b — arytmetyka na tarczy zegara, gdzie 10 + 5 ≡ 3 (mod 12), i podstawa NWD, NWW oraz potęgowania modularnego.
Pomnożenie dwóch dużych liczb pierwszych jest natychmiastowe, ale odzyskanie ich z iloczynu jest obliczeniowo brutalne — ta jednokierunkowa asymetria stoi za szyfrowaniem RSA i dlatego φ(n) modułu 2048-bitowego nie jest publiczne.
