martedì 31 dicembre 2013

Come creare l'e-learning in modo semplice

Equazioni diofantine che derivano dalla fattorizzazione

Dal problema della fattorizzazione dei numeri sia n=pq, q =kp+a allora possiamo scrivere che (kp+a)p=n ,  il che ci porta, dopo semplici calcoli ad una equazione di II grado in pkp^2+ap-n=0, dove possiamo fissare k e far variare a (caso più frequente e conveniente) oppure fissare a e far variare k. Notiamo che se k pari allora a è dispari, mentre se k è dispari allora a è pari.
L'equazione di II grado ci porta alla soluzione dell'equazione diofantea a^2+4nk=b^2:

a^2+4nk-b^2=0
n=pq
q=kp+a

ad esempio conoscendo n , p, q (p,q non necessariamente primi ma comuqnue una fattorizzaizone per n) e k , si trova a qundi b

domenica 29 dicembre 2013

Riassunto delle nuove tecniche di crittografia quantistica

Crittografia bisimmetrica

A e B vogliono comunicare in modo sicuro.
A sceglie un numero intero per esempio 9
B sceglie un numero intero per esempio 2

In generale i numeri scelti non dovranno essere primi

a questo punto A invia a B una applicazione compilata (exe) dove all'interno del codice ha inserito il suo numero. L'applicazione consente a B di inserire il proprio numero e di fare la moltiplicazione tra i due numeri, ottenendo quindi 9 x 2 = 18. Questo risultato A lo invia per posta a B. A e B quindi dividendo per il numero che hanno scelto otterranno l'altro numero , cioè A otterrà il numero segreto di B e B otterrà il numero segreto di A. Se un intruso intercettasse la comunicazione potrebbe solo catturare il prodotto dei due numeri cioè 18 ma potrà sapere se 18=9*2 oppure 18=6*3. Se A e B scelgono numero molto grandi le possibilità di moltiplicano rendendo molto difficile un attacco per tentativi. A può comunicare con B usando una doppia chiave simmetrica la sua e quella di B, B a sua volta prima decifrerà con la sua chiave e poi con quella di A. In questo modo la comunicazione è sicura e A e B sanno con certezza chi è il loro interlocutore.
Questo algoritmo sfrutta il fatto che dato un numero intero la decomposizione in fattori (non primi) non è unica. Ad esempio 30=3*10=15*2. Dall'eseguibile (exe) non è possibile ricavare il codice sorgente quindi quando A invia il programma a B nessuno può sapere quale numero A abbia scelto e quando B inserisce il proprio numero nel programma questo viene mascherato da asterischi per evitare che qualcuno lo possa copiare. Il prodotto dei due numeri può essere inviato in un canale insicuro per i motivi sopra esposti. La password comune potrebbe essere ottenuta anche come somma di x, y dei due numeri segreti di A e B oppure un numero ottenuto come la loro unione.
In realtà A e B potrebbero concordare anche p, q primi a patto che p, q siano molto grandi e quindi n=pq sia molto difficile da fattorizzare per chi intercetta la comunicazione.




venerdì 27 dicembre 2013

Crittografia quantistica

In questo breve articolo descriverò un meccanismo che il linea teoria potrebbe essere utilizzato per implementare un sistema di crittografia quantistica. Supponiamo che A e B siano due soggetti che vogliono comunicare e per farlo utilizzeranno un algoritmo di crittografia simmetrica come ad esempio quello del cifrario monouso di Vernam (cifrario perfetto). A inizierà a generare una serie di stati in modo casuale ad esempio lanciando una moneta dove per convenzione T=testa = 1, C= croce =0. Lo stesso farà B. A otterrà una sequenze del tipo TCTTCTCC che corrisponde alla sequenza numerica 10110100 e B invece otterrà qualcosa di simile a CTTTCTCT che corrisponde a 01110101. Supponiamo ora che A e B possano inserire le sequenze che hanno scelto in modo casuale in un sistema informatico in modo protetto (ovvero mentre digitano la sequenza a video comparo solo una serie di asterischi). Il programma dovrà fare solo la differenza numero per numero (bit per bit) delle due sequenze inserite e dovrà visualizzare a video il risultato. Nel nostro caso 1, -1, 0, 0, 0, 0, 0, -1. L’hacker potrà solo visualizzare quest’ultima sequenza e quindi dove c’è 1 oppure -1 potrà ricavare gli stati ai A e B perché -1 =0-1 mentre 1=1-0 mentre non potrà farlo per gli stati 0 in quanto 0=0-0 oppure a 0=1-1. Questi stati indicheranno i bit che costituiranno la password (parola chiave) che A e B utilizzeranno per la crittografia simmetrica e quindi scarteranno gli stati corrispondenti della differenza -1, 1. A e B quindi avranno costruito la password che è 11010 ovvero gli stati che casualmente hanno concordato. Per ottenere una password sufficientemente lunga dovranno generare una sequenza di molti bit (almeno 100). Il problema è costruire l’applicativo informatico che consenta di inserire la sequenza scelta da A e B, in modo da calcolare la differenza bit a bit ma non di farla visualizzare da altri, tutto questo senza utilizzar i fotoni. In realtà si può fare anche la somma bit a bit usando la somma troncata o l'operatore XOR  infatti 1+1=10 (0 troncato), 0+0=0 ,mentre 1+0=1, 0+1=1: 0 xor 0 = 0, 1 xor 1 = 0, 0 xor 1 = 1 xor 0 = 1 Anche questa volta solo gli stati 0 sono stati comuni in quanto dalla  conoscenza di essi non è possibile risalire a chi li ha generati. Di seguito un programma che simula la creazione di una chiave comune. Alice inserisce nel codice sorgente la stringa dei suoi stati, poi compila il codice e invia l'eseguibile a Bob che inserisce la sua stringa e ottiene la differenza: gli stati pari a 0 sono quelli comuni che solo Alice e Bob sanno come sono stati generati se come 0-0=0 o come 1-1=0: questi stati noti solo a loro due costituiranno la password comune, gli altri verranno cancellati. Nessuno può, a partite dall'eseguibile, ricavare il codice sorgente e quindi  un pirata informatico non può dal file .exe risalire alla scelta degli stati di Alice.


