Qualcuno sa usare wolfram?

[marione111]

Qui ho trovato una descrizione del test di lucas-lehmer. http://mathworld.wolfram.com/Lucas-LehmerTest.html

Sembra sia possibile scaricare un file (notebook) con il codice. Ma non ne capisco il funzionamento. Qualcuno è in grado di farlo funzionare? Non riesco a trovare un programma di verifica dei numeri primi, né utilizzando il test di lucas-lehmer né altri.

[minomic]

Ciao, ho velocemente buttato giù un programmino in C++ per eseguire il test di Lucas-Lehmer. Ti lascio il codice:

#include <iostream>
#include <cmath>

using namespace std;

long int termine_successione(unsigned long long int indice, unsigned long long int mersenne)
{
    unsigned long long int termine = 4;
    for(unsigned long long int i=1; i<indice; i++)
    {
        termine = (termine*termine-2)%mersenne;
    }
    return termine;
}

bool isPrimo(unsigned long long int num)
{
    for(unsigned long long int i=2; i<((unsigned long long int)sqrt(num)+1); i++)
    {
        if(num % i == 0)
            return false;
    }
    return true;
}


bool test_lucas_lehmer(unsigned long long int p)
{
    unsigned long long int mersenne = pow(2, p)-1;
    cout << "Mersenne = " << mersenne << endl;
    unsigned long long int L = termine_successione(p-1, mersenne);
    cout << "L = " << L << endl;
    if(L % mersenne == 0) return true;
    return false;
}

int main()
{
    unsigned long long int numero;
    cout << "Inserire un numero primo p: ";
    cin >> numero;
    if(!isPrimo(numero))
    {
        cout << "Il numero inserito non e' primo!" << endl;
        return -1;
    }

    if(test_lucas_lehmer(numero))
    {
        cout << "Numero primo" << endl;
    }
    else
    {
        cout << "Numero NON primo" << endl;
    }

    return 0;
}

Se conosci anche solo un po' di programmazione lo puoi modificare come vuoi.
Il programma mi sembra funzionare correttamente, ad esempio ho provato ad inserire 3 e mi dice che 7 è un numero primo; inserendo 11 invece dice che 2047 (il corrispondente numero di Mersenne) non è primo. Per altre informazioni puoi guardare qui.

Nota 1: queste righe le ho scritte veramente in pochi minuti, quindi non è assolutamente da escludere che ci siano errori. A te (o chi vuole) il compito di trovarli e correggerli (o almeno segnalarli).

Nota 2: ho utilizzato unsigned long long int per avere la possibilità di operare su numeri anche molto grandi. Tuttavia questo approccio è comunque limitato: il valore massimo rappresentabile è, se non sbaglio, $2^64$. Per questo motivo il massimo numero primo che puoi inserire è 61. Se inserisci il numero primo successivo (cioè 67) allora il software non riesce a calcolare il numero di Mersenne corrispondente.



P.S. Nota 3: il test di Lucas-Lehmer non è un generico test di primalità, ma un test di primalità per i numeri di Mersenne (e solo quelli). Se vuoi un test generico, allora devi utilizzare un altro approccio.

[marione111]

"minomic":Ciao, ho velocemente buttato giù un programmino in C++ per eseguire il test di Lucas-Lehmer. Ti lascio il codice:

#include <iostream>
#include <cmath>

using namespace std;

long int termine_successione(unsigned long long int indice, unsigned long long int mersenne)
{
    unsigned long long int termine = 4;
    for(unsigned long long int i=1; i<indice; i++)
    {
        termine = (termine*termine-2)%mersenne;
    }
    return termine;
}

bool isPrimo(unsigned long long int num)
{
    for(unsigned long long int i=2; i<((unsigned long long int)sqrt(num)+1); i++)
    {
        if(num % i == 0)
            return false;
    }
    return true;
}


bool test_lucas_lehmer(unsigned long long int p)
{
    unsigned long long int mersenne = pow(2, p)-1;
    cout << "Mersenne = " << mersenne << endl;
    unsigned long long int L = termine_successione(p-1, mersenne);
    cout << "L = " << L << endl;
    if(L % mersenne == 0) return true;
    return false;
}

int main()
{
    unsigned long long int numero;
    cout << "Inserire un numero primo p: ";
    cin >> numero;
    if(!isPrimo(numero))
    {
        cout << "Il numero inserito non e' primo!" << endl;
        return -1;
    }

    if(test_lucas_lehmer(numero))
    {
        cout << "Numero primo" << endl;
    }
    else
    {
        cout << "Numero NON primo" << endl;
    }

    return 0;
}

Se conosci anche solo un po' di programmazione lo puoi modificare come vuoi.
Il programma mi sembra funzionare correttamente, ad esempio ho provato ad inserire 3 e mi dice che 7 è un numero primo; inserendo 11 invece dice che 2047 (il corrispondente numero di Mersenne) non è primo. Per altre informazioni puoi guardare qui.

Nota 1: queste righe le ho scritte veramente in pochi minuti, quindi non è assolutamente da escludere che ci siano errori. A te (o chi vuole) il compito di trovarli e correggerli (o almeno segnalarli).

Nota 2: ho utilizzato unsigned long long int per avere la possibilità di operare su numeri anche molto grandi. Tuttavia questo approccio è comunque limitato: il valore massimo rappresentabile è, se non sbaglio, $2^64$. Per questo motivo il massimo numero primo che puoi inserire è 61. Se inserisci il numero primo successivo (cioè 67) allora il software non riesce a calcolare il numero di Mersenne corrispondente.



P.S. Nota 3: il test di Lucas-Lehmer non è un generico test di primalità, ma un test di primalità per i numeri di Mersenne (e solo quelli). Se vuoi un test generico, allora devi utilizzare un altro approccio.

Ti ringrazio moltissimo.
Purtroppo però non conosco nulla di programmazione (ho giusto qualche reminiscenza delle basi del pascal... di 10 anni fa quando andavo a scuola XD), e mi rendo conto che la creazione di un programma del genere va oltre le mie possibilità. ad esempio già il fatto di non sapere come aumentare il massimo numero da testare è un problema, perché vorrei usare il programma per numeri enormi, di cui non si conosce la primalità, a fini di ricerca.

Ti ringrazio comunque per l'aiuto, ma devo desistere... non mi resta nient'altro che installare una versione di Linux per usare i programmi esistenti (che sono testati e ideati proprio per i miei scopi). Purtroppo questo sarà un altro problema perché con Linux non so dove mettere mano