Perché gli algoritmi genetici non funzionano su problemi come il factoring RSA?

StackOverflow https://stackoverflow.com/questions/5456483

Domanda

Qualche tempo fa ero abbastanza interessato al gas e ho studiato un bel po '.Ho usato GALIB C ++ per scrivere alcuni programmi ed ero piuttosto sorpreso dalla loro capacità di risolvere altrimenti difficili da calcolare i problemi, in pochi secondi.Sembravano una grande tecnica brutaforming che funziona davvero davvero intelligente e adatta.

Stavo leggendo un libro di Michalewitz, se ricordo il nome correttamente e tutto sembrava essere basato sul teorema dello schema, dimostrato da MIT.

Ho anche sentito che non può essere usato per affrontare problemi come factoring tasti privati RSA.

Qualcuno potrebbe spiegare perché questo è il caso?

È stato utile?

Soluzione

L'algoritmo genetico non è intelligente a tutti , sono algoritmi ottimizzatori molto avidi. Lavorano tutti sulla stessa idea. Hai un gruppo di punti ('una popolazione di individui "), e trasformi quel gruppo in un altro con un operatore stocastico, con un pregiudizio nella direzione del miglior miglioramento (" mutation + crossover + selezione "). Ripeti finché non converge o sei stanco di esso, niente di intelligente lì.

Per un algoritmo genetico da lavorare, una nuova popolazione di punti dovrebbe esibirsi vicino alla precedente popolazione di punti. Poca perturbazione dovrebbe creare poco cambiamento. Se, dopo una piccola perturbazione di un punto, si ottiene un punto che rappresenta una soluzione con prestazioni completamente diverse, quindi, l'algoritmo non è niente di meglio della ricerca casuale, un algoritmo di solito non buono. Nel caso RSA, se i tuoi punti sono direttamente i numeri, è sì o no, semplicemente lanciando un po '... usando così un algoritmo genetico non è migliore della ricerca casuale, se si rappresenta il problema RSA senza molto pensare "Let's Punti di ricerca del codice come bit dei numeri "

Altri suggerimenti

Direi perché il fattorizzazione dei tasti non è un problema di ottimizzazione, ma un problema esatto.Questa distinzione non è molto accurata, quindi qui ci sono dettagli. Gli algoritmi genetici sono fantastici per risolvere i problemi in cui sono minimi (locali / globali), ma non ci sono dei problemi di facriting.L'algoritmo genetico come DCA o ricottura simulata ha bisogno di una misura di "Quanto vicino sono alla soluzione" ma non puoi dire questo per il nostro problema.

Per un esempio della genetica problematica è buono, c'è il problema di arrampicata sulla collina.

Gas si basano sulla valutazione del fitness delle soluzioni candidate.

Hai fondamentalmente una funzione fitness che prende una soluzione candidata come input e ti restituisce uno scalare che ti dice quanto è buono quel candidato.Quindi vai avanti e consente ai migliori individui di una determinata generazione di accoppiarsi con maggiore probabilità rispetto al resto, in modo che la progenie sarà (si spera) più "adatta" nel complesso, e così su .

.

Non c'è modo di valutare il fitness (quanto è buona una soluzione candidata rispetto al resto) nello scenario di Factorization RSA, quindi è per questo che non puoi usarli.

Gas non è in forzatura bruta, sono solo un algoritmo di ricerca.Ogni GA è essenzialmente questo: 

candidates = seed_value;
while (!good_enough(best_of(candidates))) {
    candidates = compute_next_generation(candidates);
}
.

Dove good_enough e best_of sono definiti in termini di una funzione di fitness .Una funzione di fitness dice quanto bene un dato candidato risolve il problema .Sembra essere il problema principale qui: come scriveresti una funzione fitness per la fattorizzazione?Ad esempio 20= 2 * 10 o 4 * 5.Le tuple (2,10) e (4,5) sono chiaramente i vincitori, ma per quanto riguarda gli altri?Come "Fit" è (1,9) o (3,4)?

indirettamente, tu può Utilizzare un algoritmo genetico per factory un metodo Integer Integer Integer N. Dixon utilizza equazioni che coinvolgono poteri dei primi K PREMES, Modulo N. Questi prodotti di poteri di piccoli primi sono chiamati "lisci". Se stiamo usando i primi k= 4 numerosi - {2,3,5,7} - 42= 2x3x7 è liscia e 11 non è (per mancanza di un termine migliore, 11 è "ruvido" ). Il metodo di Dixon richiede un allontanamento k x k la matrice costituita dagli esponenti che definiscono questi numeri lisci. Per ulteriori informazioni sul metodo di Dixon vedere https://en.wikipedia.org/wiki/dixon%27s_factorization_method .

