lunedì 16 aprile 2018

Casi particolari della congettura di Beal e equazioni diofantine

equazione X^m + Y^n = Z^p
alcune soluzioni particolari

1+2^3 = 3^2
2^5 + 7^2 = 3^4
7^3+13^2 = 2^9
2^7 + 17^3 = 71^2
3^5 + 11^4 = 122^2
17^7 + 76271^3 = 21063928^2
1414^3 + 2213459^2 = 65^7
1414^3 + 2213459^2 = 65^7
43^8 + 96222^3 = 30042907^2
33^8 + 1549034^2 = 15613^3


l'equazione X^4+Y^2 = Z^3
ammette lo schema di soluzioni generale:

x = 6st(s^4-12t^4)
y = (s^4+12t^4)(s^8-408s^4t^4+144t^8)
z = s^8+168s^4t^4+144t^8

come è facile provare per sostituzione

domenica 15 aprile 2018

Una versione informatizzata del metodo di fattorizzazione del rho di Pollard

Fattorizzazione con il metodo del rho di Pollard

Versione in Python
m = mcm di una lista dei primi j numeri interi

import math;
def mcd(a, b):
if b == 0:
return a;
else:
return mcd(b, a%b);
def facto(N, m):
n = 2;
p = mcd(math.fmod(n**(m)-1, N),N );
while (p == 1):
n = n+1;
p = mcd(math.fmod(n**(m)-1, N),N );
q = N/p;
print(p);
print(q);

-------------------------------------------------------------
Versione in PARI/GP
{MCM(m)=
n = 2;
k = 1;
while(n <=m, k = lcm(n, k); n =n+1);
return(k);

}

{fact(N, m) =
n = 2;
while(gcd(lift(Mod(n^m-1, N)), N) == 1, n = n+1);
p = gcd(lift(Mod(n^m-1, N)), N);
print(p);
print(N/p);

}

In un attacco in parallelo basta assegnare ad ogni pc un differente valore di m.

mercoledì 4 aprile 2018

Frattali, numeri complessi e numeri primi

In base ad un famoso teorema ogni numero primo della forma p = 4n+1 si può scrivere come somma di due quadrati, ovvero p = 4n+1 = a^2+b^2, numero primo
ma a^2+b^2 = modulo(z)^2, ove z è un numero complesso della forma z = a+ib ed i è l'unità immaginaria. Questo tipo di numeri primi costituisce il 50% di tutti i numeri primi in quanto gli altri numeri primi sono esprimibili nella forma 4n+3.

Ora per ogni numero primo della forma p = 4n+1 rimangono determinate 8 coppie di numeri (a,b) tali che a^2+b^2 = p = 4n+1, quindi 8 numeri complessi nella forma z = a+ib. Esse sono:
(a,b), (-a, b), (a, -b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a)

Possiamo per ogni numero primo della forma 4n+1 trovare tutti i numeri complessi ad esso associati cioè tutte le coppie (a,b) tali che a^2+b^2 = p = 4n+1.

Quindi possiamo rappresentare graficamente queste coppie in un piano cartesiano: viene generato un frattale di questo tipo




lunedì 2 aprile 2018

Numeri semiprimi

n = pq con p e q primi es RSA

allora

ln(n) = ln(pq) = ln(p)+ln(q)

ln(p) = ln(n)-ln(q)
ln(p)ln(q) = ln(q)ln(n)-(ln(q))^2

u = ln(q)

Z^2-ln(n)Z+uln(n)-u^2=0
(ho usato il fatto che se M = ab S = a+b allora l'equazione Z^2-SZ+M=0, dà Z1=a, Z2=b)

delta > 0 => ln(n)^2-4(u*ln(n)-u^2) >0
(2u-ln(n))^2>0, sempre

y = (2u-ln(n))^2 parabola con minimo u = ln(n)/2 per valori minori del minimo è decrescente, per valori maggiori è crescente
ma
2u-ln(n) >0 oppure
2u-ln(n) < 0

ma u = ln(q)
quindi vuol dire che q > sqrt(n), oppure q < sqrt(n) come era ovvio aspettarsi
infatti se u > ln(n)/2 allora ln(q) > ln(n)/2
2ln(q) >ln(n)
ln(q^2) >ln(n)
q^2 > n
q >sqrt(n) ecc..

d'altra parte se n = pq e p=q allora q = p = sqrt(n) mentre se uno dei due fattori è maggiore della radq(n) l'altro dovrà essere per forza minore affinché il prodotto non cambi.

La dimostrazione porta quindi ad un risultato ovvio ma il procedimento è originale.
Questa proprietà spiega anche il crivello di Eratostene usato fin dall'antichità per trovare i numeri primi (tabella dei numeri primi)

Essendo sqrt(n) -3 < n/3 -sqrt(n) sempre per n > 3 allora questo vuol dire che è più conveniente andare a cercare i numeri primi fattori di n = pq nell'intervallo 3-sqrt(n) che maggiori di sqrt(n): nella'ltro intervallo ce ne sarebbero di più e sarebbero anche più grandi

martedì 27 febbraio 2018

Semplici tecniche di calcolo mentale: le moltiplicazioni e fattorizzazione

MOLTIPLICAZIONI
primo metodo
N = ab ?
N=ab = ((a+b)2)^2-((a-b)/2)^2
a, b dispari o entrambi pari

il problema si riduce nel calcolo dei quadrati che è semplice in quanto ogni quadrato si può ridurre in una somma più semplice di due numeri più semplici da gestire: c^2 = (u+v)^2 = u^2+v^2+2uv

Altro metodo: uso delle equazioni di II grado

N = ab

X^2-sX+N=0 X = a, b

s= (a+b)

N= sX-X^2

dove come X possiamo scegliere sia a che b (il valore che ci fa più comodo)

X^2 è riconducibile al problema di calcolare un quadrato (vedi sopra)

sX potrebbe essere una moltiplicazione più grande di N=ab ma il prodotto potrebbe essere più semplice, in caso contrario reiterare l'algoritmo e provare a calcolare sX usando Z^2-(s+X)Z+sX=0
sX = (s+Z)Z-Z^2, Z = s, X

FATTORIZZAZIONE
Anche qui usiamo l'equazione di II grado x^2-sx+n=0, n = ab s = p+q

ora x=p, q= [s+/-sqrt(s^2-4n)]/2
quindi si calcola in modo approssimativo la radice di n poi la si moltiplica per 2 e poi si considera tutti i numeri pari successivi finché sqrt(s^2-4n) non è un quadrato perfetto. A quel punto abbiamo trovato la soluzione