Proprietà (?) riguardante i numeri primi
Ciao a tutti, la questione nasce da una discussione su un altro forum di informatica, dove un utente afferma di aver fatto una scoperta che potrebbe trovare applicazione nel campo della crittografia. Nonostante l'assenza di una dimostrazione matematica, l'algoritmo in questione sembra funzionare stando alle sperimentazioni fatte dall'autore. La cosa mi ha incuriosito a allora ho cercato di inquadrare meglio il problema dal punto di vista matematico, e, dopo alcune domande mirate fatte all'autore, credo di esserci riuscito.
---------------------------------------------------------------------------------------------------
Sia $p$ un numero primo e $e_1>e_2$ e $b$ degli interi positivi.
Sia poi [size=140]\(z=p^{\lfloor\frac{e_1+e_2}{2}\rfloor}\)[/size], mentre [size=130]\(p_{1_i}\)[/size] e [size=130]\(p_{2_j}\)[/size] sono i numeri primi appartenenti rispettivamente ai due seguenti intervalli disgiunti: [size=120]$[p^(e_1)+1;p^(e_1)+2^b]$[/size] e [size=120]$[p^(e_2)+1;p^(e_2)+2^b]$[/size].
Si afferma che determinati valori di $p$, $e_1$, $e_2$ e $b$ individuano una famiglia di semiprimi [size=130]$s_(ij)=p_{1_i}*p_{2_j}$[/size] (ossia costituiti dal prodotto di due primi prelevati da ciascuno dei suddetti due intervalli) per cui $MCD(s_(ij), s_(ij) mod z)$ fornisce la fattorizzazione del semiprimo (essendo uguale a [size=130]\(p_{1_i}\)[/size] o [size=130]\(p_{2_j}\)[/size]).
---------------------------------------------------------------------------------------------------
Al momento non sono ancora riuscito a dimostrare o confutare la suddetta proprietà, ma mi sono limitato ad un paio di osservazioni:
1) affinché i due intervalli siano disgiunti dovrà essere
[size=115]$p^(e_1)+1>p^(e_2)+2^b=>b
2) poi
[size=130]\( z=p^{\lfloor\frac{e_1+e_2}{2}\rfloor} \leq p^{\frac{e_1+e_2}{2}} \leq p^{\frac{e_1+(e_1-1)}{2}} = p^{e_1} \cdot p^{-\frac{1}{2}} = \frac{p^{e_1}}{\sqrt{p}} < p^{e_1}+1 \leq p_{1_{MIN}}\)[/size]
Da cui si deduce una precisazione sulla tesi:
[size=130]$z s_{ij} mod z < p_{1_i} => MCD(s_(ij), s_(ij) mod z) = p_(2_j)$[/size]
Inoltre posto [size=130]$s_i=p_(1_i)*p_2$[/size] (con $p_2$ che indica uno specifico valore di [size=130]$p_(2_j)$[/size]), si deduce che dovrà essere:
[size=130]$MCD(s_i,s_i mod z) = p_2 AA i => [(p_(1_i)*p_2) mod z] mod p_2 = 0 AAi$[/size]
---------------------------------------------------------------------------------------------------
Non so quanto abbia senso tutto quello che ho scritto, per questo spero che qualcuno possa aiutarmi a fare luce sulla questione.
P.S.
L'autore ha saputo fornire esempi numerici solo con valori estremamente grandi, e a tal proposito penso vada sottolineato che la funzione python [inline]simpy.nextprime(n)[/inline] da lui usata, utilizzi per $n>2^64-1$ test di primalità su base probabilistica.
---------------------------------------------------------------------------------------------------
Sia $p$ un numero primo e $e_1>e_2$ e $b$ degli interi positivi.
Sia poi [size=140]\(z=p^{\lfloor\frac{e_1+e_2}{2}\rfloor}\)[/size], mentre [size=130]\(p_{1_i}\)[/size] e [size=130]\(p_{2_j}\)[/size] sono i numeri primi appartenenti rispettivamente ai due seguenti intervalli disgiunti: [size=120]$[p^(e_1)+1;p^(e_1)+2^b]$[/size] e [size=120]$[p^(e_2)+1;p^(e_2)+2^b]$[/size].
Si afferma che determinati valori di $p$, $e_1$, $e_2$ e $b$ individuano una famiglia di semiprimi [size=130]$s_(ij)=p_{1_i}*p_{2_j}$[/size] (ossia costituiti dal prodotto di due primi prelevati da ciascuno dei suddetti due intervalli) per cui $MCD(s_(ij), s_(ij) mod z)$ fornisce la fattorizzazione del semiprimo (essendo uguale a [size=130]\(p_{1_i}\)[/size] o [size=130]\(p_{2_j}\)[/size]).
---------------------------------------------------------------------------------------------------
Al momento non sono ancora riuscito a dimostrare o confutare la suddetta proprietà, ma mi sono limitato ad un paio di osservazioni:
1) affinché i due intervalli siano disgiunti dovrà essere
[size=115]$p^(e_1)+1>p^(e_2)+2^b=>b
2) poi
[size=130]\( z=p^{\lfloor\frac{e_1+e_2}{2}\rfloor} \leq p^{\frac{e_1+e_2}{2}} \leq p^{\frac{e_1+(e_1-1)}{2}} = p^{e_1} \cdot p^{-\frac{1}{2}} = \frac{p^{e_1}}{\sqrt{p}} < p^{e_1}+1 \leq p_{1_{MIN}}\)[/size]
Da cui si deduce una precisazione sulla tesi:
[size=130]$z
Inoltre posto [size=130]$s_i=p_(1_i)*p_2$[/size] (con $p_2$ che indica uno specifico valore di [size=130]$p_(2_j)$[/size]), si deduce che dovrà essere:
[size=130]$MCD(s_i,s_i mod z) = p_2 AA i => [(p_(1_i)*p_2) mod z] mod p_2 = 0 AAi$[/size]
---------------------------------------------------------------------------------------------------
Non so quanto abbia senso tutto quello che ho scritto, per questo spero che qualcuno possa aiutarmi a fare luce sulla questione.
P.S.
L'autore ha saputo fornire esempi numerici solo con valori estremamente grandi, e a tal proposito penso vada sottolineato che la funzione python [inline]simpy.nextprime(n)[/inline] da lui usata, utilizzi per $n>2^64-1$ test di primalità su base probabilistica.
Risposte
Dopo che l'autore mi ha fornito un esempio numerico, ossia un set di valori $p$, $e_1$, $e_2$ e $b$ (pari rispettivamente a $6523567678547$, $38$, $33$ e $75$), mi sono reso conto che la proprietà 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, facendo alcune prove e ragionando, credo di aver capito cosa avviene matematicamente dietro le quinte.
------------------------------------------------------------------------------------------------------------------------
Siano $a>b$ due interi positivi e
1) sia $c$ un divisore di $ab-b$
che soddisfa le seguenti due condizioni
2) $c>kb$ (con $k$ intero positivo)
3) $a mod c=1$ (è necessario quindi che sia $c
Una soluzione sempre valida, e che massimizza $c$ (e quindi $k$), è $c=a-1$; le altre soluzioni saranno invece costituite dai divisori di $a-1$ che sono $>b$.
Dalla 1) e 2) si deduce che
4) $ab mod c = b$
Introduciamo i due interi non negativi
5) $i<=k-1$
6) $j
Notando dalla 6) che al crescere di $i$ il limite superiore di $j$ diminuisce, e volendo trovare un limite superiore $m$ comune per entrambi, risolviamo la seguente equazione di secondo grado nella variabile $i$
7) $c/(i+1)-b=i$
Dalla 6) si deduce che $m$ sarà uguale all'arrotondamento per eccesso della soluzione positiva della 7) diminuita di $1$, ossia
8) [size=120]\( m = \Bigl\lceil \frac{-b-1 + \sqrt{(b-1)^2+4c}}{2} -1 \Bigr \rceil \) [/size]
Sfruttando la proprietà distributiva dell'operazione modulo rispetto all'addizione si ricava
9) [size=85]$[(a+i)(b+j)] mod c = (ab +ja + ib + ij) mod c = (ab mod c + ja mod c + ib mod c + ij mod c) mod c$[/size]
Dalla 3) e 6) (che in questo caso risulta più restrittiva del necessario, sarebbe infatti sufficiente $j
10) $ja mod c = j$
Dalla 2) e 5) si ricava
11) $ib mod c = ib$
Sostituendo la 4), 10) e 11) nella 9) e utilizzando la 6) (da cui si evince che $b+j+ib+ij
12) [size=85]$[(a+i)(b+j)] mod c = (b+j+ib+ij) mod c = b+j+ib+ij = (i+1)(b+j)$[/size]
E quindi per la 12) sarà
13a) ${[(a+i)(b+j)] mod c} mod (b+j)=0$
13b) ${[(a+i)(b+j)] mod c} \ \ -: \ \ \ (b+j)=i+1$
Inoltre, sempre dalla 12), ed essendo $a != 1$, ipotizzando che $a+i$ e $b+j$ siano due numeri primi, si deduce
14) $MCD{(a+i)(b+j) \ , \ [(a+i)(b+j)] mod c} = MCD[(a+i)(b+j) \ , \ (i+1)(b+j)] = b+j$
------------------------------------------------------------------------------------------------------------------------
Che dovrebbe essere la proprietà riscontrata sperimentalmente dall'autore.
Un esempio numerico (che in generale può essere trovato molto agevolmente) è il seguente:
$a=873$ , $b=59$ , $c=a-1=872$ , \( k= \Bigl \lfloor \frac{c}{b} \Bigl \rfloor = 14 \)
Per cui la 12) risulterà valida per ${(i<=13),(j<872/(i+1)-59):}$ o per $i,j<=m=11$
Che ne pensate? I passaggi sono corretti?
Alla fine, facendo alcune prove e ragionando, credo di aver capito cosa avviene matematicamente dietro le quinte.
------------------------------------------------------------------------------------------------------------------------
Siano $a>b$ due interi positivi e
1) sia $c$ un divisore di $ab-b$
che soddisfa le seguenti due condizioni
2) $c>kb$ (con $k$ intero positivo)
3) $a mod c=1$ (è necessario quindi che sia $c
Una soluzione sempre valida, e che massimizza $c$ (e quindi $k$), è $c=a-1$; le altre soluzioni saranno invece costituite dai divisori di $a-1$ che sono $>b$.
Dalla 1) e 2) si deduce che
4) $ab mod c = b$
Introduciamo i due interi non negativi
5) $i<=k-1$
6) $j
Notando dalla 6) che al crescere di $i$ il limite superiore di $j$ diminuisce, e volendo trovare un limite superiore $m$ comune per entrambi, risolviamo la seguente equazione di secondo grado nella variabile $i$
7) $c/(i+1)-b=i$
Dalla 6) si deduce che $m$ sarà uguale all'arrotondamento per eccesso della soluzione positiva della 7) diminuita di $1$, ossia
8) [size=120]\( m = \Bigl\lceil \frac{-b-1 + \sqrt{(b-1)^2+4c}}{2} -1 \Bigr \rceil \) [/size]
Sfruttando la proprietà distributiva dell'operazione modulo rispetto all'addizione si ricava
9) [size=85]$[(a+i)(b+j)] mod c = (ab +ja + ib + ij) mod c = (ab mod c + ja mod c + ib mod c + ij mod c) mod c$[/size]
Dalla 3) e 6) (che in questo caso risulta più restrittiva del necessario, sarebbe infatti sufficiente $j
10) $ja mod c = j$
Dalla 2) e 5) si ricava
11) $ib mod c = ib$
Sostituendo la 4), 10) e 11) nella 9) e utilizzando la 6) (da cui si evince che $b+j+ib+ij
12) [size=85]$[(a+i)(b+j)] mod c = (b+j+ib+ij) mod c = b+j+ib+ij = (i+1)(b+j)$[/size]
E quindi per la 12) sarà
13a) ${[(a+i)(b+j)] mod c} mod (b+j)=0$
13b) ${[(a+i)(b+j)] mod c} \ \ -: \ \ \ (b+j)=i+1$
Inoltre, sempre dalla 12), ed essendo $a != 1$, ipotizzando che $a+i$ e $b+j$ siano due numeri primi, si deduce
14) $MCD{(a+i)(b+j) \ , \ [(a+i)(b+j)] mod c} = MCD[(a+i)(b+j) \ , \ (i+1)(b+j)] = b+j$
------------------------------------------------------------------------------------------------------------------------
Che dovrebbe essere la proprietà riscontrata sperimentalmente dall'autore.
Un esempio numerico (che in generale può essere trovato molto agevolmente) è il seguente:
$a=873$ , $b=59$ , $c=a-1=872$ , \( k= \Bigl \lfloor \frac{c}{b} \Bigl \rfloor = 14 \)
Per cui la 12) risulterà valida per ${(i<=13),(j<872/(i+1)-59):}$ o per $i,j<=m=11$
Che ne pensate? I passaggi sono corretti?
Mi rendo conto che quanto scritto in precedenza possa risultare dispersivo e poco chiaro, quindi vi chiedo di ignorare tutto e dirmi se la seguente dimostrazione (se così si può chiamare), per quanto stupida e inutile, sia corretta o meno.
(Premetto che $mod$ è inteso come operatore binario, dove $a mod b$ restituisce il resto della divisione intera tra $a$ e $b$ col quoziente arrotondato verso l'infinito negativo).
-------------------------------------------------------------------------------------------------------------------------
Siano $a>b$ due interi positivi, e sia $c$ un divisore di $ab-b$ che soddisfa le seguenti due condizioni
1) $c>kb$ (con $k$ intero positivo)
2) $a mod c=1$ (è necessario quindi che sia $c
Una soluzione sempre valida, e che massimizza $c$ (e quindi \( k = \Bigl \lfloor \frac{c}{b} \Bigr \rfloor \)), è $c=a-1$; le altre soluzioni saranno invece costituite dai divisori di $a-1$ che sono $>b$.
Introduciamo i due interi non negativi
3) $i
Sfruttando la proprietà distributiva dell'operazione modulo rispetto all'addizione si ricava
5) [size=83]$[(a+i)(b+j)] mod c = (ab +ja + ib + ij) mod c = [(ab mod c) + (ja mod c) + (ib mod c) + (ij mod c)] mod c$[/size]
Dalla 1) e 2) si ricava
6) $ab mod c = b$
Dalla 2) e 4) (che in questo caso risulta più restrittiva del necessario, sarebbe infatti sufficiente $j
7) $ja mod c = j$
Dalla 1) e 3) si ricava
8) $ib mod c = ib$
Sostituendo la 6), 7) e 8) nella 5) e utilizzando la 4) (da cui si evince che $b+j+ib+ij
9) [size=85]$[(a+i)(b+j)] mod c = (b+j+ib+ij) mod c = b+j+ib+ij = (i+1)(b+j)$[/size]
-------------------------------------------------------------------------------------------------------------------------
OSSERVAZIONE 1: dalla 9) si ricava
10) [size=80]$MCD{(a+i)(b+j) \ , \ [(a+i)(b+j)] mod c} = MCD[(a+i)(b+j) \ , \ (i+1)(b+j)] =(b+j)*MCD(a+i \ , \ i+1)$[/size]
che restituisce come risultato $b+j$ nel caso in cui $a+i$ e $i+1$ sono coprimi, cosa che sarà sicuramente vera se $(a+i)(b+j)$ è un semiprimo.
-------------------------------------------------------------------------------------------------------------------------
OSSERVAZIONE 2: notando dalla 4) che al crescere di $i$ il limite superiore di $j$ diminuisce, e volendo trovare un limite superiore $m$ comune per entrambi, risolviamo la seguente equazione di secondo grado nella variabile $i$
11) $c/(i+1)-b=i$
Tale equazione ha due soluzioni, una positiva (chiamiamola $i'$ , che non sarà per forza una quantità intera) e una negativa, e ovviamente quella negativa va scartata essendo per ipotesi $i$ e $j$ interi non negativi. A questo punto sostituendo $i'$ nella 4) si otterrebbe $j
12) [size=120]\( m = \Bigl \lceil \frac{\sqrt{(b-1)^2+4c} \ -b-1}{2} -1 \Bigr \rceil \) [/size]
(Premetto che $mod$ è inteso come operatore binario, dove $a mod b$ restituisce il resto della divisione intera tra $a$ e $b$ col quoziente arrotondato verso l'infinito negativo).
-------------------------------------------------------------------------------------------------------------------------
Siano $a>b$ due interi positivi, e sia $c$ un divisore di $ab-b$ che soddisfa le seguenti due condizioni
1) $c>kb$ (con $k$ intero positivo)
2) $a mod c=1$ (è necessario quindi che sia $c
Una soluzione sempre valida, e che massimizza $c$ (e quindi \( k = \Bigl \lfloor \frac{c}{b} \Bigr \rfloor \)), è $c=a-1$; le altre soluzioni saranno invece costituite dai divisori di $a-1$ che sono $>b$.
Introduciamo i due interi non negativi
3) $i
Sfruttando la proprietà distributiva dell'operazione modulo rispetto all'addizione si ricava
5) [size=83]$[(a+i)(b+j)] mod c = (ab +ja + ib + ij) mod c = [(ab mod c) + (ja mod c) + (ib mod c) + (ij mod c)] mod c$[/size]
Dalla 1) e 2) si ricava
6) $ab mod c = b$
Dalla 2) e 4) (che in questo caso risulta più restrittiva del necessario, sarebbe infatti sufficiente $j
7) $ja mod c = j$
Dalla 1) e 3) si ricava
8) $ib mod c = ib$
Sostituendo la 6), 7) e 8) nella 5) e utilizzando la 4) (da cui si evince che $b+j+ib+ij
9) [size=85]$[(a+i)(b+j)] mod c = (b+j+ib+ij) mod c = b+j+ib+ij = (i+1)(b+j)$[/size]
-------------------------------------------------------------------------------------------------------------------------
OSSERVAZIONE 1: dalla 9) si ricava
10) [size=80]$MCD{(a+i)(b+j) \ , \ [(a+i)(b+j)] mod c} = MCD[(a+i)(b+j) \ , \ (i+1)(b+j)] =(b+j)*MCD(a+i \ , \ i+1)$[/size]
che restituisce come risultato $b+j$ nel caso in cui $a+i$ e $i+1$ sono coprimi, cosa che sarà sicuramente vera se $(a+i)(b+j)$ è un semiprimo.
-------------------------------------------------------------------------------------------------------------------------
OSSERVAZIONE 2: notando dalla 4) che al crescere di $i$ il limite superiore di $j$ diminuisce, e volendo trovare un limite superiore $m$ comune per entrambi, risolviamo la seguente equazione di secondo grado nella variabile $i$
11) $c/(i+1)-b=i$
Tale equazione ha due soluzioni, una positiva (chiamiamola $i'$ , che non sarà per forza una quantità intera) e una negativa, e ovviamente quella negativa va scartata essendo per ipotesi $i$ e $j$ interi non negativi. A questo punto sostituendo $i'$ nella 4) si otterrebbe $j
12) [size=120]\( m = \Bigl \lceil \frac{\sqrt{(b-1)^2+4c} \ -b-1}{2} -1 \Bigr \rceil \) [/size]
Riferimenti precisi?
Chi è l'autore? Quale forum?
Chi è l'autore? Quale forum?
Giusto per chiarire il contesto... l'autore ha notato che i semiprimi $S$, dati dal prodotto di due generici primi prelevati da due determinati intervalli, potevano essere tutti fattorizzati con una stessa chiave $c$ attraverso la formula $MCD(S ;S mod c)$; la suddetta proprietà è stata riscontrata sperimentalmente senza sapere perché funzionasse, e infatti intervalli e chiavi venivano trovati per tentativi.
La cosa mi ha incuriosito e allora ho deciso di ragionarci un po' per capire cosa avvenisse matematicamente dietro le quinte, da cui la "dimostrazione" riportata nel mio precedente post.
La "dimostrazione" è mia e l'autore è al corrente di questo topic, non capisco dove sia il problema!?
Cioè volendo se ne può anche parlare, ma non ne vedo il motivo...
La cosa mi ha incuriosito e allora ho deciso di ragionarci un po' per capire cosa avvenisse matematicamente dietro le quinte, da cui la "dimostrazione" riportata nel mio precedente post.
"gugo82":
Riferimenti precisi?
Chi è l'autore? Quale forum?
La "dimostrazione" è mia e l'autore è al corrente di questo topic, non capisco dove sia il problema!?
Cioè volendo se ne può anche parlare, ma non ne vedo il motivo...
Sinceramente non capisco perché fino ad adesso non ho ricevuto nemmeno una risposta che mi dica se quanto scritto in questo post sia corretto o meno?!
Io sono abbastanza convinto di quello che ho scritto, ma, visto che nell'altro forum di informatica di cui parlavo mi sono state fatte delle obiezioni per me completamente infondate, ho pensato di approfittare di questo topic per chiedere una conferma.
Io sono abbastanza convinto di quello che ho scritto, ma, visto che nell'altro forum di informatica di cui parlavo mi sono state fatte delle obiezioni per me completamente infondate, ho pensato di approfittare di questo topic per chiedere una conferma.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo