Visualizza il feed RSS

Titolo provvisorio...

Algoritmi sui numeri primi: riferimenti essenziali.

Valuta questo inserimento
di pubblicato il 05-12-2019 alle 00:10 (122 Visite)
La questione dei numeri primi dal punto di vista computazionale riaffiora con una certa regolarità sui forum, mettendo regolarmente allo scoperto aree piuttosto critiche nella formazione e nella divulgazione/comunicazione scientifica.

La confusione è poi sicuramente aumentata dal fiorire di superficiali e confusi "testi" su crittografia e "sicurezza", frettolosamente commissionati ad "autori" di quart'ordine da case editrici spinte dal miraggio di facili guadagni sulla scorta dei cangianti umori e delle fastidiose mode del mainstream: o, peggio, sgangherati "tutorial" scritti in una grossolana approssimazione di lingua italiana e messi online da incompetenti che, nel migliore dei casi, hanno a loro volta "studiato" su wikipedia.

Purtroppo è un dato di fatto che le varie formule inerenti i numeri primi - elaborate nell'ambito della teoria classica del numero - sono terribilmente insoddisfacenti dal punto di vista computazionale e operativo, per i motivi succintamente richiamati qui. Allo stesso modo, gli algoritmi di fattorizzazione sono notoriamente inefficienti, come ampiamente (e stancamente) confermato anche dalla questione crittografica, che non finisce di attrarre lamer di ogni età pronti a tentare l'impossibile pur di non arrendersi di fronte all'evidenza. Sì, gli algoritmi di cifratura più gettonati si basano su funzioni non invertibili (modulari) e su prodotti di numeri primi pseudocasuali con duecento e più cifre, i quali sono oggi impossibili da fattorizzare in tempi compatibili con l'esistenza umana, appunto a causa della notevole inefficienza degli algoritmi di fattorizzazione noti. Ormai lo sanno anche i sassi.

Nondimeno, esistono algoritmi con prestazioni ampiamente accettabili per le altre principali categorie di applicazione inerenti i numeri primi: generazione tabulare (crivelli) e test di primalità, oltre ad una serie di algoritmi "minori", più specializzati, che troviamo regolarmente in applicazioni verticali, librerie numeriche e nei più famosi package di calcolo numerico e CAS (Computer Algebra System, vulgo "calcolo simbolico"). Ed è qui che la comunicazione tra ricerca e practitioners sembra avere più buchi dei famosi formaggi svizzeri.

Ad esempio, pochissimi sembrano informati del fatto (importantissimo!) che da quasi un ventennio ormai esiste e fiorisce una famiglia di test di primalità deterministici non condizionati in tempo polinomiale, basati su una pubblicazione del 2002 di tre ricercatori indiani (AKS: Agrawal, Kayal e Saxena), che trovano vasta applicazione in una nutrita schiera di implementazioni indipendenti. All'epoca la pubblicazione ricevette anche una vasta eco nel mainstream, che tuttavia pare essersi persa nell'alluvione informativa di internet, nella quale ormai da anni il rumore di fondo supera di vari ordini di grandezza il segnale vero e proprio.

Vorrei solo sottolineare l'aspetto "non condizionato" del test AKS, oltre alla fin troppo ovvia superiorità data dalla sua natura deterministica: il più longevo e (quindi) più famoso test di Miller-Rabin, oltre ad essere non deterministico, ha anche il difetto di essere basato su di una ipotesi non (ancora) dimostrata, che peraltro è uno dei Problemi del Millennio ossia la congettura sulla funzione Zeta di Riemann, che riguarda direttamente i numeri primi e la loro densità. Sebbene esistano numerosi "indizi" computazionali in favore della congettura, non è certo plausibile una dimostrazione computazionale in stile 4CP (la natura del problema e la cardinalità dell'insieme dei primi in sostanza lo impediscono a priori, a meno di trovate davvero fantasiose ed inedite) e numerosi influenti matematici ritengono che tale ipotesi sia falsa: tra questi spiccano il teorico dei numeri John E. Littlewood (collega e collaboratore del grandissimo Godfrey Hardy) e più recentemente Aleksandar Ivic.

Per il resto, lo spazio e il tempo non giocano certo in nostro favore, costringendomi ad una sintesi estrema, ai confini con l'omertosità. Mi limito dunque a fornire due tra i più affidabili riferimenti in materia: il primo è Crandall & Pomerance, "Prime numbers: a computational perspective", Springer, 2005, ISBN 9780387289793. Gli autori sono una garanzia assoluta: Carl Pomerance è uno dei protagonisti dell'ultimo mezzo secolo di ricerca in materia di primalità, mentre il fisico Richard Crandall è uno dei pionieri della computazione scientifica. Ma a rendere particolarmente appetibile il volume per l'informatico applicativo è il fatto che gli algoritmi presentati sono di una chiarezza esemplare, grazie anche alla cura posta nella scelta dello pseudocodice, e sono volutamente vicini alle implementazioni del real world anziché orientati ad una pedantesca chiarezza e astratta leggibilità scolastica (che va a scapito delle prestazioni, in genere, o finisce per essere incoerente a causa di ingiustificate scelte di economia simbolica). D'altro canto, la teoria è esposta in modo chiaro ma limitato al minimo necessario, con poche e semplici dimostrazioni, pensando soprattutto a quei practitioners con un limitato background matematico e number-theoretic ma rimandando sempre il lettore avanzato alle fonti per i necessari approfondimenti.

Il secondo testo è una monografia probabilmente molto meno accessibile per l'informatico quadratico medio, pur essendo un testo introduttivo: vale comunque la pena di familiarizzare con la teoria ivi contenuta. I metodi di crivello, infatti, sono importanti sia dal punto di vista algoritmico che da quello dimostrativo, vista anche l'ampia coincidenza tra codeste due categorie nella teoria della dimostrazione e dei modelli legata alla matematica discreta (as a rule of thumb: dimostrazioni costruttive = algoritmi).
Cojocaru & Ram Murty, "An introduction to Sieve Methods and their applications", Cambridge University Press, 2006, ISBN 9780521612753.

Ai testi citati si possono aggiungere, per ulteriori approfondimenti, anche i seguenti:
Victor Shoup, "A computational introduction to number theory and algebra"
Bressoud & Wagon, "A course in computational number theory", Wiley, 2008
Cohen, "A course in computational algebraic number theory", Springer, 1993

Come accennato in apertura, alcuni paragrafi non organici sugli algoritmi qui trattati si trovano anche in vari testi stagionali su crittografia e dintorni, che tuttavia in generale non mi sento di consigliare se non per una veloce occhiata a posteriori.

aggiornamento da 07-12-2019 a 15:30 di M.A.W. 1968

Categorie
Libri , Programmazione , Scienza