Fattorizzazione di Pollard p−1

Il metodo p meno uno di Pollard è un algoritmo classico di fattorizzazione di interi che trova un fattore non banale di un modulo composto n quando almeno un fattore primo p di n ha la proprietà che p meno uno è liscio rispetto a un limite B scelto — ogni potenza prima nella fattorizzazione di p meno uno è al più B. Studenti di teoria elementare dei numeri, concorrenti CTF e apprendisti di crittografia incontrano questo algoritmo quando studiano perché i moduli RSA devono evitare primi con totienti lisci. Questa capacità esegue una ricerca deterministica di stadio uno di Pollard p−1: costruisce il prodotto di potenze prime fino a B, eleva una piccola base a tale esponente modulo n e restituisce il MCD di quella potenza meno uno con n quando il MCD è un fattore proprio.

Come Pollard p−1 trova un fattore da un p−1 liscio

Fissi un intero composto n e un limite di levigatezza positivo B. L'osservazione di Pollard è semplice: se p è un divisore primo di n e ogni potenza prima che divide p meno uno è al più B, allora il minimo comune multiplo degli interi da uno a B è un multiplo di p meno uno.

Per il piccolo teorema di Fermat, qualsiasi base a coprima con p soddisfa a alla potenza p meno uno congruente a uno modulo p, e quindi a elevata a quel grande mcm è anch'essa congruente a uno modulo p. Calcolare la stessa potenza modulo n e prendere il massimo comun divisore del risultato meno uno con n spesso produce p o un altro fattore non banale.

In pratica l'implementazione non costruisce mai l'mcm completo in modo esplicito; setaccia i primi fino a B e, per ogni primo q, eleva l'accumulatore corrente alla massima potenza di q che non supera B, tutto modulo n. Dopo ogni passo di potenza prima valuta il MCD dell'accumulatore meno uno con n. Un MCD intermedio non banale viene restituito subito.

Se il MCD collassa a n, un percorso di recupero più fine su esponenti minori tenta di isolare un solo fattore primo prima di abbandonare quella base. Si provano diverse basi piccole affinché ordini sfortunati della base due non nascondano un fattore altrimenti B-liscio. Il metodo non è un algoritmo di fattorizzazione completa: restituisce un fattore non banale e il cofattore corrispondente.

Chi necessita della fattorizzazione prima completa può alimentare ogni pezzo composto a uno strumento di fattorizzazione in primi oppure alzare B e rieseguire. Il successo è garantito solo nello scenario di p−1 liscio; grandi fattori primi di p meno uno impongono una B maggiore o un altro algoritmo, come il metodo delle curve ellittiche o il crivello quadratico.

Quando conviene questo metodo di fattorizzazione

I corsi di crittografia usano Pollard p−1 per mostrare perché i primi con predecessori lisci sono pericolosi nella generazione di parametri RSA e Diffie–Hellman; uno strumento live che accetta n e B consente all'insegnante di dimostrare una scissione in classe senza scrivere a mano l'esponenziazione modulare.

Le piattaforme CTF e dei compiti necessitano di un oracolo deterministico che o restituisce un fattore documentato per semiprimi classici come milletré con limite sedici, o rifiuta limiti troppo stretti così i correttori possono valutare sia i fattori corretti sia i ragionamenti di fallimento corretti. Gli ingegneri della sicurezza che auditano la generazione di chiavi legacy possono setacciare moduli candidati alla ricerca di fattori con p−1 liscio prima che raggiungano la produzione.

Mantenga n entro il limite di cifre, scelga B abbastanza grande da coprire il maggiore fattore primo di p meno uno per qualche primo p che divide n, e otterrà fattori riproducibili per la didattica, i write-up CTF e audit leggeri senza erigere un intero stack di algebra computazionale.