[VB.NET o multipiattaforma] Aiuto Algoritmo Lucas-Lehmer

[albeganasa]

Ciao a tutti, mi ha sempre affascinato come programmi come ORTHOS e PRIME95 facessero girare i nostri processori!
Adesso vorrei crearne uno semplice, in casa diciamo.
Mi sono studiato un pò la situazione:

Numero di Mersenne: M(n)=2^n - 1
Successione: S(n) = s(n-1)^2 -2 --> (s(0) = 4)

Un numero di mersenne è primo solo se S(n-2) divide M(n), Oppure per metterlo in termini informatici S(n-2) MOD M(n) = 0.

Adesso ho un po di domande su come iniziare!
In testa ho qualche idea...Ma i problemi sono parecchi.

Per testare se è primo il numero S(n-2) deve essere diviso per tutti i numeri M(n), con N numero primo, piu piccolo di S(n-2).
E' esatto??
Perchè Wikipedia lo spiega in modo obrobrioso...

Detto questo ciò mi spaventa:

Il test è talmente rapido e facile da programmare, che nel 1978 due studenti delle superiori dimostrarono che il numero di Mersenne 221701 − 1 è primo, battendo il precedente record del più alto numero primo allora conosciuto.

Eppure non sono cosi talpa in informatica.

Ho altre perplessità:

Che tipologia di variabile utilizzo per salvare quei numeri che diventano immensamente grandi??
Ovviamente dovrei creare un vettore per contenere i numeri Primi M(n) da dare in pasto a S(n-2), ma di che tipo e di che lunghezza??
Come imposto il ciclo che controlla il numero?
Lo posso basare su Mod=0, ma appena mi trova il mumero il ciclo finisce.
Dovrebbe essere un ciclo dentro ciclo.
Il primo ciclo calcola il numero S e lo da in pasto al secondo ciclo che calcola M, il terzo ciclo fa tutti i controlli e da come risultato se è Primo o no, e cosi via si torna al primo ciclo.
Ditemi se sbaglio oppure dico il vero.
Volevo inoltre sapere, secondo la VS esperienza, quale piattaforma è meglio utilizzare, io sono abituato con Vb.net e pensavo di utilizzare quella.
Grazie a tutti.

[albeganasa]

Up

[Noixe]

Un numero di mersenne è primo solo se S(n-2) divide M(n)

Stando a quanto scritto su Wikipedia, dove la successione è chiamata L:

M(p) deve dividere L(p-1)

L(n+1) = L(n)^2 - 2

L(p-1) = L(p-2)^2 - 2

Comunque se quegli studenti hanno dimostrato che 2^21701 - 1 è primo penso che abbiano lavorato molto sull'esponente, dato che non so con che tipo di dato si possa rappresentare tale numero, forse con librerie particolari.

Leggevo proprio su wikipedia che se n e' composto lo e' anche 2^n - 1

Quindi prova a verificare solo se n e' primo, dividendo da 2 fino alla radice quadrata di n.

Questa condizione necessaria la puoi verificare facilmente.

Ho provato a implementare ricorsivamente quella successione in C++ ma cresce troppo in fretta e non diventa più rappresentabile (ho usato long int e unsigned long int).


Ciao