sabato 31 agosto 2013

Calcolare l'hash in modo semplice

Per calcolare l'hash di un documento possiamo semplicemente calcolare:

1) il numero dei caratteri
2) il numero delle vocali
3) il numero delle consonanti
4) il numero delle pagine
5) il numero dei paragrafi
6) numero dei caratteri compresi gli spazi
7) il numero delle lettere accentate
8) il numero dei segni di punteggiatura

abbiamo quindi un codice con 8 numeri. Se l'hash inviato e l'hash calcolato coincidono allora il documento è integro. Ovviamente può capitare una collisione del tipo "casa" "cosa" comportano lo stesso hash però sono casi molto limitati e dalla lettura del testo si capisce perfettamente l'eventuale errore (es basta applicare il correttore ortografico per determinare eventuali ambiguità)

giovedì 29 agosto 2013

L'equazione A^(n+1) = B^n + C^n e UTF

Per risolvere l'equazione diofantina A^(n+1) = B^n + C^n con A, B, C, n interi possiamo procedere così:
sia ^ l'elevamento a potenza
poniamo B = A * E , C = A * F con E, F interi a piacere.
Sostituendo otteniamo A^(n+1) = A^n E^n + A^n F^n. Semplifichiamo e otteniamo A = E^n +F^n

quindi lo schema risolutivo di A^(n+1) = B^n + C^n sarà dato da

A = E^n +F^n
B = A * E
C = A * F





con E, F interi a piacere e n intero fissato

Ovviamente da A^(n+1) = B^n + C^n deriva anche B^n = A^(n+1)-C^n

Questa piccola dimostrazione è anche sufficiente a provare che nell'ultimo teorema di Fermat  non ci possono essere soluzioni intere per B e C multipli interi di A (A^n = B^n + C^n)

Dal momento che A^(n+1) = B^n + C^n ha sempre soluzione (infinite) provare l'ultimo teorema di fermat equivale a provare che B^n + C^n = D^n non ha soluzioni ovvero che non ha soluzioni intere
D^n = A^(n+1) . Possiamo scrivere (D/A)^n = A  e se A non divide D l'equazione è ovviamente impossibile non essendo possibile che un numero decimale elevato ad una potenza intera sia un intero.
Tuttavia con riferimento a D^n = A^(n+1) si vede che basta porre A=k^n,  D=kA con k intero qualsiasi

lunedì 26 agosto 2013

Semplici applicazioni della teoria dei numeri

-pubblicazione riservata degli esiti di un esame. Il docente assegna a ogni studente un numero che lo studente moltiplicherà per la propria matricola ottenendo CM =V. gli esiti saranno pubblicati mettendo on line i numeri V. Ogni studente conoscerà il proprio esito leggendo scegliendo il V che è proprio il prodotto della sua matricola e del suo codice personale. Ci sono delle varianti: il codice personale potrebbe essere segreto quindi lo studente va a vedere tra gli V quale è  divisibile per la sua matricola. Ottiene quindi il codice personale e si presenta dal prof. per la prova orale

-assegnazione dei tutor all'Università: ogni docente del Dipartimento ha un numero progressivo da 0 a n secondo una tabella pubblicata. Lo studente calcola la sua matricola modulo n il numero che ottiene è il numero del suo docente tutor.


teorema. n^3+5n è sempre divisibile per 6
soluzione
Principio di induzione
supponiamo che per un certo n , n^3+5n è multiplo di 6 ovvero n^3+5n = 6k con k intero
Dobbiamo provare che (n+1)^3+5(n+1)  è multiplo di 6.
Sviluppando ho n^3+3n^2+3n+1+5n+5 = n^3+5n + 3n^2+3n+6= 6k+6 +3n(n+1)

6k+6 è sempre multiplo di 6
3n(n+1) è sempre un multiplo di 6 perché se n è pari 3n è un multiplo di 6 perchè in 3n c'è almento un 3 e un 2; se n è dispari 3(n+1) è sempre un multiplo di 6 perché n+1 è pari

teorema n^2+n è sempre divisibile per 2
soluzione
banale basta osservare che n^2+n = n(n+1) che se ha sempre un fattore pari sia che sia pari o dispari n

Il super-algoritmo per fattorizzare gli RSA con l'approssimazione del fattoriale

sappiamo che per n abbastanza grande
ln(n!) = n ln(n)  
in realtà ln(n!) = n ln(n)-n+0,5ln(2Pi*n)

e sappiamo se n = pq allora MCD(n,int( sqrt(n))!) = p , oppure q con p, q numeri primi

quindi
W= int(sqrt(n))
V = int(e^((W ln(W)-W+0,5+ln(2*Pi*W))))
while MCD(n, v) == 1
         V = V+1
print (V)
print(N/V)

l'algoritmo dà velocemente i fattori di p usando l'approssimazione del fattoriale di Stirling. Per numeri molto grandi si può usare una formula migliore per l'approssimazione di n!. Milgiore è la formula che approssima n! prima si arriva alla fattorizzazione

sabato 10 agosto 2013

Euqazioni diofantee cubiche

Vogliamo studiare l'equazione con soluzioni intere

X^3 + Y^3 = A^3 + B^3 +C^3 + D^3

Notazione ^ = elevamento a potenza

soluzione:
(a+b)^3 = a^3+b^3+ 3ab(a+b)
(c+d)^3 = c^3+d^3+ 3cd(c+d)

