Matematica: problemi aperti
Claudio Procesi
Prima di parlare dei problemi aperti nella matematica è bene riflettere su quelli che ne hanno segnato la storia passata. Sono infatti proprio questi che [...] problema sui primi (che ha avuto recentemente nuova attenzione dopo il lavoro di Manindra Agrawal e altri sul test polinomiale di primalità e la discussione del problema P verso NP) è se esistano infiniti primi di Sophie Germain, ovvero della forma p ...
Leggi Tutto
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] proposto da Michael O. Rabin nel 1980 per decidere se un dato numero è un numero primo (test di primalità), un problema per il quale allora non era noto alcun algoritmo polinomiale. Altri algoritmi probabilistici sono stati realizzati per risolvere ...
Leggi Tutto
L'Ottocento: matematica. Teoria dei numeri
Catherine Goldstein
Teoria dei numeri
Le tappe più significative dello sviluppo di un settore della scienza o dell'arte si accordano raramente con la suddivisione [...] +1 ma non i termini il cui indice divide p+1, allora p è primo. Questo criterio è particolarmente adatto per dimostrare la primalità di numeri quali quelli di Mersenne (ossia di numeri del tipo 2k−1) e le sue versioni più recenti fanno parte del gran ...
Leggi Tutto
La grande scienza. Teoria dei numeri
Anatolij A. Karatsuba
Teoria dei numeri
La teoria dei numeri o, adottando una locuzione di Carl Friedrich Gauss (1777-1855), l'aritmetica superiore, è lo studio [...] '. Proprio alla crittografia deve la sua comparsa la teoria 'computazionale' dei numeri che studia il 'riconoscimento' della primalità di numeri 'grandi', cioè la fattorizzazione di quelli composti.
Negli ultimi decenni è stata ottenuta una serie di ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1971-1980
1971-1980
1971
I problemi NP-completi. L'informatico americano Stephen Cook dà il primo esempio di problema algoritmico NP-completo. La classe NP [...] tecnica appare ancora imperfetta e si affermerà solo a metà degli anni Ottanta.
1976
Test probabilistico di primalità. Il logico israeliano Michael Rabin, basandosi sui risultati aritmetici di Gary Miller, propone un algoritmo probabilistico per ...
Leggi Tutto
primalita
primalità s. f. [lat. mod. primalitas, der. del lat. primus «primo»; cfr. fr. primauté]. – 1. Nella filosofia di T. Campanella (1568-1639), ciascuno dei principî o proprietà trascendentali dell’essere, e cioè la potenza, la sapienza...