Cryptology Academy · leksjon

GCD, Eulers totientfunksjon og en innføring i tallteori

Bruk GCD og Eulers totientfunksjon på praktiske kryptografiproblemer.

Leksjon 4 av 413 trinn

GCD, Eulers totientfunksjon og en innføring i tallteori er en gratis leksjon i Cryptology Academy på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Cryptology Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Cryptology Academy inneholder totalt 4 leksjoner.

Velkommen

GCD og Eulers totientfunksjon er viktige verktøy i RSA og mange andre systemer med offentlig nøkkel. La oss få kontroll på dem gjennom eksempler.

Største felles divisor (GCD)

GCD(a, b) er det største heltallet som deler både a og b uten rest. GCD(12, 8) = 4. Hvis GCD(a, m) = 1, sier vi at a og m er innbyrdes primiske eller relativt primiske.

Euklidsk algoritme

GCD(a, b) = GCD(b, a mod b), med basistilfellet GCD(a, 0) = a. GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

Utvidet euklidsk algoritme

Den utvidede versjonen finner heltallene x og y slik at ax + by = GCD(a,b). Når GCD(a,m)=1, er x den modulære inversen til a modulo m. Slik beregner RSA private nøkler.

Eulers totientfunksjon φ(n)

φ(n) teller heltallene fra 1 til n som er innbyrdes primiske med n. φ(10) = 4 fordi {1, 3, 7, 9} er innbyrdes primiske med 10. φ(p) = p-1 for alle primtall p.

Totientfunksjonen til et produkt

For RSA: n = p×q (p,q er primtall). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Eksempel: p=5, q=11: φ(55) = 4×10 = 40. Dette er grunnen til at faktorisering av n bryter RSA — den avslører φ(n).

Eulers teorem

Hvis GCD(a,n)=1: a^φ(n) ≡ 1 (mod n). Dette er det matematiske grunnlaget for RSA-dekryptering: M = C^d mod n fordi e×d ≡ 1 (mod φ(n)).

Beregne d i RSA

Velg e = 65537 (en vanlig offentlig RSA-eksponent). Beregn d = e^(-1) mod φ(n) ved hjelp av den utvidede euklidske algoritmen. Kontroller at e×d mod φ(n) == 1.

Totientfunksjonen i Python

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Carmichaels lambda

Moderne RSA bruker Carmichaels lambda-funksjon λ(n) = lcm(p-1, q-1) i stedet for φ(n). Den gir en mindre, ekvivalent modulus. PKCS#1 v2 og NIST anbefaler λ(n).

Oppsummering av praktisk bruk

GCD: kontroller at e er innbyrdes primisk med φ(n). Utvidet euklidsk algoritme: beregn den private nøkkelen d. Totientfunksjon: bestem eksponentgruppen for modulær eksponentiering. Alle tre brukes ved hver RSA-nøkkelgenerering.

Kontrollspørsmål

For RSA med p=7 og q=11, hva er φ(n)?

Besvar den i den interaktive leksjonen

Oppsummering

Utmerket! GCD, den euklidske algoritmen og Eulers totientfunksjon er nå en del av verktøykassen Deres. Deretter studerer vi XOR og bitvise operasjoner — byggesteinene i symmetriske chifre.

Gratis å komme i gang

Lær deg Cryptology Academy med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 67
Leksjoner: 261

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «GCD, Eulers totientfunksjon og en innføring i tallteori» gratis?

Ja – hele teksten i «GCD, Eulers totientfunksjon og en innføring i tallteori» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Cryptology Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Cryptology Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «GCD, Eulers totientfunksjon og en innføring i tallteori»?

Bruk GCD og Eulers totientfunksjon på praktiske kryptografiproblemer. Du øver på Cryptology Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Cryptology Academy?

Ingen tidligere erfaring er nødvendig. Cryptology Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «GCD, Eulers totientfunksjon og en innføring i tallteori»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Cryptology Academy-leksjonen?

Ja. Alle Cryptology Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

Grunnleggende binær- og heksadesimaltall
Grunnleggende modulær aritmetikk
Primtall og faktorisering
GCD, Eulers totientfunksjon og en innføring i tallteori

← Tilbake til Cryptology Academy