PricingLoginStart free
Cryptology Academy · Lektion

Primtal og faktorisering

Lær, hvorfor primtal er grundlaget for kryptografi med offentlig nøgle

Lektion 3 af 413 trin

Primtal og faktorisering er en gratis Cryptology Academy-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Cryptology Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Cryptology Academy-kurset indeholder 4 lektioner i alt.

Velkommen

Primtal har kun 1 og sig selv som divisorer. De er multiplikationens atomer — og grundlaget for RSA, Diffie-Hellman og mange andre kryptosystemer.

Definition og eksempler

Primtal: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... Et tal er et primtal, hvis dets eneste positive divisorer er 1 og tallet selv. 1 er IKKE et primtal efter konventionen.

Aritmetikkens fundamentalsætning

Ethvert heltal > 1 kan faktoriseres til primtal på præcis én måde, bortset fra rækkefølgen. 60 = 2² × 3 × 5. Denne entydighed er det, der får kryptografi baseret på faktorisering til at fungere.

Prøvedivision

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True Det er kun nødvendigt at kontrollere op til √n — hvis der ikke findes nogen faktor under √n, er n et primtal.

Eratosthenes' si

Hvis du vil finde alle primtal op til N, starter du med en liste over tallene 2..N. Kryds multipla af 2 ud, derefter 3, så 5 osv. De resterende tal er primtal. Algoritmen kører i O(N log log N).

Primtalstest: Miller-Rabin

For store tal (2048 bit) er prøvedivision for langsom. Miller-Rabin er en probabilistisk test: Kør den 40 gange, så er sandsynligheden for en fejl < 4^(-40).

Heltalsfaktorisering

Givet n = p × q er det at finde p og q heltalsfaktoriseringsproblemet. Hvis n er 2048 bit, kræver de bedste kendte algoritmer 2^112 operationer — det er i øjeblikket praktisk umuligt.

Hvorfor RSA bruger to store primtal

RSA-modulus n = p × q. Når man kender n, men ikke p og q, er det svært at beregne den private nøgle. Sikkerheden afhænger fuldstændigt af, hvor svært det er at faktorisere n.

Generering af store primtal

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Oracle: generér et tilfældigt ulige tal, test det med Miller-Rabin, og gentag, indtil det er et primtal.

Sikre primtal og stærke primtal

Et sikkert primtal p = 2q+1, hvor q også er et primtal. Sikre primtal modstår visse angreb på DH. RSA bruger nogle gange stærke primtal for at forhindre Pollards p-1-angreb.

Primtalshuller og uendelighed

Euklid beviste i 300 f.Kr., at der findes uendeligt mange primtal. Tvillingeprimtalformodningen (at der findes uendeligt mange primtal p, p+2) er stadig ikke bevist. Vi løber aldrig tør for primtal til kryptografi.

Hurtigt tjek

Hvorfor bruger RSA store primtal?
Besvar den i den interaktive lektion

Opsamling

Du forstår nu primtal og faktorisering. Nu anvender vi Eulers totientfunktion og GCD — de sidste matematiske værktøjer, der er nødvendige før RSA.
Gratis at komme i gang

Lær Cryptology Academy med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser
67
Lektioner
261
Start gratisSe hele kurset

Ofte stillede spørgsmål

Er lektionen “Primtal og faktorisering” gratis?

Ja — hele teksten til “Primtal og faktorisering” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Cryptology Academy-kurset, skal du opgradere til CoddyKit PRO. Cryptology Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Primtal og faktorisering”?

Lær, hvorfor primtal er grundlaget for kryptografi med offentlig nøgle Du øver dig i Cryptology Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Cryptology Academy?

Der kræves ingen tidligere erfaring. Cryptology Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.

Hvor lang tid tager lektionen “Primtal og faktorisering”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Cryptology Academy-lektion?

Ja. Alle Cryptology Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

  1. Grundlæggende binær- og hexadecimalregning
  2. Grundlæggende modulær aritmetik
  3. Primtal og faktorisering
  4. GCD, Eulers phi-funktion og introduktion til talteori
← Tilbage til Cryptology Academy