Che cos'è un semplice esempio di una funzione di botola?

5

Stavo tentando di spiegare la crittografia a chiave pubblica a un laico l'altro giorno che richiede una spiegazione di una funzione di botola. Mentre in linea di principio so che cos'è una funzione di botola, devo ammettere le proprietà matematiche specifiche dietro il problema della fattorizzazione principale e il problema della CCE non sono al mio fianco.

Esiste un semplice esempio che può essere utilizzato per esemplificare una funzione di botola? Stavo pensando ai quadrati e alle radici quadrate, poiché i quadrati sono facilmente calcolati ma le radici quadrate, in un certo senso, richiedono una forza bruta guidata.

    
posta John Wu 25.09.2015 - 19:49
fonte

1 risposta

6

La risposta più semplice è semplicemente la fattorizzazione. È facile calcolare il prodotto di due numeri primi. Ci vorrebbero un minuto o due, ma è possibile calcolare su carta e penna che 1093 * 1039 = 1,135,627. Andare dall'altra parte è molto più difficile. Se ti ho appena dato il numero 1,135,627 e ti ho chiesto quali numeri ho moltiplicato per ottenere quel numero, potrebbero essere necessarie ore di fattorizzazione di prova con carta e penna per calcolarlo. Per farlo rapidamente ti serve un computer.

Ma se ti chiedessi di fare il fattore 15, risponderesti rapidamente a 5 e 3. Quindi la difficoltà del factoring aumenta quando i numeri primi aumentano di valore. Se i due numeri primi vengono scelti sufficientemente grandi anche un computer, o anche migliaia di computer non sono sufficienti per arrivare ai due fattori.

    
risposta data 25.09.2015 - 20:12
fonte

Leggi altre domande sui tag