» Esercizi svolti di Matematica e Fisica

Test di primalità con il «primoriale»

Riceviamo e pubblichiamo un lavoro di Vincenzo Sambito sui test di primalità.

L'articolo esordisce con il Teorema di Wilson ponendo l'attenzione sul carico computazionale del relativo test, proponendone poi un altro basato sul primoriale che è l'analogo del fattoriale, con la differenza che mentre il fattoriale di n è il prodotto dei primi n interi naturali, il primoriale di n è il prodotto dei numeri primi minori o uguali di n. Ci si aspetta, dunque, una andamento "meno veloce" in funzione di n. Più precisamente, il primoriale di n è proporzionale al logaritmo naturale di n. Da qui la possibilità di implementare un test di primalità più veloce.

Con l'introduzione di un algoritmo generativo di numeri primi, frutto dell'appicazione di una misteriosa Ipotesi, si ottiene un risultato concreto. Quindi non solo teoremi e ipotesi ma una applicazione pratica.

L'autore poi propone la realizzazione di un database dinamico per la memorizzazione di numeri primi generati deterministicamente da un network di computer distribuiti (Progetto Neprimes). In linea di principio, non occorrerebbe nemmeno un computer dedicato a tempo pieno ma un semplice software che simula una calcolatrice (appositamente sviluppata per lavorare con grandi numeri) che gira in background nel computer lasciando potenza disponibile ad altri utilizzi. Tali software si appoggiano a una libreria nota come BigInteger. A tale scopo, l'autore suggerisce il calcolatore VincSCalc liberamente scaricabile dal link citato, corredato di apposito manuale utente.

"We received and here we publish a work by Vincenzo Sambito on primality tests. The article begins with Wilson’s Theorem, focusing on the computational load of the related test, then proposes another one based on the primorial which is analogous to the factorial, with the difference that while the factorial of n is the product of the first n natural numbers, the primorial of n is the product of the prime numbers less than or equal to n. Therefore, a “slower” trend is expected as a function of n. More precisely, the primorial of n is proportional to the natural logarithm of n. Hence the possibility of implementing a faster primality test. With the introduction of a generative algorithm for prime numbers, the result of the application of a mysterious Hypothesis, a concrete result is obtained. So not only theorems and hypotheses but a practical application.

The author then proposes the creation of a dynamic database for storing prime numbers deterministically generated by a network of distributed computers (Neprimes Project). In principle, not even a full-time dedicated computer would be needed but a simple software that simulates a calculator (specifically developed to work with large numbers) that runs in the background on the computer leaving power available for other uses. Such software relies on a library known as BigInteger. For this purpose, the author suggests the VincSCalc calculator, freely downloadable from the cited link, accompanied by a specific user manual."