Matematica: fattorizzazione

Question

Omettendo i dettagli dei metodi per calcolare i numeri primi e i metodi di fattorizzazione.

Perché preoccuparsi di scomporre?

Quali sono le sue applicazioni?

Answer 1

Wow, tanti combattimenti in questo thread.

Ironia della sorte, questa domanda ha una grande risposta valida.

La fattorizzazione viene effettivamente utilizzata pesantemente negli algoritmi di crittografia / decrittazione, al punto che RSA conduce regolarmente competizioni in cui il compito è quello di fattorizzare alcuni numeri grandi che sono multipli di numeri primi molto grandi.

Questo è, a sua volta, perché diversi algoritmi di crittografia / decrittazione si basano sul presupposto che la fattorizzazione richiede molto tempo, il che (presumibilmente) rende difficile e / o poco pratico craccare determinati algoritmi di crittografia / decrittazione, dato il presupposto che l'hacker / cracker non ha accesso a chiavi pubbliche / private.

Gli algoritmi di fattorizzazione possono quindi essere utilizzati per verificare quanto sia forte un determinato algoritmo di crittografia / decrittografia.

Answer 2

La crittografia asimmetrica come RSA / DAS si basa sul fatto che la fattorizzazione è una cosa molto difficile. Se ti do un numero, che una volta stampato è grande quanto un'intera pagina di giornale e ti dico "Questo numero è stato generato moltiplicando due numeri primi. Ora, per favore, fattorizzalo " ... pensi di poterlo fare? Fidati di me, qualsiasi modo noto per farlo richiederà un'eternità. Non esiste un modo efficace per farlo senza aver bisogno di tonnellate di tempo di CPU (secoli) o tonnellate di memoria (più spazio di archiviazione di tutti i server Internet del mondo insieme). Se trovi un modo semplice per fattorizzare numeri così grandi, ad esempio interrompi la firma e-mail e SSL (HTTPS).

Tuttavia, ci sono altre attività legate alla fattorizzazione. La fattorizzazione non riguarda solo il numero. A volte si tratta di "perché i polinomi sono fattori di altri polinomi". Quindi le attività matematiche possono dipendere dalla fattorizzazione e così tanti problemi possono essere risolti da essa. Pertanto un'efficace fattorizzazione è di grande valore. Anche le matrici possono essere fattorizzate.

Answer 3

Può essere usato per decifrare alcuni tipi di crittografia (se la loro chiave era abbastanza piccola).

Ne avresti bisogno anche per alcuni tipi di software scientifico.

Un'altra domanda è rispondere alle ProjectEuler Domande.