M1n021
Utente Attivo
- Messaggi
- 213
- Reazioni
- 91
- Punteggio
- 42
Il topic, come si evince dal titolo, vuole essere una continuazione (si spera più serena e ragionata) della seguente discussione chiusa un po' di tempo fa: https://forum.tomshw.it/threads/programma-di-criptazione-decriptazione.932244/
Il fatto che il metodo ideato da @piergiac-1, stando alle sue sperimentazioni, sembrasse funzionare, mi ha incuriosito, e quindi ho deciso di approfondire la questione cercando di capire cosa avvenisse matematicamente dietro le quinte, in modo da poter giungere alla fine ad una sua dimostrazione o confutazione.
Il primo passo è stato quello di inquadrare meglio e formalizzare il metodo proposto dall'autore, che più o meno dovrebbe essere il seguente.
Sia
Non starò qui a tediarvi con tutti i passaggi, mi limito quindi a dire che, ragionando matematicamente su quanto appena scritto, ho dedotto che il suddetto MCD non può restituire il maggiore dei due numeri primi (ossia
a)
Inoltre dalla a) si deduce che
b)
In seguito, facendo alcuni test su uno degli esempi numerici forniti dall'autore, mi sono reso conto che la proprietà b) non riguarda esclusivamente i numeri primi, ma sussiste per ogni coppia di numeri prelevata dai due intervalli; inoltre essa persiste anche oltre i limiti degli intervalli da lui fissati.
Alla fine, ragionando su questi presupposti, credo di aver capito cosa avviene matematicamente dietro le quinte:
Dove la 14) dovrebbe essere proprio la proprietà riscontrata sperimentalmente dall'autore.
Per chiarire il senso della mia dimostrazione provo a fare un esempio numerico relativo alla 14).
Innanzitutto scegliamo due valori qualsiasi
A questo punto siamo in grado di definire precisamente gli intervalli da cui prelevare i numeri primi, ossia
Quindi in definitiva la formula
In seguito poi si potrà anche approfondire la parte del metodo sviluppato dall'autore più legata alla crittografia, ma per il momento mi vorrei soffermare sulla parte più matematica, anche perché mi sembra di ricordare che c'erano alcuni utenti interessati alla questione.
Ovviamente eventuali osservazioni o correzioni relative alla dimostrazione matematica sono ben accette.
Il fatto che il metodo ideato da @piergiac-1, stando alle sue sperimentazioni, sembrasse funzionare, mi ha incuriosito, e quindi ho deciso di approfondire la questione cercando di capire cosa avvenisse matematicamente dietro le quinte, in modo da poter giungere alla fine ad una sua dimostrazione o confutazione.
Il primo passo è stato quello di inquadrare meglio e formalizzare il metodo proposto dall'autore, che più o meno dovrebbe essere il seguente.
Sia
p un numero primo e siano e1 > e2 e b degli interi positivi. Sia poi z = p^[(e1+e2)/2] (dove le parentesi quadre indicano in questo caso la divisione intera), mentre p1 e p2 sono due generici numeri primi appartenenti rispettivamente agli intervalli [p^e1 + 1 ; p^e1 + 2^b] e [p^e2 + 1 ; p^e2 + 2^b] . Si afferma che determinati valori di p, e1, e2 e b individuano una famiglia di semiprimi s = p1*p2 (costituiti cioè dal prodotto di due primi prelevati da ciascuno dei suddetti due intervalli) per cui la formula MCD(s , s mod z) fornisce la fattorizzazione del semiprimo (restituendo il MCD o p1 o p2 ). Fine.Non starò qui a tediarvi con tutti i passaggi, mi limito quindi a dire che, ragionando matematicamente su quanto appena scritto, ho dedotto che il suddetto MCD non può restituire il maggiore dei due numeri primi (ossia
p1), quindi qualora il metodo fosse corretto dovrà per forza esserea)
MCD(s , s mod z) = MCD(p1*p2 , p1*p2 mod z) = p2Inoltre dalla a) si deduce che
p1*p2 mod z deve essere un multiplo di p2 , che in matematichese si può scrivere comeb)
(p1*p2 mod z) mod p2 = 0In seguito, facendo alcuni test su uno degli esempi numerici forniti dall'autore, mi sono reso conto che la proprietà b) non riguarda esclusivamente i numeri primi, ma sussiste per ogni coppia di numeri prelevata dai due intervalli; inoltre essa persiste anche oltre i limiti degli intervalli da lui fissati.
Alla fine, ragionando su questi presupposti, credo di aver capito cosa avviene matematicamente dietro le quinte:
Per chiarire il senso della mia dimostrazione provo a fare un esempio numerico relativo alla 14).
Innanzitutto scegliamo due valori qualsiasi
a e b (con a>b), per esempio a=8361 e b=207 . Il massimo valore della chiave c sarà c_max = a-1 = 8360 = 2^3*5*11*19; gli altri valori assumibili dalla chiave c sono i divisori di a-1 maggiori di b , come per esempio c_1 = 2^2*5*19 = 380 o c_2 = 5*11*19 = 1045 .A questo punto siamo in grado di definire precisamente gli intervalli da cui prelevare i numeri primi, ossia
[a ; a+i] e [b ; b+j) , con i e j definiti rispettivamente dalla 5) e dalla 6) (da cui si può notare che j dipende da i ). Volendo però si può semplificare il tutto riducendo gli intervalli a [a ; a+m] e [b ; b+m] , con m ricavabile dalla 8), da cui peraltro si deduce che al diminuire della chiave c diminuisce anche m ; quindi il massimo valore di m , e di conseguenza gli intervalli più ampi, si ottengono per c = c_max , e facendo i conti nel nostro caso si ottiene m=33 .Quindi in definitiva la formula
MCD(A*B , A*B mod c_max) = B sarà valida per tutti i numeri primi A e B prelevati rispettivamente dagli intervalli [8361 ; 8361+33] e [207 ; 207+33] .In seguito poi si potrà anche approfondire la parte del metodo sviluppato dall'autore più legata alla crittografia, ma per il momento mi vorrei soffermare sulla parte più matematica, anche perché mi sembra di ricordare che c'erano alcuni utenti interessati alla questione.
Ovviamente eventuali osservazioni o correzioni relative alla dimostrazione matematica sono ben accette.
Ultima modifica: