PricingLoginStart free
Cryptology Academy · Lektion

Primtal och faktorisering

Lär dig varför primtal är grunden för kryptografi med publika nycklar

Lektion 3 av 413 steg

Primtal och faktorisering är en gratis lektion i Cryptology Academy på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Cryptology Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Cryptology Academy innehåller totalt 4 lektioner.

Välkommen

Primtal är bara delbara med 1 och sig själva. De är multiplikationens byggstenar — och grunden för RSA, Diffie-Hellman och många andra kryptosystem.

Definition och exempel

Primtal: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... Ett tal är ett primtal om dess enda positiva delare är 1 och talet självt. 1 är enligt konvention INTE ett primtal.

Aritmetikens fundamentalsats

Varje heltal > 1 kan faktoriseras till primtal på exakt ett sätt (bortsett från ordningen). 60 = 2² × 3 × 5. Det är denna entydighet som gör faktoriseringsbaserad kryptografi möjlig.

Prövning genom division

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 räcker att kontrollera upp till √n — om ingen faktor hittas under √n är n ett primtal.

Eratosthenes såll

För att hitta alla primtal upp till N: börja med en lista över talen 2..N. Stryk över multiplarna av 2, sedan 3, sedan 5 och så vidare. De tal som återstår är primtal. Körs i O(N log log N).

Primtalstest: Miller-Rabin

För stora tal (2048 bitar) är prövning genom division för långsam. Miller-Rabin är ett sannolikhetsbaserat test: kör det 40 gånger så är sannolikheten för fel < 4^(-40).

Heltalsfaktorisering

Givet n = p × q är det problem som består i att hitta p och q ett heltalsfaktoriseringsproblem. Om n är 2048 bitar kräver de bästa kända algoritmerna 2^112 operationer — för närvarande praktiskt ogenomförbart.

Varför RSA använder två stora primtal

RSA-modulen n = p × q. Om man känner till n men inte p och q är det svårt att beräkna den privata nyckeln. Säkerheten bygger helt på svårigheten att faktorisera n.

Generera stora primtal

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Oracle: generate random odd number, test with Miller-Rabin, repeat until prime.

Säkra och starka primtal

Ett säkert primtal p = 2q+1 där q också är ett primtal. Säkra primtal står emot vissa attacker mot DH. RSA använder ibland starka primtal för att förhindra Pollards p−1-attack.

Primtalsluckor och oändlighet

Euklides bevisade år 300 f.Kr. att det finns oändligt många primtal. Förmodan om tvillingprimtal (att primtal p och p+2 förekommer oändligt många gånger) är fortfarande obevisad. Vi får aldrig slut på primtal för kryptografi.

Snabbkontroll

Varför använder RSA stora primtal?
Besvara frågan i den interaktiva lektionen

Sammanfattning

Ni förstår nu primtal och faktorisering. Därefter tillämpar vi Eulers phi-funktion och SGD — de sista matematiska verktygen som behövs före RSA.
Gratis att börja

Lär dig Cryptology Academy med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser
67
Lektioner
261
Börja lära dig gratisVisa hela kursen

Vanliga frågor

Är lektionen ”Primtal och faktorisering” gratis?

Ja – hela texten till ”Primtal och faktorisering” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Cryptology Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Cryptology Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”Primtal och faktorisering”?

Lär dig varför primtal är grunden för kryptografi med publika nycklar Ni övar på Cryptology Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Cryptology Academy?

Du behöver inga förkunskaper. Utbildningen i Cryptology Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.

Hur lång tid tar lektionen ”Primtal och faktorisering”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Cryptology Academy-lektionen?

Ja. Varje Cryptology Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

  1. Grunderna i binära och hexadecimala tal
  2. Grunderna i modulär aritmetik
  3. Primtal och faktorisering
  4. GCD, Eulers totientfunktion och en introduktion till talteori
← Tillbaka till Cryptology Academy