0Pricing
Cryptology Academy · Lezione

MCD, funzione totiente di Eulero e introduzione alla teoria dei numeri

Applichi il MCD e la funzione totiente di Eulero a problemi crittografici reali.

MCD, funzione totiente di Eulero e introduzione alla teoria dei numeri è una lezione Cryptology Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Cryptology Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Cryptology Academy include 4 lezioni in totale.

Benvenuto

Il MCD e la funzione totiente di Eulero sono strumenti essenziali in RSA e in molti altri sistemi a chiave pubblica. Li padroneggeremo attraverso alcuni esempi.

Massimo comune divisore (GCD)

GCD(a, b) è il più grande intero che divide sia a sia b senza resto. GCD(12, 8) = 4. Se GCD(a, m) = 1, si dice che a e m sono coprimi o relativamente primi.

Algoritmo euclideo

GCD(a, b) = GCD(b, a mod b), con caso base 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

Algoritmo euclideo esteso

La versione estesa trova interi x e y tali che ax + by = GCD(a,b). Quando GCD(a,m)=1, x è l'inverso modulare di a modulo m. È così che RSA calcola le chiavi private.

Funzione totiente di Eulero φ(n)

φ(n) conta gli interi da 1 a n che sono coprimi con n. φ(10) = 4 perché {1, 3, 7, 9} sono coprimi con 10. φ(p) = p-1 per ogni primo p.

Totiente di un prodotto

Per RSA: n = p×q (p,q primi). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Esempio: p=5, q=11: φ(55) = 4×10 = 40. Per questo fattorizzare n compromette RSA: rivela φ(n).

Teorema di Eulero

Se GCD(a,n)=1: a^φ(n) ≡ 1 (mod n). Questa è la base matematica della decifrazione RSA: M = C^d mod n perché e×d ≡ 1 (mod φ(n)).

Calcolo di d in RSA

Scegliere e = 65537 (esponente pubblico RSA comune). Calcolare d = e^(-1) mod φ(n) usando l'algoritmo euclideo esteso. Verificare che e×d mod φ(n) == 1.

Il totiente in 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)

Lambda di Carmichael

RSA moderno utilizza la funzione lambda di Carmichael λ(n) = lcm(p-1, q-1) invece di φ(n). Fornisce un modulo equivalente più piccolo. PKCS#1 v2 e NIST raccomandano λ(n).

Riepilogo dell'applicazione pratica

MCD: verificare la coprimalità di e con φ(n). Euclideo esteso: calcolare la chiave privata d. Totiente: determinare il gruppo degli esponenti per l'esponenziazione modulare. Tutti e tre vengono utilizzati in ogni generazione di chiavi RSA.

Verifica rapida

Per RSA con p=7 e q=11, qual è φ(n)?

Riepilogo

Eccellente! MCD, algoritmo euclideo e totiente di Eulero fanno ora parte del Suo kit di strumenti. Ora studieremo XOR e le operazioni bit a bit, i mattoni fondamentali dei cifrari simmetrici.

Domande Frequenti

La lezione «MCD, funzione totiente di Eulero e introduzione alla teoria dei numeri» è gratuita?

Sì — il testo completo di «MCD, funzione totiente di Eulero e introduzione alla teoria dei numeri» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Cryptology Academy, passa a CoddyKit PRO. Il corso Cryptology Academy include 4 lezioni in totale.

Cosa imparerò in «MCD, funzione totiente di Eulero e introduzione alla teoria dei numeri»?

Applichi il MCD e la funzione totiente di Eulero a problemi crittografici reali. Eserciti Cryptology Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Cryptology Academy?

Non è richiesta alcuna esperienza precedente. Cryptology Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.

Quanto tempo richiede la lezione «MCD, funzione totiente di Eulero e introduzione alla teoria dei numeri»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Cryptology Academy?

Sì. Ogni lezione Cryptology Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Fondamenti del binario e dell'esadecimale
  2. Fondamenti dell'aritmetica modulare
  3. Numeri primi e fattorizzazione
  4. MCD, funzione totiente di Eulero e introduzione alla teoria dei numeri
← Torna a Cryptology Academy