mercoledì 30 marzo 2016

Quasi Beal


(9t^3+1)^3+(9t^4)^3 = (9t^4+3t)^3+1

(3^(3n+2)+1)^3+3^(12n+6) = (3^(4n+2)+3^(n+1))^3+1, n=0, 1, 2, 3

martedì 22 marzo 2016

Inverso in RSA

ed = 1 mod phi(n)

ed-1 = kphi(n)

d = [k*phi(n)+1]/e

pongo k= 1, 2, 3, .... finché d non è intero (di solito bastano pochi passaggi)

oppure e = 1, 2, 3, ..... finché ed = 1 mod phi(n) non è verificata (forza bruta)

In Python:


import math;
def inverso(e, phi):
k = 1;
d = (k*phi+1)/e;
while(d != math.floor(d)):
k =k+1;
d = (k*phi+1)/e;
print(d);


def inverso2(e, phi):
e = 1;
k = (e*d-1)/phi;
while(k != math.floor(k)):
d = d+1;
k = (e*d-1)/phi;

print(d);

domenica 13 marzo 2016

Un nuovo algoritmo per il calcolo del MCD

MCD(98, 12) = x
ovviamente  1< x <= min(98, 12)

s = 98+12= 110 = 5*11*2

divisori non banali di s sono 5, 11, 2, 5*11, 5*2, 11*2

x = 5, 11, 2 , ....
5 non divide 98, 12 e quindi nemmeno i multipli di 5
11 non divide 98, 12 e quindi nemmeno i multipli di 11
2 divide 98, 12 

allora il MCD(98, 12) = 2

analogamente nei casi più complessi

MCD(a, b) = x
s = a+b allora  x deve dividere s.

ALGORITMO PIU' VELOCE:

a > b MCD(a,b) = x , se a = c mod b allora x è un divisore di c con c diverso da zero
se c  = 0 allora MCD(a, b ) = b

MCD(98, 12)= x

98 mod 12 = 2 diverso da 0 allora il MCD(98, 12) deve essere 2 o un suo divisore quindi 2

se il modulo fosse stato zero allora il MCD tra i due numeri sarebbe stato il più piccolo tra i due


martedì 8 marzo 2016

RSA ancora possibili algoritmi

RSA

N=PQ, P e Q primi
se esistono x, y interi positivi tali che n = x+y e MCD(x,y) != 1 allora MCD(x, y) = P

analogamente nel caso n = x-y

Quali punti di partenza ?

Es:
x = int(n/2), x++
x = int(sqrt(n)), x++
x = 1, x++