Ora, torna alla domanda originale: c'è un algoritmo genetico per trovare equazioni per il metodo di Dixon.

    .
  1. Let r essere l'inverso di un numero liscio mod n - quindi r è un numero ruvido
  2. Let s essere liscio
  3. Genera soluzioni casuali di rx= sy mod n. queste soluzioni [x, y] sono la popolazione per l'algoritmo genetico. Ogni x, Y ha un componente liscio e un componente approssimativo. Ad esempio supporre x= 369= 9 x 41. Quindi (supponendo 41 non è abbastanza piccolo da contare come liscio), la parte ruvida di X è 41 e la parte liscia è 9.
  4. Scegli le coppie di soluzioni - "genitori" - combinare in combinazioni lineari con parti ruvide sempre più piccole.
  5. L'algoritmo termina quando una coppia [x, y] viene trovata con parti ruvide [1,1], [1, -1], [- 1,1] o [-1, -1]. Ciò produce un'equazione per il metodo di Dixon, perché rx= sy mod n e r è l'unico numero ruvido a sinistra: x e y sono lisci e s avviati liscio. Ma anche 1 / r mod n è liscio, quindi è tutto liscio!

    Ogni volta che combini due coppie - dì [V, w] e [x, y] - le parti lisce dei quattro numeri sono cancellati, ad eccezione dei fattori le parti lisce di V e X Share, e i fattori del parti lisce di w e y condividono. Quindi scegliamo i genitori che condividono parti liscia nella misura massima possibile. Per rendere questo preciso, scrivi

    G= GCD (parte liscia di V, parte liscia di X)

    H= GCD (parte liscia di w, parte liscia di y)

    [v, w], [x, y]= [g v / g, h w / h], [g x / g, h y / h].

    i fattori fluidi duramente conquistati G e H saranno conservati nella prossima generazione, ma le parti lisce di V / G, W / H, X / G e Y / H saranno sacrificate per combinare [V, w] e [x, y]. Quindi scegliamo i genitori per cui V / G, W / H, X / G e Y / H hanno le parti più piccole. In questo modo guidiamo davvero le parti approssimative delle nostre soluzioni a rx= sy mod n da una generazione all'altro.

su promuovere ulteriormente il modo migliore per farti strada verso coefficienti lisci x, y nell'ascia reticolata= da mod n è con la regressione, non un algoritmo genetico.

Due regressioni vengono eseguite, una con risposta vettoriale R0 costituita da valori X da soluzioni scelte a caso di AX= mediante mod n; E l'altro con la risposta R1 vettoriale costituita da valori Y dalle stesse soluzioni. Entrambe le regressioni utilizzano la stessa matrice esplicativa X. In X sono colonne composte dai resti dei valori X-Valori Modulo Smooth Divisori e altre colonne costituite dai resti dei resti dei valori Y Modulo altri divisori lisci.

La scelta migliore dei divisori lisci è quella che riduce al minimo gli errori di ciascuna regressione:

E0= R0 - X (Inverse of (X-Transpose) (X)) (X-Transpose) (R0)

E1= R1 - X (Inverse of (X-Transpose) (X)) (X-Transpose) (R1)

Quanto segue è le operazioni di riga per Annihilate X. Quindi applicare un risultato Z di queste operazioni di riga ai valori X e Y dalle soluzioni originali da cui X è stata formata. 

z R0 = z R0 - 0
     = z R0 - zX (inverse of (X-transpose)(X)) (X-transpose) (R0)
     = z E0
.

Allo stesso modo, z r1= z E1

Tre proprietà sono ora combinate in Z R0 e Z R1:

    .
  • sono multipli di grandi numeri lisci, poiché Z Annientati restanti i numeri moduli.
  • sono relativamente piccoli, da E0 ed E1 sono piccoli.
  • Come qualsiasi combinazione lineare di soluzioni a ax= mediante mod n, z r0 e z r1 sono stesse soluzioni a quell'equazione.

    Un multiplo relativamente piccolo di un numero di grande grande numero potrebbe essere il numero liscio stesso. Avere una soluzione liscia di ax= mediante mod n produce un ingresso al metodo di dixon.

    Due ottimizzazioni rendono questo particolarmente veloce:

      .
    • Non è necessario indovinare tutti i numeri e le colonne liscia di X in una sola volta. È possibile eseguire regressioni continuemente, aggiungendo una colonna a x alla volta, scegliendo colonne che riducono il massimo E0 ed E1. In nessun momento saranno selezionati due numeri lisci con un fattore comune.
    • Puoi anche iniziare con molte soluzioni casuali di ZX= mediante Mod N e rimuovere quelle con gli errori più grandi tra le selezioni delle nuove colonne per x.
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top