venerdì 15 maggio 2015

La retta critica dei numeri primi

secondo lo schema "del 6"

 secondo lo schema del 4
(correzione: l'ultimo numero in tabella è 44 invece di 45)

sono evidenti le "rette critiche" in cui si distribuiscono i primi. In giallo i numeri primi

Sono tuttavia possibili anche altri schemi dello stesso tipo

giovedì 7 maggio 2015

Scomposizione RSA

n = pq RSA

si possono presentare solo i seguenti casi:

p = 6x+1, q = 6y+5
p= 6x+1,  q = 6y+1
p = 6x+5, q=  6y+5

con x = y+a

sostituendo in n =pq si arriva ad una equazione di II grado in y con parametro a e ponendo il delta maggiore di zero si determina una regione di variabilità per a

oppure x^2-sx+n=0

s=p+q e si prende come parametro u+v = a, anche qui  ponendo il delta maggiore di zero si determina una regione di variabilità per a


mercoledì 6 maggio 2015

Approfondimento sulle Terne pitagoriche

a^2-b^2=(a-b)(a+b)

a^2=(a-b)(a+b)+b^2

=> a-b = 1, a+b = c^2

=> a= (c^2+1)/2, b = (c^2-1)/2

=> ((c^2+1)/2)^2=c^2+((c^2-1)/2)^2

con c dispari ho tutte le terne pitagoriche

lo stesso metodo si può usare per provare che non esistono soluzioni per a^3+b^3=c^3, ricordando che
a^3+b^3=(a+b)(a^2-ab+b^2)
ma anche a^3-b^3 = (a-b)(a^2+ab+b^2)
sviluppando i sistemi per tutte le possibili combinazioni si arriva solo alle soluzioni banali non ammesse
Per valori maggiori di 3 dell'esponente il metodo rimane ancora valido ma diventa enormemente più complesso a causa dei numerosi casi da analizzare

domenica 3 maggio 2015

il crivello di Eratostene ottimizzato

crivello di Eratostene ottimizzato

T = tabella dei numeri primi = (2, 3, 5, 7, 11, 13, 17, 19,....) già calcolati ad esempio fino a 100

p = 101 è primo ?

p= 101 è dispari e l'ultima cifra non finisce per 5: un candidato possibile

sqrt(101) = 10,04


p1 = 2 < sqrt(101): si
101 mod 2 <> 0: si (è un passaggio inutile dato che 101 non è pari)


p2= 3 < sart(101)
101 mod 3 <> 0: si


p3= 5 < sqrt(101)
101 mod 5 <> 0: si (è un passaggio inutile visto che 101 non finisce per 5)


p4 = 7  < sqrt(101)
101 mod 7 <> 0: si

p5 = 11 < sqrt(101): no
stop: tutti i moduli sono diversi da zero quindi p = 101 è primo quindi si aggiunge alla lista dei primi e si procede con il successivo candidato.
il vantaggio del metodo è che si memorizzano solo i numeri primi e si fanno solo i calcoli necessari per essere sicuri che il candidato sia o no primo. Appena si trova un modulo pari a zero allora i calcoli si interrompono: quel numero non può essere primo perché ha un divisore non banale.

In base al teorema di numeri primi il metodo ha una complessità computazionale minore o uguale a sqrt(n)/ln(sqrt(n)) passi con n numero da sottoporre al test per inserirlo o meno nella lista dei primi.

La moltiplicazione veloce dei grandi numeri interi


N=7854*3127

X = 10,raggruppamento a due cifre

7854 = 78*X^2+54
3127 = 31*X^2+27

N = 7854*3127 = (78*X^2+54)(31*X^2+27) =
= 2418*X^4+2106*X^2+1674*X^2+1458=
= 2418*X^4+3780*X^2+1458=
(24*X^2+18)*X^4+(37*X^2+80)+14*X^2+58=
= 24*X^6+18*X^4+37*X^4+80*X^2+14*X^2+58=
= 24X^6+55*X^4+94*X^2+58=24559458

in generale se i numeri da moltiplicare sono grandi invece di raggrupparli a due a due possiamo raggrupperli a tre a tre, a quattro a quattro sempre ponendo X = 10

esempio: p = 785427=785*X^3+427, X= 10 e fare tutti i conti modulo 10^3 come nell'esempio precedente