sabato 19 gennaio 2013

Serie di Fibonacci traslate

La distribuzione dei numeri primi nei problemi RSA

Nel classico problema di fattorizzazione  RSA n = pq con p, q primi. In genere p, q sono numeri molto grandi di dimensioni "simili" ovvero che hanno lo stesso numero di cifre. Allora se  p+q > 2radq(n) con radq = radice quadrata e se p = q/k per qualche k allora q + q/k > 2radq(n) ovvero
 q > [2k/(k+1)]*radq(n)
Al variare di k =1, 2, 3, 4, ,....10 abbiamo tutta una serie di "punti" critici dove poter cercare attraverso un attacco a fora bruta il fattore q e quindi la fattorizzazione di n
Dato che q/k= p  e  p < radq(n) ovvero q < k*radq(n) quindi:
[2k/(k+1)]*radq(n) < q < k*radq(n)


Possiamo sviluppare un piccolo programma in Python per la fattorizzazione:

import math;
def fatto(n):
    k = 1;
    while k <= 4:
            q = math.floor(2*k*math.sqrt(n)/(k+1));
            while q <= math.floor(k*math.sqrt(n)):
                    if n/q == math.floor(n/q):
                            print(q);
                            print(n/q);
                            return(1);
                    else:
                            if q/2 == math.floor(q/2):
                                    q =q+1;
                            else:
                                    q =q+2;
            k =k+1;

mercoledì 16 gennaio 2013

Altre semplici curiosità numeriche

Una curiosità della successione di Fibonacci

Un interessante teorema sulla congettura ABC

Teorema
Se MCD(a,b)= 1 e c = a+b allora MCD(c,a)=1, MCD(c,b)=1 ovvero MCD(a,b,c)=1

Dimostrazione:
se MCD(c,a)=d con d > 1 allora esistono u, v interi tali che uc+va=d d > 1 (Teorema di Bezout)
ovvero u(a+b)+va=d ovvero (u+v)a+ub=d ovvero MCD(a,b)=d, d > 1 contro l'ipotesi iniziale.
Analogamente se MCD(c,b) = d con d > 1 si arriva alle stesse conclusioni.

questo teorema vuol dire che se prendo a, b primi tra loro MCD(a,b)=1 allora c = a+b conterrà certamente fattori primi nella sua scomposizione che non sono presenti  né nella fattorizzazione di a né in quella di b e questo ci suggerisce un algoritmo, un metodo per trovare sempre nuovi numeri primi.

Questo vuol dire anche che rad(c) <  rad(abc)  e c > rad(c).

Corollario 1)
MCD(a, a+1) = 1 per ogni a intero
dim:
se c1 =dm, c2 =dn  con MCD(c1, c2) = d allora c2-c1 = dn-dm = d(n-m) = q . se q = 1 allora d = 1 e
 n-m = 1 ovvero c1 =n, c2 = m+1.

Corollario 2)
MCD(2a+1, 2a+3) = 1 per ogni a intero
la dimostrazione è simile al precedente

questi due corollari ci suggeriscono due tra le tante sequenze che possono essere usate per trovare sequenze infinite di numeri primi

Come possiamo applicare tutte questo nella teoria della fattorizzazione die numeri RSA ? se n = pq, con p, q numeri primi allora per trovare p, q basta trovare una sequenza c = a+b tale che MCD(n, c) sia divesa da 1

mercoledì 9 gennaio 2013

Fattorizzazione con i multipli

se n = pq con p, q primi

Supponiamo che p = q/k allora n = q^2/k ovvero q = radq(nk).

Quindi fissato k = 1, 2, 3, 4
possiamo trovare almeno un fattore come radq(nk)+/1, radq(nk)+-/2, ...... finché non troviamo un divisore.


ove radq = radice quadrata. In molti casi l'algoritmo si dimostra assai veloce.

e quindi questo prova che ci sono tutta una serie di punti dai quali i fattori devono essere scelti ben distanti (nuovi punti critici oltre a quelli già trovati)

giovedì 3 gennaio 2013

L'equazione "n!+A=x^2"

l'equazione diofantea n!+A=x^2 trova applicazioni nella congettura ABC. Ecco un programma in PARI/GP he trova e classifica le soluzioni intere. L'idea di base è fissato x trvare A n per ogni x intero.

{eq(x)=local(s);
n = 0;
A = x^2-n!;
s = 0;
while(s < 10, print("A= ", A, "n= ", n, "x= ", x); n=n+1;s=s+1; A=x^2-n!);
}

{list(x)=local(s);
s = 1;
for(s=1, 100, eq(x));
}

oppure fissando n faccio variare x:

{eq(n)=local(s);
x = 0;
A = x^2-n!;
s = 0;
while(s < 100, print("A= ", A, "n= ", n, "x= ", x); x=x+1;s=s+1; A=x^2-n!);
}

{list(n)=local(s);
s = 1;
for(s=1, 100, eq(n));
}

Grandi numeri in JAVA: Fibonacci e fattoriale

package fattoriale;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        BigInteger fatt = new BigInteger("1");
        BigInteger k = new BigInteger("1");
        BigInteger j = new BigInteger("1");
        long cont ;
        long n;
        n = 4;
        for(cont = 1; cont <= n; cont ++){
        fatt = fatt.multiply(k);
        k = k.add(j);
        }
        System.out.println(n);
        System.out.println(fatt);
    }
}

---------------------------------------------

package fibonacci;

import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
 BigInteger k = new BigInteger("1");
 BigInteger j = new BigInteger("1");
 BigInteger v = new BigInteger("1");
 long h, i;
 h = 10;
 System.out.println(j);
 System.out.println(k);
 for(i=1; i<=h; i++){
    v = j.add(k);
 
    System.out.println(v);
    j = k;
    k = v;
    
 }

    }

}
-------------------------------------------