advertisement

Numeri primi in battere e primi in levare

50 %
50 %
advertisement
Information about Numeri primi in battere e primi in levare
Education

Published on March 2, 2014

Author: armellini

Source: slideshare.net

Description

una nuova tecnica di fattorizzazione dei numeri RSA
advertisement

Numeri primi in battere e primi in levare Di Cristiano Armellini, cristiano.armellini@alice.it I numeri primi si possono dividere in due categorie ben distinte: primi in battere e primi in levare. I primi (in battere) si possono esprimere come la somma di due quadrati e al tempo stesso si rappresentano nella forma 4a+1 (sono cioè congrui a 1 modulo 4), i secondi non si possono mai scrivere come la somma di due quadrati e si rappresentano nella forma 4b+3 (sono cioè congrui 3 modulo 4) . Nel caso di un problema RSA abbiamo n=pq dove p, q sono grandi numeri primi da trovare dato il numero n. Abbiamo tre casi possibili. Caso 1) p, q sono in battere n  pq  (4a  1)(4b  1)  4(4ab  a  b)  1, ovvero 4 | (n-1) n  1  4(a  b) troviamo ab in funzione di a+b ab  (potevamo ovviamente fare anche l’inverso 16 ovvero trovare a+b in funzione di ab) Ricordando una importante proprietà delle equazioni x 2  Sx  N  0, x  a, b; N  ab, S  a  b abbiamo che x 2  Sx  di II grado: n  2  4S  0 ovvero 16 semplificando 16 x  16 Sx  n  1  4 S  0 . Ricordando che il delta deve essere maggiore di zero (siamo infatti ricercando le soluzioni intere) ho che : 2 2S  4S 2  4S  1  n n 1 x ,S  , x  a, b e iterando S si arriva presto al risultato 4 2 Caso 2) p in battere, q in levare n  pq  (4a  1)(4b  3)  4(4ab  3a  b)  3 ovvero 4 | (n-3) 2 In questo caso p  q  4( a  b  1) , quindi x  4( a  b  1) x  n  0 detto S=a+b+1 ho che x  2S  4S 2  n , S  n / 2 Caso 3) p, q in levare n  pq  (4a  3)(4b  3)  4(4ab  3(a  b))  9 , ovvero 4|(n-9) n  9  12(a  b) , N  ab, S  a  b e Il caso 3) è quindi simile al caso 1) N  ab  16 2 S  4 S 2  12 S  9  n 2 x  Sx  N  0, x  a, b , x  , con il delta maggiore di zero 4 n 3 ovvero con S  . Anche qui potevamo fare un scelta differente ovvero trovare S in 2 funzione di N invece che N in funzione di S. Lasciamo al lettore lo sviluppo in dettaglio dei singoli calcoli. In realtà è ben nota un’altra caratterizzazione dei numeri primi, ovvero tutti i numeri primi si possono esprime nella forma 6 a +1 oppure nella forma 6 b –1.

Ragionando come sopra e omettendo i calcoli algebrici ottengo Caso 1) p  6a  1, q  6b  1 n  (6a  1)(6b  1)  6(6ab  (b  a ))  1  n , ovvero 6 | (n+1) Qui l’attacco ai fattori si fa tendo conto che D  b  a, S  a  b, N  ab e che S 2  4N  D 2 , S 2  4N Caso 2) p  6a  1, q  6b  1 n  (6a  1)(6b  1)  6(ab  a  b)  1 , ovvero 6 | (n-1) Da questa relazione troviamo N = ab in funzione di S=a+b oppure l’inverso e li sostituiamo in x 2  Sx  N  0 imponendo il delta maggiore di zero per trovare x = a, b interi. Caso 3) p  6a  1, q  6b  1 n  (6a  1(6b  1)  36ab  6(a  b)  1 ovvero 6 | (n-1) simile al caso 2) cambia solo la relazione che lega S con N. Sviluppare programmi in C/C++ o in Python che fattorizzano gli interi con questi algoritmi è molto semplice. La velocità della scomposizione in fattori dipende dall’impiego dell’equazione di II grado e della caratterizzazione dei numeri primi. Dire che un numero primo p si può esprime nella forma p = 6 a+1 non vuol dire che per ogni valore di a ottenendo un p primo ma che al contrario esiste tutta una classe di primi che si possono esprimere nella forma p = 6 a +1 per qualche a intero. In definitiva abbiamo i seguenti casi: n  (4a  1)(4b  1) x 2  2(2(a  b)  1) x  n  0 x  v  v 2  n , x  p, q v  2 s  1, s  a  b, s  n 1 2 n  (4a  3)(4b  3) x 2  2(2(a  b)  3) x  n  0 x  p, q, x  c  c 2  n c  2(a  b)  3  2 s  3 s  a  b, s  ( n  3) / 2 n  (4a  1)(4b  3) x 2  2[2(a  b)  2]x  n  0 x  c  c 2  n , x  p, q c  2(a  b)  2, s  a  b s n 2 2

n  (6a  1)(6b  1) x 2  2(3(a  b)  1) x  n  0 c  3(a  b)  1, s  a  b 3s  1  n , s  n 1 3 n  (6a  1)(6b  1) x 2  2(3(a  b)  1) x  n  0 c  3(a  b)  1, s  a  b 3s  1  n , s  n 1 3 n  (6a  1)(6b  1) x 2  2(3(a  b)) x  n  0 x  c  c 2  n , c  3(a  b)  3s s  n /3

Add a comment

Related presentations

Related pages

armellini / Numeri primi in battere e primi in levare.pdf

No preview is available for Numeri primi in battere e primi in levare.pdf. To view it, click the "Download" tab above.
Read more

Numeri primi in battere e primi in levare - HubSlide

Transcripts - Numeri primi in battere e primi in levare. 1. Numeri primi in battere e primi in levare Di Cristiano Armellini, cristiano.armellini@alice.it ...
Read more

Blogghetto: gennaio 2010 - dionisoo.blogspot.de

... (battere, battere, battere levare battere). ... La musica dei numeri e dell ... "3 è primo, 5 è primo, 7 è primo, quindi tutti i dispari sono primi
Read more

armellini.pbworks.com

Title: Numeri primi in battere e primi in levare Author: cristiano armellini Created Date: 3/4/2014 11:56:46 AM
Read more

"L'Italia è tra i Paesi con la più bassa tassazione ...

... replica con numeri e ... vecchietti andranno a prendere l'acqua come nei primi del 900 alla ... che si pagano vogliono levare proprio quella ...
Read more

NUOVO CIAO AMICI

Tutti questi primi attori potranno ... Le accezioni tecniche « downbeat » e « upbeat » indicano il battere e il levare, ... nei prossimi numeri, ...
Read more

Blog di Armellini Cristiano: Numeri primi in battere e in ...

Numeri primi in battere e in levare e fattorizzazione degli RSA Numeri primi in battere e primi in levare from Cristiano Armellini. Pubblicato da
Read more

Esorcismo e preghiere di liberazione - Risposte ad alcune ...

Come lei ha cominciato a dire le dieci “Ave Maria” quest'uomo ha cominciato a battere forte i piedi sul pavimento ma ... ai primi tempi, noi ...
Read more

nogood.it/gibson » concerto

Basta poco a rendere storico un concerto, ... BATTERE E LEVARE 06 ... Oggi invece mi ricorda di un ragazzino che provava a muovere i suoi primi ...
Read more

Csen Calcio Firenze e Prato - facebook.com

Csen Calcio Firenze e Prato, Firenze (Florence, Italy). 2,089 likes · 128 talking about this · 30 were here. L'ente di promozione sportiva riconosciuto...
Read more