Programma Numeri Primi su commissione

di il
50 risposte

Programma Numeri Primi su commissione

Mi sono imbattuto sul sito dell'EFF *** ma più che altro per semplice curiosità , vorrei avere tra le mani un programmino che riuscisse a "generare" e fattorizzare numeri di dimensioni molto grandi esempio 200 cifre , La domanda è qualcuno di voi ha idea di come si sviluppi e ovviamente dietro un lauto compenso da concordare , progettare un programma del genere ? Io conosco già il programma PARI che lavora con cifre molto grandi , ma intendevo avere il sorgente e capirne il meccanismo , per poi dopo ampliarlo ( proprio come il programma PARI per intenderci ) ,preferirei un programma scritto in Assembly ovviamente. Ovviamente se non fosse possibile un programma completo , anche il semplice meccanismo in un qualsiasi linguaggio andrebbe bene , e il tutto avviene sempre dietro compenso.

50 Risposte

  • Re: Programma Numeri Primi su commissione

    Ciao, ti chiedo di utilizzare i link a risorse esterne solo se strettamente necessario.
    Il fatto che ti sei imbattuto per sbaglio su un sito mentre cercavi un programmino per la generazione di numeri non è un motivo valido
    per postarne il link.

    Grazie
  • Re: Programma Numeri Primi su commissione

    Ok , ho capito
  • Re: Programma Numeri Primi su commissione

    "generare" e "fattorizzare" son due cose moooolto diverse.
    Nel secondo caso gli algoritmi sono pochi, e davvero poco efficienti
  • Re: Programma Numeri Primi su commissione

    Si hai ragione intendevo generare la fattorizzazione di un numero molto grande e determinare quindi se è primo in quel senso , mi sono espresso male.
    Se credi che sia facile , ti sbagli comunque e tanto anche.
  • Re: Programma Numeri Primi su commissione

    aleasia ha scritto:


    intendevo generare la fattorizzazione di un numero molto grande e determinare quindi se è primo in quel senso
    A prescindere dal fatto che neppure questa "spiegazione" elimina l'ambiguità e indica se si desidera un test di primalità oppure un algoritmo di fattorizzazione, prima di intraprendere qualsiasi discussione o addirittura pensare di "commissionare" un programma per studiarne i sorgenti è opportuno studiare a fondo la letteratura esistente in materia.

    In un caso del genere, esiste fortunatamente un Testo Sacro, aggiornato e sostanzialmente insuperato, referenziato ad esempio in questo post assieme ad una quantità di altre informazioni massimamente utili, che riassumono il quadro attuale del settore.
  • Re: Programma Numeri Primi su commissione

    Intanto prima di sparare cose senza senso che non ho mai detto , quella di voler vincere un test di primalità , vorrei precisare che l'EFF ha offerto quei premi in danaro solo per i numeri dei primi di mersenne . Io in sostanza vorrei solo conoscere come funziona un programma come PARI ad esempio , e niente di più , dopo quello che ci devo fare sono affari miei , e credimi so benissimo quello che dico , comunque grazie.
  • Re: Programma Numeri Primi su commissione

    aleasia ha scritto:


    Intanto prima di sparare cose senza senso che non ho mai detto , quella di voler vincere un test di primalità .
    Mi sembra che non ti abbia scritto questo ma "se si desidera un test di primalità oppure un algoritmo di fattorizzazione" ......
  • Re: Programma Numeri Primi su commissione

    Allora non ho capito , chiedo scusa , comunque c'è da dire anche che quei due libri che tu dici essere Testi sacri nel post parlano solo esclusivamente di numeri primi credo e delle relazioni tra essi ; ma questo non cambia il perché vorrei capire il funzionamento interno del programma , il programma deve innanzitutto fattorizzare numeri molto grandi , e quello che cerco è appunto un algoritmo , per test di primalità nel senso determinare se un numero è Primo dato un numero , poi visualizzare i fattori , è perfetto , è come PARI ma non necessariamente ; Quello che più mi interessa sono le operazioni tra numeri molto grandi + * - /
  • Re: Programma Numeri Primi su commissione

    Ti segnalo che stabilire se un numero è primo (... diciamo un test di primalità, anche se diciamo di tipo probabilistico) è diverso da fattorizzarlo.
    ---
    Andiamo nel concreto: hai un numero intero positivo e vuoi fattorizzarlo?
    O magari sai già che il numero è il prodotto di DUE numeri primi e vuoi sapere quali siano?
  • Re: Programma Numeri Primi su commissione

    Esatto solo operazioni , lasciamo perdere fattorizzare che sta venendo fuori un casino con questa parola , non ho mai fatto tanto casino in quattro righe
  • Re: Programma Numeri Primi su commissione

    aleasia ha scritto:


    esatto solo operazioni , lasciamo perdere fattorizzare che sta venendo fuori un casino con questa parola , non ho mai fatto tanto casino in quattro righe
    Non è "casino", si tratta di argomenti ben noti e anche oggetto di ricerche.
    Siccome il titolo del topic è "programma numeri primi" suppongo che tu voglia scomporre (fattorizzare) il prodotto di due numeri primi (in sostanza per un qualche meccanismo classico di chiave pubblica alla RSA o cugini vari).

    Come si fa? Semplice, non si fa.
    Non esistono algoritmi "furbi" per farlo (*nota: in realtà ce ne sono polinomiali per computer quantistici, ma dò per scontato che tu non ne abbia uno sottomano), sono (chi più, chi meno) derivazioni del mitico crivello di eratostene.

    In sostanza si procedere esaustivamente, provando tutti i numeri (* con qualche ottimizzazione, ma di poco conto in relazione alla complessità asintotica non-polinomiale) e sperando per il meglio.

    Se specifichi esattamente quale sia il tuo problema è facile indicare i tanti algoritmi già belli e pronti che puoi studiare tranquillamente (ma, come detto, sono più o meno evoluzioni del crivello, ci sono tante analisi teoriche che provano che alla fin fine è quello il sistema più efficiente conosciuto)
  • Re: Programma Numeri Primi su commissione

    Perchè questi 3 problemi sono ben diversi...

    1) stabilire se un numero è primo (al limite con una certa probabilità)
    2) moltiplicare due numeri primi (o non primi) anche molto grandi
    3) fattorizzare un numero dato dal prodotto di due numeri primi molto grandi nei due numeri "originali"

    1) è facile
    2) è relativamente facile (è una questione di implementazione efficiente, più che di problemi teorici)
    3) è difficile, si spera difficilissimo.
  • Re: Programma Numeri Primi su commissione

    Riformulo la domanda : Vorrei vedere il codice di un programma che sappia fare le operazioni + x - / con numeri di anche 200 cifre e basta.

    A = 200 cifre
    B = 200 cifre
    C = nBYTE ????

    A * B = C

    int A contiene nBYTE , come fare a sommarlo ad B nBYTE ? come fare ad Unire gli nBYTE ?
  • Re: Programma Numeri Primi su commissione

    aleasia ha scritto:


    Riformulo la domanda : Vorrei vedere il codice di un programma che sappia fare le operazioni + x - / con numeri di anche 200 cifre e basta.

    A = 200 cifre
    B = 200 cifre
    C = nBYTE ????

    A * B = C

    int A contiene nBYTE , come fare a sommarlo ad B nBYTE ? come fare ad Unire gli nBYTE ?
    Allora vuoi (2), che non ha nulla a che spartire coi numeri primi.

    La risposta è: ci sono librerie già fatte, basta che cerchi su google.
    Se vuoi farti la tua ti basta fare le moltiplicazioni... come alle elementari, in colonna (* si lo so... lo so... non è che sia molto furbo come metodo).

    Nulla ti vieta di implementare (*si lo so... lo so...) A e B come stringhe, e C sempre come stringa, operando come menzionato come si insegna alle elementari.
    Inefficiente, ma un buon esercizio.

    Se vuoi vedere una libreria già fatta (tra le tante) puoi partire con GMP, dove il prodotto si fa banalmente con
    EDIT: correzione se usi interi, mpf sono i float ovviamente
    EDIT2: cavolo sto dormendo, abbi pazienza ma sto compilando mentre scrivo qui
    mpz_t A, B,C;
    mpz_mul(C, A, B);
Devi accedere o registrarti per scrivere nel forum
50 risposte