domenica 20 maggio 2018

Algoritmo semplificato per fattorizzare numeri RSA

Dalla relazione sempre vera
2*radq(n+d^2) = S = p+q
n = pq
d = (p-q)/2




#include
#include
#include

using namespace std;

int main(int argc, char *argv[])
{
long long int n;

long double s, p, q, d;


cout << "inserisci n ";
cin >> n;

d = 0;
s = sqrt(n+d*d);

while(s != floor(s)) {
d = d+1;
s = sqrt(n+d*d);
}

s = 2*s;
p = (s-sqrt(s*s-4*n))/2;
q = n/p;

cout << "p = " << p << "\n";
cout << "q = " << q << "\n";
 
  system("PAUSE");   
  return 0;
}

lunedì 7 maggio 2018

Legge sui ritardi nel gioco del lotto e della roulette

Supponiamo di considerare la distribuzione binomiale o legge delle prove ripetute e di applicarla al gioco del lotto su estratto singolo (o al gioco della roulette sulle chance semplici)

Ovvero
p = prob evento favorevole = esce un certo numero in una data ruota (es il 6 a Napoli) = 5/90=1/18
q = prob evento contrario = 1- 1/18=17/18

allora sappiamo che l'evento favorevole con probabilità p si verificherà con una probabilità del 99,7%, in n estrazioni un  numero di volte compreso tra:

[np-3*sqrt(npq) e np+3sqrt(npq)]

sqrt(npq) = scarto quadratico medio della distribuzione bernulliana
np = valore atteso

dove sqrt() = è la radine quadrata

in dettaglio dalla teoria:
[np-3*sqrt(npq) - np+3sqrt(npq)], 99,7 % probabilità
[np-2*sqrt(npq) - np+2sqrt(npq)], 95 % probabilità
[np-1*sqrt(npq) - np+1*sqrt(npq)], 68 % probabilità

che ricorda molto la proprietà più famosa della Gaussiana

allora l'equazione in n
np-3*sqrt(npq) = 1 risolta ci darà il valore di n ovvero  quanto ritardo può accusare un numero in una determinata ruota perché ci dice che la frequenza di quel numero deve essere almeno 1 con una probabilità prossima al 99,7%

Se ad esempio  p = 1/18 allora n è circa 187. Il che vuol dire che se un un numero accusa un ritardo in un certa ruota (non importa la posizione, estratto singolo) da 187 estrazioni (ogni estrazione è di 5 numeri) allora conviene iniziare a giocarlo.

Ovviamente il 99,7% di probabilità non è il 100% e lo scarto di 0.3% su 1000 estrazioni può diventare significativo (3 casi su 1000 non compresi nell'intervallo). Per avere il 100% nel range occorre sostituire il 3 con il 4 (qualcosa in meno in realtà) e n diventa circa 300, vuol dire che un estratto singolo non potrà superare le 300 estrazioni di ritardo.

Lo stesso ragionamento si può applicare per altri giochi aleatori come il gioco della roulette per le chance semplici (rosso/nero, alto/basso, pari/dispari) ecc
Nel gioco della roulette p = 1/37, q = 1-p ecc

In realtà si potrebbe usare anche la legge del teorema del limite centrale ma i calcoli sarebbero molto più complessi pertanto ci limitiamo a trattare l'argomento in un post successivo
Solo un breve cenno
f = numero di volte che l'evento con probabilità p può accedere in N lanci
p = prob che si verifichi l'evento
P (a < (f-pN)/sqrt(p(1-p)N) < b ) = P(gaussiana in forma standard con estremi a - b)
da cui con semplici passaggi algebrici si deduce i valori di a, b

Osservazione: calcolando la medie aritmetiche di tutte le estrazioni sappiamo che la distribuzione delle medie segue la curva normale di probabilità quindi la media dei numeri estratti  cadrà negli intervalli:

[np-3*sqrt(npq) - np+3sqrt(npq)] con 99,7 % probabilità
[np-2*sqrt(npq) - np+2sqrt(npq)]con 95 % probabilità
[np-1*sqrt(npq) - np+1*sqrt(npq)] con  68 % probabilità



giovedì 3 maggio 2018

Sistema di crittografia semplice e sicuro

Un semplice sistema per la generazione e protezione delle password. Ad ogni servizio associamo un codice. Nel fogli Excel quel codice viene inviato ad una funzione (segreta non visibile) la quale visualizza in output solo il risultato delle operazioni che è un numero. La password sarà data da una prima parte letterale che descrive il servizio e da una successiva parte che è il numero calcolato dalla funzione segreta. In questo modo possiamo evitare di ricordare le password ma avere comunque password molto sicure
Nemmeno il proprietario del file conosce la formula in teoria perché non è visibile
lo stesso meccanismo può essere usato per concordare password tra due soggetti che comunicano a distanza: basta che i due soggetti hanno lo stesso file. L'unica cosa che devono trasmettersi è il codice - servizio per concordare la medesima password senza trasmetterla