venerdì 23 maggio 2014

Una nota sull'ultimo teorema di Fermat

Nell'utimo teorema di fermat x n +yn =z deve essere z < x+y, infatti se fosse z > x+y  allora z = x+y+a con a > 0 e quindi x^n + y^n = (x+y+a)^n conduce subito ad un assurdo perché avremo
x^n +y^n = x^n+y^n +(termini positivi>0)
Dunque z = x+y-a , a > 0
Tuttavia x < z, y < z quindi x+y < 2z ovvero z > (x+y)/2
Indipendentemente da n dovrà essere (x+y)/2 < z < x+y

Fissato quindi il livello x+y=k , possiamo andare a trovare tutti gli z che potrebbero soddisfare la relazione concludendo che per n > 2  non ce ne sono di interi (verifica parziale)

Inoltre se x pari e y è pari  anche z deve essere pari
se x è dispari e y è dispari , z deve essere pari
se x  pari e y dispari (o viceversa), z deve essere dispari

Questo aiuta a velocizzare la ricerca

lunedì 19 maggio 2014

Lista dei primi con il software Mathematica

i:=3
While[i<1000, If[PrineQ[i]==True, print[i]]; i=i+2]
-------------------------

i:= 3
While[i<1000, If[Gcd[FloorN[[Sqrt[i]] ]!!, i] == 1, Print[i]]; i=i+2]
--------------------------------

i := 3
While[i < 1000, If[Mod[(i-1)!, i] == i-1, Print[i]]; i = i+2]
--------------------------------------------------------------





domenica 18 maggio 2014

Mathematica e PARI/GP: algoritmi di fattorizzazione per RSA

Programmi per fattorizzare numeri RSA e creare una lista di numeri primi

Mathematica

n := 187
i := 3
While[ n/i != Floor[n/i], i = i+2]
Print[i]
Print[n/i]
--------------------------------
n := 187
i := 1
p := Prime[i]
While[n/p != Floor[n/p], i=i+1; p = Prime[i]]
Print[p]
Print[n/p]
-------------------------------
n := 187
i := 1
p := Prime[i]
While[n/p != Floor[n/p], p = NextPrime[p+1]]
Print[p]
Print[n/p]
---------------------------------------------
m := 1000
i := 1
While[Prime[i] < m, Print[Prime[i]], i = i+1]
-----------------------------------------------
m :=1000
i:=1
p:=Prime[i]
While[ p < m, Print[p]; p =NextPrime[p+1]]
--------------------------------------------------
PARI/GP
{fattori(n) = local(i);
i := 1
p = nextprime(i);
while(n/p != floor(n/p), p = nextprime(p+1));
print(p);
print(n/p);
}
-----------------------------------------------
{lista(m) = local(i);
i:=1;
p = nextprime(i);
while(p < m, print(p), p = nextprime(p+1));
}

giovedì 15 maggio 2014

Mathematica: fattorizzazione e equazioni diofantee

Con il Mathematica è possibile :

1) fattorizzare un numero usando gli algoritmi delle equazioni di II grado
Solve[x^2-s*x+187==0, {x, s}, Integers] link  (parte soluzioni intere)

n:=2701
Table[NSolve[x^2-s*x+n==0, x], {s, n, 2*Floor[Sqrt[n]], n}]

2)  risolvere le equazioni diofantee
caso delle terne pitagoriche Solve[x^2+y^2==z^2, {x, y, z}, Integer]  link (parte soluzioni intere)

caso equazione di Bezout  Solve[3*x+4*y==1, {x, y}, Integers]  link (parte soluzioni intere)

mercoledì 14 maggio 2014

RSA: fattorizzazione tramite analisi dell'ultima cifra

sia n=pq con p, q numeri primi anche molto grandi (problema RSA).
Dato che un numero primo deve terminare (ovvero la sua ultima cifra deve terminare) con 1, 3, 7, 9 allora anche n deve terminare con una delle seguenti cifre 1, 3, 7, 9
caso 1) n=pq termina con 1
possiamo avere:
(2x+1)(2y+1)=n oppure
(2x+9)(2y+9)=n oppure
(2x+3)(2y+7)=n

caso 2) n=pq termina con 3
possiamo avere:
(2x+1)(2y+3)=n oppure
(2x+7)(2y+9)=n

caso 3) n=pq termina con 7
possiamo avere:
(2x+1)(2y+7)=n oppure
(2x+3)(2y+9)=n

caso 4) n=pq termina con 9
possiamo avere:
(2x+3)(2y+3)=n oppure
(2x+7)(2y+7)=n oppure
(2x+1)(2y+9)=n

