Lukuteorian laskin — alkuluvut, SYT/PYJ, modulaariaritmetiikka ja muuta
Lukuteorian laskin
Tutki alkulukuja, tekijöihin jakoa, suurimpia yhteisiä tekijöitä, modulaariaritmetiikkaa ja muuta.
Kaikki laskenta tehdään paikallisesti selaimessa — syötettäsi ei ladata.
Tila:
Alkuluvun tarkistin
Syötä luku ja napsauta "Tarkista"
Vinkki: Käyttää determinististä Miller-Rabinia lukuihin asti 264.
Napsauta "Seuraava alkuluku" tai "Edellinen alkuluku" löytääkseen lähellä olevia alkulukuja.
Alkutekijöihin jako
Syötä luku ja napsauta "Jaa tekijöihin"
Vinkki: Tukee kokonaislukuja jopa 1015. Tekijäpuun hajotelma alkulukueksponenttiesityksenä.
SYT- & PYJ-laskin
Syötä lukuja ja napsauta SYT, PYJ tai Molemmat
Vinkki: Syötä kaksi tai useampi kokonaisluku pilkulla erotettuna. SYT lasketaan Eukleideen algoritmilla; PYJ lasketaan kaavalla |a*b|/(a,b).
Modulaariaritmetiikka
Syötä a, b, m ja valitse toiminto
Vinkki: Modulaarinen potenssiinkorotus käyttää nopeaa potenssiinkorotusta (neliöi ja kerro).
Modulaarinen käänteisluku on olemassa vain, kun a ja m ovat keskenään jaottomia.
Jakajat & jakajafunktiot
Syötä luku ja napsauta "Laske"
Vinkki: Luettelee kaikki positiiviset jakajat, jakajien lukumäärän d(n), jakajien summan σ(n)
ja aidot jakajat. Tukee lukuja jopa 1012.
Eulerin funktio & aritmeettiset funktiot
Syötä luku ja napsauta "Laske"
Vinkki: Laskee Eulerin funktion φ(n), Möbiuksen funktion μ(n),
σ(n), d(n) ja muita aritmeettisia funktioita.
Alkuluvut ja kongruenssit
Alkuluvulla on täsmälleen kaksi tekijää, 1 ja itse; jokainen kokonaisluku, joka on suurempi kuin 1, jakautuu alkulukuihin täsmälleen yhdellä tavalla (aritmetiikan peruslause). Kongruenssi a ≡ b (mod n) tarkoittaa, että n jakaa luvun a−b — kellotaulun aritmetiikkaa, jossa 10 + 5 ≡ 3 (mod 12), ja SYT:n, PYJ:n ja modulaarisen potenssiinkorotuksen perusta.
Kahden suuren alkuluvun kertominen on hetkessä tehty, mutta niiden palauttaminen tulosta on laskennallisesti raskasta — tämä yksisuuntainen epäsymmetria on RSA-salauksen perusta, ja siksi 2048-bittisen moduulin φ(n) ei ole julkinen.
