Algoritmi di fattorizzazione

di
Paolovox
il
4 risposte
Paolovox
Paolovox
Utente Attivo
Iscritto da
giu, 2014
Messaggi:
344

Algoritmi di fattorizzazione

Quali sono i migliori da utilizzare? dove è possibile reperire materiale per studiarli?

4 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6072

    Re: Algoritmi di fattorizzazione

    Di che algoritmi di fattorizzazione stai parlando?
    Di quelli per fattorizzare numeri interi?

    Se si, a quali numeri interi stai pensando? A quelli da 8/16/32/64 bit di macchina o a quelli usati in campo crittografico da 512/1024/2048/65536 bit?

    Fino a 2^32 li puoi fattorizzare usando la forza bruta, in una manciata di secondi.
    Quelli a 64 bit piu' o meno anche, anche se ci potrebbe volere un po' di tempo (forse qualche mese con il pc di casa).

    Se stai pensando a quelli usati in campo crittografico, non esiste un unico algoritmo di fattorizzazione, ma ne esistono diversi. Comunque sono tutti poco efficienti: per fattorizzare numeri da 512 bit ci potrebbe volere un tempo superiore alla vita dell'universo conosciuto.

    2^512 ~= 1.3 *10^154
    2^1024 ~= 1.8 *10^308

    supponi di provare 1000.000.000.000 (mille miliardi, 1*10^12) di test al secondo, e prova a fare un po' di conti .

    Si potrebbe fare di meglio (decisamente meglio ) usando un computer quantistico. Ma al momento i computer quantistici non li acquisti da MediaWorld .

    Gli algoritmi di fattorizzazione fanno parte della teoria dei numeri: settore della matematica estremamente affascinante ma decisamente tosto

    Comunque se spulci wikipedia per Fattorizzazione, trovi un bel po' di informazioni.
  • Paolovox
    Paolovox
    Utente Attivo
    Iscritto da
    giu, 2014
    Messaggi:
    344

    Re: Algoritmi di fattorizzazione

    Stiamo progettando una piccola shell fatta in Java e comprende il metodo factorize. Il grade della shell comprende dei test per il metodo factorize con numeri del tipo : 2028429820228621619.
    Un bruteforce impiega troppo tempo dato che ho max 60000 ms per fattorizzare un numero.
    Ti ringrazio per la risposta e continuerò a sbatterci la testa.
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6072

    Re: Algoritmi di fattorizzazione

    Allora ti consiglio:

    1) limitati a numeri inferiori a 2^64 (1.8 *10^19). Il numero che hai scritto e' 2*10^18 e va bene

    2) implementa la fattorizzazione in C, e crea una DLL

    3) usa JNA (Java Native Access) per accedere alla DLL. JNA ti permette di evitare di scornarti con JNI (Java Native Interface), con un minuscolo overhead

    A questo punto la fattorizzazione puo' essere implementata in modo decisamente efficiente in C usando un long int, un intero a 64 bit.

    Puoi usare diverse strategie:

    1) la prima e' usare un vettore di primi precablato nel codice. Ad esempio puoi usare un vettore con 1000/10.000 elementi

    https://www.mathsisfun.com/numbers/prime-number-lists.html

    2) se il numeo e' inferiore a 2^32, puoi usare il bruteforce

    3) infine, puoi implementare, o trovare del codice gia' pronto, per ulteriori algoritmi di fattorizzazione



    ecc..

    Ovviamente, se implementi gli algoritmi di fattorizzazione, devi implementare anche degli algoritmi per i test di primalita'!

    Bel progetto .
  • Paolovox
    Paolovox
    Utente Attivo
    Iscritto da
    giu, 2014
    Messaggi:
    344

    Re: Algoritmi di fattorizzazione

    Adesso fattorizzo i numeri alla velocià della luce Si il progetto è molto divertente e didatticamente costruttivo. Grazie mille per l'aiuto fondamentale. Inoltre è davvero un argomento molto interessante, con i misteri sui numeri primi, la crittografia odierna, congettura di Riemann, funzione di Eulero, crivello di Eratostene ecc..
Devi accedere o registrarti per scrivere nel forum
4 risposte