sommando membro a membro ho le soluzioni intere per l'equazione diofantea
X^3+Y^3=A^3+B^3+C^3+D^3 +3W
con
X=a+b
Y=c+d
A=a
B=b
C=c
D=d
W=ab(a+b)+cd(c+d)
allora W=0 sse ab(a+b)=-cd(c+d), ovvero se dato k intero k=ab(a+b) e k=-cd(c+d)
cioè quando a^2 b +ab^2-k = 0 (equazione in a) c^2 d +cd^2+k = 0 (equazione in c). per trovare i valori di a, b, c, d basterà allora verificare tra i tutti i divisori di k (per ogni k intero) quali valori sostituiti ad a (prima equazione) e a c (seconda equazione) danno valori interi di b (prima equazione) e di d (seconda equazione). Fissato k le prove da fare sono limitate .

si vede poi che per l'equazione A^3=B^3+C^3+D^3 possiamo ricorre a
A=M(M^3+N^3)
B= N(M^3+N^3)
C= M(M^3-2*N^3)
D=N(2M^3-N^3)
oppure a A= M(M^3+2N^3)
B=(M^3-N^3)
C=N(M^3-N^3)
D=N(2M^3+N^3)
per provarlo basta sotituire A, B, C, D con i loro parametri M, N nell'equazione e verificare l'identità
mentre per l'equazione A^2=B^2+C^2+D^2
basta porre
A= P^2+Q^2 +R^2
B = P^2+Q^2-R^2
C = 2RP
D= 2QR
per provarlo basta sostituire A, B, C, D con i loro parametri P, Q, R nell'equazione e verificare l'identità.
Esiste però un altra classe di soluzioni.
Dall'identità (a^2+b^2+c^2^2)^2=(a^2-b^2-c^2)^2+(2ab)^2+(2ac)^2 ottengo
A=a^2+b^2+c^2
B=a^2-b^2-c^2
C=2ab
D=2ac
un po' differente dalla precedente

venerdì 9 agosto 2013

RSA fattorizzazione con le potenze ricorsive

Algoritmo
^ è l'elevamento a potenza
N = pq, p q primi e non noti

N = N^(1/k)  N^(1-1/k)

k = 2, 3, 4, 5, .....

a = int [N^(1/k)]
b = int [N^(1-1/k)]

si calcola il MCD(n, a) e il MCD(n, b) per k = 2, 3, 4, 5, 6, ....
finché uno dei due MCD è diverso dall'unità ovvero finché
MCD(n, a) = p, q oppure MCD(n, b) = p, q

ecco una implementazione in Python:

import math;
def mcd(a, b):
 if b == 0:
  return a;
 else:
  return mcd(b, a%b);
def fatto(N):
 k = 2;
 while(mcd(N,math.floor(math.pow(N,1-1/k))) == 1):
  k =k+1;
 w = mcd(N,math.floor(math.pow(N,1-1/k)));
 print (w);
 print(N/w);




mercoledì 7 agosto 2013

Esercizi su equazioni diofantine particolarmente interessanti

Notazione ^ = elevamento a potenza

Equazione 1) A^3 = B^2+ C^2

soluzione: A^3 = (a+b)^3 = (a+b)^2 (a+b) = a(a+b)^2 +b(a+b)^2
sostituendo a^2 al posto di a, b^2 al posto di b ottengo
[(a^2+b^2)]^3 = [(a^2+b^2)]^2 a^2 + [(a^2+b^2)]^2 b^2
ovvero
A= a^2+b^2
B = (a^2+b^2) a
C = (a^2+b^2) b

oppure (a+b)^3 = a^2 (a+3b) + b^2 (b+3a) (*)
poniamo quindi a+3b = M^2, b+3a = N^2 ottenendo a = (3N^2-M^2)/8, b= (3M^2-N^2)/8
sostituendo  in (*) ho finalmente
(N^2+M^2)^3 = M^2 (3N^2-M^2)^2 + N^2 (3M^2-N^2)^2
quindi A= N^2+M^2, B=M(3N^2-M^2), C= N(3M^2-N^2)
steso risultato ponendo
(a-b)^3 = a^2(a-3b)+b^2 (3a-b)
(N^2+M^2)^3 = (3N^2-M^2)^2 M^2  + (N^2-3M^2)^2 N^2

Equazione 2) A^3 = B^2- C^2

soluzione: A^3 = (a-b)^3 = (a-b)^2 (a-b) = a(a-b)^2 -b(a-b)^2
sostituendo a^2 al posto di a, b^2 al posto di b ottengo
[(a^2-b^2)]^3 = [(a^2-b^2)]^2 a^2 - [(a^2-b^2)]^2 b^2
ovvero
A= a^2-b^2
B = (a^2-b^2) a
C = (a^2-b^2) b

oppure
(a-b)^3 = a^2 (a-3b) -b^2 (b-3a) (x)
poniamo a-3b = M^2, b-3a = N^2 ottenendo b =-(N^2+3M^2)/8, a = - (3N^2+M^2)/8
sostituendo in (x) e semplificando ottengo
(M^2-N^2)^3 = (3N^2+M^2)^2 M^2 - (N^2+3M^2)^2 N^2

Equazione 3) d^2 +8n = V^2
soluzione
si scelgono p, q interi tali che n = pq
n = pq con p, q non necessariamente primi
d = q-2p

Equazione 5) s^2-4n = G^2
soluzione
si scelgono p, q interi tali che n = pq
n = pq con p, q non necessariamente primi
s= p+q