venerdì 20 dicembre 2013

La verifica in PARI/Gp della congettura dei primi gemelli e distribuzione dei primi

{gemelli(n)=local(i, g);
g=0;
i=3;
while(i<=n, if(isprime(i) && isprime(i+2),print("---"); print(i); print(i+2);print("---"); g=g+1); i=i+2);
print(g);
}

{gemelli2(n, m)=local(i, g);
g=0;
i=n; /* n dispari 
while(i<=m, if(isprime(i) && isprime(i+2),print("---"); print(i); print(i+2);print("---"); g=g+1); i=i+2);
print(g);
} 

/* altri algoritmi per i primi gemelli e il calcolo dei primi
{twins(n)=local(s);
s=0;
forprime(p=2, n, if(isprime(p+2), s++)); return(s)}

/*primi minori o uguali a x
pi(x, c=0)=forprime(p=2,x,c++); c;

giovedì 19 dicembre 2013

Il problema della somma nei numeri RSA


clicca sull'immagine per ingrandire e leggere il testo

mercoledì 18 dicembre 2013

Relazioni interessanti per equazioni diofantine

Equazione n=x^2+y^2+z^2+w^2

si risolve osservando che:
(a^2+b^2)(c^2+d^2)=(ac)^2+(bc)^2+(ad)^2+(bd)^2


Equazione n=x^2+y^2 (caso particolare della precedente)
osserviamo che
(a^2+b^2)(c^2+d^2)=(ad+bd)^2+(ad-bc)^2

martedì 17 dicembre 2013

Una relazione matematica interessante

E' facile notare che p^2+q^2 =(p+q)^2-2pq
dove p, q sono interi

se n=pq, s=p+q e sostituendo n =(s^2-p^2-q^2)/2 nella  x^2-sx+n=0 troviamo, imponendo il delta maggiore di zero che p^2+q^2>(s^2)/2 ovvero p^2+q^2 > 2n perché (s^2>4n).

Queste relazioni  possono essere molto utili negli algoritmi di fattorizzazione

Analisi matematica di giochi e e lotterie

lunedì 16 dicembre 2013

Casi speciali per numeri RSA


La distanza dei numeri primi

Recentemente hanno dimostrato che la massima distanza tra due primi consecutivi è inferiore a 10^70.

Questo implica che deve esistere un intero n tale che per ogni m >  n deve capitare che

  •  m!+1 e m!+(m+1) non possono essere contemporaneamente primi. Infatti m!+2, m!+3, ....m!+m sono sicuramente composti
Ovviamente m deve essere un numero pari.

lunedì 9 dicembre 2013

Un generatore di numeri primi e sule applicazioni alla fattorizzazione

Tutti i numeri primi devono finire (ultima cifra) per 1, 2, 7, 9.

Quindi tutti i numeri primi si possono esprimere in una delle forme

p=10a+1
p= 10b+3
p=10c+7
p=10d+9 

con le ovvie condizioni che

MCD(10b, 3)= 1
MCD(10c, 7)=1
MCD(10d, 9)= 1

e a, b, c, d interi positivi

e nel caso in cui p = 10d+9 occorre verificare che p non sia un quadrato perfetto. Infatti , un'altra importante osservazione che gioca un ruolo molto importante anche nella fattorizzazione dei numeri interi è che  ogni quadrato perfetto deve finire con una delle cifre 0 (solo per potenze di 10), 1, 4, 5, 6, 9. Ovviamente non sempre le formule danno numeri primi, anzi molte volte per certe scelte dei parametri i numeri saranno composti ma la percentuale sarà buona.
Se n = pq allora per trovare i fattori p, q basterà trovare un h tale che MCD(n, (10h+1)(10h+3)(10h+7)(10h+9)) sia diverso da 1. Una interessante possibilità è considerare la funzione g(x,y,u,v, k)=(10x+1)(10y+3)(10u+7)(10v+9)(10k+5) che al variare dei parametri interi x, y, u, v, k dà sempre numeri composti, quindi costituisce un valido crivello

Vediamo un interssante esempio applicativo
se devo fattorizzare 187 in base alle condiderazioni precedenti  n=187=pq=(10a+1)(10b+7)=100ab+10(7a+b)+7, ove a, b = 0,1, ....9 Si deduce che a=b=1 ovvero 187=11*17
nel caso di fattori a tre cifre potevo scrivere p = 100a+10b+3. ecc dove a, b possono valere tra 0....9

nel caso 377=13*29 = (10a+3)(10b+9)=100ab+10(9a+3b+2)+7
ora risolviamo 9a+3b+2=7 modulo 10 ovvero a=1, b=2 che ci dà la soluzione finale.
e dato che 9a+3b+2=17  , 17-7=10 allora ab+1=3=3 modulo 10

Il problema della fattorizzazione si riduce alla soluzioni delle equazioni lineari modulari a più incognite, argomento sul quale occorre fare molta ricerca
in ogni caso su termine può essere solo  9a+3b+2-7=0,  9a+3b+2-7=10, 9a+3b+2-7=20, 9a+3b+2-7=30,.........9a+3b+2-7=90 e quindi l'analisi dei casi è sempre finita perché il riporto può essere solo un numero da 0 a 9.