in tutti i casi dobbiamo porre y =x+m (y=x-m) e quindi ottenere una equazione di II grado in x con parametro m  (positivo o negativo ma itero) che varierà in base al campo di esistenza delle radici reali  dell'equazione finché non otteniamo un valore di x intero (quindi anche di y) => la  fattorizzazione di n. Potevamo mettere x=y+m (x=y-m) con una equazione di II grado in y e parametro m.
Possiamo anche considerare come ulteriore alternativa la relazione Z^2-sZ+n=0, dove s=p+q Z = p, q
Per agevolare i calcoli possiamo fare le semplificazioni usando il PARI/GP, Mathematica o Maxima.

mercoledì 7 maggio 2014

Metodo della minima distanza nella fattorizzazione RSA


funziona bene quando k è circa p/q e negli RSA questo valore   è in genere piccolo

import math;
def mcd(a, b):
    if b == 0:
        return a;
    else:
        return mcd(b, a%b);
def facto(n, k):
 d = 0;
 delta = math.sqrt(d**2+4*n*k);
 while(delta != math.floor(delta)):
  d = d+1;
  delta = math.sqrt(d**2+4*n*k);
 v = d+delta;
 p = mcd(n, v);
 q = n/p;
 print(p);
 print(q);

lunedì 5 maggio 2014

RSA e JAVA

semplici algoritmi per fattorizzare numeri RSA in JAVA

modello algoritmico dell'equazione di II grado x^2-sx+n=0
import java.io.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
       double p;
       double q;
       double n;
       double s;
       double disc;
       n = 187;
       s = 2*Math.floor(Math.sqrt(n));
       disc = Math.sqrt(Math.abs(s*s-4*n));
       while(disc != Math.floor(disc)){
           s = s+2;
            disc = Math.sqrt(Math.abs(s*s-4*n));
       }
       p = (s-disc)/2.;
       q = (s+disc)/2;
       System.out.println(p);
       System.out.println(q);

    }
}
attacco a forza bruta
public class Main {

    public static void main(String[] args) {
       double p, i;
       p = 187.0;
       while(p!=1){
       i = 1;
        while ( p%i != 0 ){
            i = i+2.0;
        }
          System.out.print(i);
          System.out.print(" X ");
          p = p/i;
          
   }

    }
  }

domenica 4 maggio 2014

Lo scambio della chiave in canali insicuri

 A e B con un interruttore azionano all'unisono in tempi definiti due lampadine ognuno una per ogni stanza. Lo stato delle lampade corrisponde a un bit 1= acceso, 0 = spento. A non sa cosa farà B e nemmeno B sa cosa farà A quando devono decidere simultaneamente di accendere o segnare una lampada. In alcuni casi la scelta sarà comune e allora all'istante stabilito A e B avranno deciso, per caso, di accedere o di spegnere le lampade nello stesso modo. Queste sequenze di bit costituiranno la chiave comune che nessuno potrà intercettare. La chiave comune è la password da usare nella crittografia simmetrica per lo scambio di informazioni. Il sistema è sicuro se si è certi che nessuno possa verificare la presenza o meno della corrente nei circuiti nel momento dell'invio del segnale. La procedura può essere automatizzata e velocizzata con dei chip in modo che A e B non debbano far nulla ma solo attendere l'esito dei confronti.




giovedì 1 maggio 2014

Il Fortran 77-90 e la fattorizzazione dei numeri RSA

Ecco di seguito un programma scritto in Fortran 77 che fattorizza un numero RSA n =pq con p, q primi dove l'algoritmo usato è quello dell'equazione di II grado x^2-sx+n=0. Il listato può essere adattato anche a tutti gli altri algoritmi che si basano su questo schema: è un quindi un modello di partenza.


        program fatt
      double precision s, n, p, q, disc
integer d
read (*,*) n
s = 2*int(dsqrt(n))
disc = dsqrt(abs(s*s-4*n))
p = (s-disc)/2.
        do 30 i=2,n
d = int(n/p)
        if(d*p.eq.n)goto100
s = s+2
disc = dsqrt(abs(s*s-4*n))
p = (s-disc)/2.
30    continue
100  write(*,*) p
q = (s+disc)/2.
write(*,*) q
        stop
        end

di seguito il codice in F90

program fatt
implicit none
real (kind = 8) :: s, n, p, q, disc
integer :: d
read (*,*) n
s = 2*int(sqrt(n))
disc = sqrt(abs(s*s-4*n))
p = (s-disc)/2.
do
d = int(n/p)
if(d*p == n) exit
s = s+2
disc = sqrt(abs(s*s-4*n))
p = (s-disc)/2.
end do
write(*,*) p
q = (s+disc)/2.
write(*,*) q
stop
end program fatt