Fisica e Matematica
Esiste ed esisterà sempre un forte legame tra Fisica e Matematica.
Spesso è un problema di Fisica a scatenare ricerche matematiche: ad esempio il problema del "gap di massa" o congettura di Yang e Mills è nato dalla Fisica e non si è trovato ancora una matematica adeguata alla risoluzione del problema, problema attualmente trattato con la Teoria dei gruppi ed in particolare i gruppi di Lie.
Altre volte è stata la matematica ad offrire spunti per la creazione di modelli in Fisica: la teoria dei Numeri dietro alla congettura di Birch e Swinnerton-Dyer, le forme modulari, la zeta di Riemann, l'ultimo Teorema di Fermat e le curve ellittiche E su un campo Fp, i numeri p-adici sono diventati strumenti ideali per la teoria delle stringhe e delle brane e la M-teoria.
Oppure il caso del legame che trovò G. Veneziano tra la funzione Beta e le interazioni forti del Modello standard: la Beta è legata alla funzione Gamma e di conseguenza alla funzione zeta di Riemann.
Articoli degli autori di Fisica e Matematica, propedeutici alla comprensione di cui sopra, sono presenti sul sito di "Rudi Mathematici": http://www.rudimathematici.com/blocknotes.htm
Su Riemann, problemi del Millennio e ulteriori articoli di Fisica e Matematica:
http://www.gruppoeratostene.com/articoli/articoli.htm
Alla prossima
sabato 21 novembre 2009
domenica 15 novembre 2009
Fattorizzazioni semiprimi e espansioni periodiche
Fattorizzazioni di un semiprimo con le espansioni periodiche di base 10 di 1/N
Cercare il periodo significa, da quanto visto, cercare il più piccolo valore k tale che B^k = 1 mod N. E una ricerca esaustiva non è sempre più veloce di una "Division Trial".
Tra le fattorizzazioni più curiose e simpatiche di un semiprimo N=p*q c'è la tecnica della "Espansione periodica in base 10 della frazione 1/N".
Facciamo un esempio: N=1517 con PARI/GP.
Step 1: troviamo la lunghezza del periodo T(1/N) della frazione 1/N
1/N=0.000659195781147000659195781147
dove per semplicità abbiamo marcato in bold rosso solo la "parte periodica" della frazione 1/N. Se contiamo le cifre di tale periodo (bold rosso) si ottiene che T(1/N)=15.
Step 2: Fattorizziamo la lunghezza del periodo della frazione 1/N
Fattorizziamo adesso la lunghezza del periodo T(1/N) = 15 = 3*5 (stesso risultato ottenibile da PARI/GP con factor(15)), dove k1=3 e k2=5
Step 3: troviamo il MCD (in inglese GCD) di N con 10^k1-1 e di N con 10^k2-1
GCD(1517,10^3-1)=37=p
GCD(1517,10^5-1)=41=q
Allora N=1517=37*41
Controprova
La contro-prova del metodo che valida l'esempio (poi lo dimostriamo generalizzando) è la seguente:
Sappiamo che N=1517=37*41
Ora cerchiamo per p=37 e q=41 i più piccoli valori k1 e k2 tali che siano intere le quantità:
(10^k1-1)/p=3
(10^k2-1)/q=5
Come si dimostra?
Intanto ricordiamo che lcm è il minimo comune multiplo (mcm), mentre LCM è il prodotto dei minimi comuni multipli in gioco; inoltre indichiamo con T il periodo di una frazione.
Se N=p*q è allora:
T(N)=LCM(T(p), T(q))
Se indichiamo g = GCD[T(p),T(q)] allora T(N) = T(p)T(q) / g.
Così per qualche fattorizzazione T(N) = abg noi avremo:
T(p) = ag e T(q) = bg
ed in conclusione
p = GCD [ N, 10^ag - 1 ]
q = GCD [ N, 10^bg - 1 ]
In tutto questo abbiamo usato la base B=10 ma nella dimostrazione al posto del 10 potevamo mettere genericamente B.
Simpatico no? E' un metodo che si applica bene e facilmente ad un numero semiprimo; mentre le cose si complicano di più se non è semiprimo o se il periodo non si riesce a individuare.
Se N è semiprimo possiamo saperlo ad esempio in PARI/GP con la funzione bigomega(N) che se è semiprimo restituisce 2. La bigomega fornisce il numero di fattori primi anche se ripetuti.
Esiste sempre un periodo? No, non sempre.
Se N è primo, 1/N è periodica ad eccezione del caso N=2 e N=5
Se N è semiprimo N=p*q non è periodica se p=q oppure p e q sono fattori primi uguali a 2 o potenze di 2 o uguali a 5 o potenze di 5 o prodotti di 2 e 5
Le difficoltà:
1. In PARI/GP occorre scriversi un algoritmo per individuare il periodo
2. Non sempre la frazione è periodica
3. Per N grandi PARI/GP restituisce il valore in notazione esponenziale (esempio 23 E-21)
Cercare il periodo significa, da quanto visto, cercare il più piccolo valore k tale che B^k = 1 mod N. E una ricerca esaustiva non è sempre più veloce di una "Division Trial".
L'esempio di prima era banale. Esaminiamo N = 66167. T(66167)=1092
La fattorizzazione è: 1092 = 2*2*3*7*13
Qui dobbiamo vedere come combinare le possibili partizioni di 1092. Ad esempio dopo qualche tentativo
si vede 1092=21*26*2 da cui ag=42 e bg=52. In questo caso T(p) e T(q) non sono coprimi.
Da qui:
GCD[66167,10^(21*2)-1] = 127
GCD[66167,10^(26*2)-1] = 521
Ovviamente basta calcolarne solo uno dei fattori, l'altro è ottenibile per divisione,
finchè non si ottiene un fattore non banale tale che GCD[N,B^k-1].
Questo tipo di fattorizzazione sicuramente potrebbe lavorare su numeri inferiori rispetto a N, ed è utile soprattutto per i semiprimi. Ma, come visto, non è detto che sia più veloce di una fattorizzazione di tipo trial.
Se avete idee a tal proposito, postatemele.
Se avete idee a tal proposito, postatemele.
Alla prossima
domenica 8 novembre 2009
Test di primalità
Sia P è l'insieme di numeri primi ed n un numero intero. Un numero primo per definizione è un numero divisibile solo per 1 e sè stesso.
Una tecnica, quindi, per verificare se n è primo è di dividerlo per ogni m numero intero dispari minore o uguale alla radice di n. Tale tecnica è una specializzazione del "crivello di Eratostene"; solo che tale metodo non è efficiente: esso richiede un numero di step pari a O(n^1/2).
Un test efficiente dovrebbe richiedere un numero di step polinomiale, legato al numero delle cifre di input. ovvero log10(n). Una proprietà questa che è quasi rispettata dal Piccolo Teorema di Fermat.
Difatti se p è un numero primo, allora per ogni a non divisibile per p si ottiene che a^(p-1) = 1 mod p. Per cui si cerca di testare p per vari valori di base a tali che gcd(a,p)=1, per almeno un centianio di basi a
Non sempre il test del Piccolo Teorema di Fermat è efficace, a volte è superato da numeri composti di Carmichael; tuttavia con vari accorgimenti è possibile realizzare un algoritmo che può evitare questo.
D'altra parte esistono molti altri test, Teoremi o dimostrazioni che prendono spunto dal Piccolo Teorema di Fermat o sono riconducili ad esso.
Oggi con l'AKS è noto che il problema della primalità è in P. L'AKS stesso è una generalizzazione del Piccolo Teorema di Fermat come algoritmo polinomiale sugli anelli su campi finiti.
Ad esempio una versione diversa del Piccolo Teorema di Fermat può essere:
(X+a)^n = (X^n+a) mod n.
Vediamo quali possono essere le idee di base, da usare, dove alcune delle quali hanno portato
all'AKS.
Lemma A
Sia a appartenente a Z, n appartenente a N, n minore di 2 e gcd(a,n)=1. Allora n è primo se e solo se
(X + a)^n = X^n + a (mod n) (1)
Nel seguito indichiamo per semplicità col simbolo (n i) il coefficiente binomiale di Newton.
Dimostrazione del Lemma A
Per i maggiore di zero e i minore di n, il coefficiente di x^i in ((X+a)^n - (X^n+a)) è (n i) a^(n-i).
Se n è primo allora (n i) a^(n-i) = 0 mod n e quindi tutti i coefficienti sono nulli.
Difatti se n=3 e a=2 gcd(a,n)=1 se considero i maggiore di zero e i minore di n èlo stesso di dire che (n i) a^(n-i) = 0 mod n.
Supponiamo invece n composto. Sia q un numero primo che è fattore di n e sia q^k non divisore di n.
Allora q^k non divide (n i) ed è coprimo con a^(n-q) e quindi il coefficiente di X^q non è 0 mod n. Di conseguenza (X+a)^n-(X^n+a) non è nullo.
Ad esempio n=6=2*3=q*3
se q=2 se k=2 q^2 non divide (n i).
se gcd(a,n)=1 es a=5 allora gcd(a^n-q,q^k)=1 infatti gcd(5^4,2^2)=1.
Il Lemma A è già un buon test di primalità: dato un valore n trovare dei valori a che rispettano il Lemma allora n è primo. Il problema del Lemma è valutare tutti i coefficienti di Newton, quindi serveono un numero di step uguale a O(n).
Un modo per ridurre i calcoli è di valutare entrambi i membri della (1) e verificare se c'è l'uguaglianza oppure ancora meglio è valutare l'espressione:
(X + a)^n = X^n + a (mod X^r-1,n) (2)
dove r è un numero intero piccolo e scelto opportunamente (con una caratterizzazione).
Il Lemma A comporta che tutti i primi n soddisfano la (2) per tutti i valori di a e r.
In verità alcuni composti potrebbero anch'essi soddisfare la (2) ma con una opportuna scelta di r questo si può evitare e quindi n è effettivamente un numero primo.
In questo caso la scelta di r e la valutazione degli a ci porta ad un tempo O(logn) ottenendo un algoritmo polinomiale deterministico per il test di primalità e quindi la primalità è da dichiarare un problema in P.
Se definiamo l'ordine r di a come or(a), esso rappresenta il più piccolo valore k tale che a^k = 1 mod r.
Se definiamo, poi, la funzione totiente di Eulero ph(r) essa è il numero dei numeri minori di r e primi relativamente a r. Si dimostra che or(a) è un divisore di ph(r) per ogni a e per gcd(a,r)=1.
Allora in tal caso Manindra Agrawal, Neraji Kayal e Nitin Saxena hanno dimostrato l'AKS dicendo che:
Input: integer n > 1.
1. If (n = ab for a 2 N and b > 1), output COMPOSITE.
2. Find the smallest r such that or(n) > log2 n.
3. If 1 < (a, n) < n for some a less or equal than r, output COMPOSITE.
4. If n less or equal than r, output PRIME.
5. For a = 1 to sqrt(ph (r)) log n do
if ((X + a)^n is distinct from X^n + a (mod Xr − 1, n)), output COMPOSITE;
6. Output PRIME;
Famoso è il loro articolo "PRIMES IN P" il cui abstract dice semplicemente: "We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite".
Alla prossima
Una tecnica, quindi, per verificare se n è primo è di dividerlo per ogni m numero intero dispari minore o uguale alla radice di n. Tale tecnica è una specializzazione del "crivello di Eratostene"; solo che tale metodo non è efficiente: esso richiede un numero di step pari a O(n^1/2).
Un test efficiente dovrebbe richiedere un numero di step polinomiale, legato al numero delle cifre di input. ovvero log10(n). Una proprietà questa che è quasi rispettata dal Piccolo Teorema di Fermat.
Difatti se p è un numero primo, allora per ogni a non divisibile per p si ottiene che a^(p-1) = 1 mod p. Per cui si cerca di testare p per vari valori di base a tali che gcd(a,p)=1, per almeno un centianio di basi a
Non sempre il test del Piccolo Teorema di Fermat è efficace, a volte è superato da numeri composti di Carmichael; tuttavia con vari accorgimenti è possibile realizzare un algoritmo che può evitare questo.
D'altra parte esistono molti altri test, Teoremi o dimostrazioni che prendono spunto dal Piccolo Teorema di Fermat o sono riconducili ad esso.
Oggi con l'AKS è noto che il problema della primalità è in P. L'AKS stesso è una generalizzazione del Piccolo Teorema di Fermat come algoritmo polinomiale sugli anelli su campi finiti.
Ad esempio una versione diversa del Piccolo Teorema di Fermat può essere:
(X+a)^n = (X^n+a) mod n.
Vediamo quali possono essere le idee di base, da usare, dove alcune delle quali hanno portato
all'AKS.
Lemma A
Sia a appartenente a Z, n appartenente a N, n minore di 2 e gcd(a,n)=1. Allora n è primo se e solo se
(X + a)^n = X^n + a (mod n) (1)
Nel seguito indichiamo per semplicità col simbolo (n i) il coefficiente binomiale di Newton.
Dimostrazione del Lemma A
Per i maggiore di zero e i minore di n, il coefficiente di x^i in ((X+a)^n - (X^n+a)) è (n i) a^(n-i).
Se n è primo allora (n i) a^(n-i) = 0 mod n e quindi tutti i coefficienti sono nulli.
Difatti se n=3 e a=2 gcd(a,n)=1 se considero i maggiore di zero e i minore di n è
Supponiamo invece n composto. Sia q un numero primo che è fattore di n e sia q^k non divisore di n.
Allora q^k non divide (n i) ed è coprimo con a^(n-q) e quindi il coefficiente di X^q non è 0 mod n. Di conseguenza (X+a)^n-(X^n+a) non è nullo.
Ad esempio n=6=2*3=q*3
se q=2 se k=2 q^2 non divide (n i).
se gcd(a,n)=1 es a=5 allora gcd(a^n-q,q^k)=1 infatti gcd(5^4,2^2)=1.
Il Lemma A è già un buon test di primalità: dato un valore n trovare dei valori a che rispettano il Lemma allora n è primo. Il problema del Lemma è valutare tutti i coefficienti di Newton, quindi serveono un numero di step uguale a O(n).
Un modo per ridurre i calcoli è di valutare entrambi i membri della (1) e verificare se c'è l'uguaglianza oppure ancora meglio è valutare l'espressione:
(X + a)^n = X^n + a (mod X^r-1,n) (2)
dove r è un numero intero piccolo e scelto opportunamente (con una caratterizzazione).
Il Lemma A comporta che tutti i primi n soddisfano la (2) per tutti i valori di a e r.
In verità alcuni composti potrebbero anch'essi soddisfare la (2) ma con una opportuna scelta di r questo si può evitare e quindi n è effettivamente un numero primo.
In questo caso la scelta di r e la valutazione degli a ci porta ad un tempo O(logn) ottenendo un algoritmo polinomiale deterministico per il test di primalità e quindi la primalità è da dichiarare un problema in P.
Se definiamo l'ordine r di a come or(a), esso rappresenta il più piccolo valore k tale che a^k = 1 mod r.
Se definiamo, poi, la funzione totiente di Eulero ph(r) essa è il numero dei numeri minori di r e primi relativamente a r. Si dimostra che or(a) è un divisore di ph(r) per ogni a e per gcd(a,r)=1.
Allora in tal caso Manindra Agrawal, Neraji Kayal e Nitin Saxena hanno dimostrato l'AKS dicendo che:
Input: integer n > 1.
1. If (n = ab for a 2 N and b > 1), output COMPOSITE.
2. Find the smallest r such that or(n) > log2 n.
3. If 1 < (a, n) < n for some a less or equal than r, output COMPOSITE.
4. If n less or equal than r, output PRIME.
5. For a = 1 to sqrt(ph (r)) log n do
if ((X + a)^n is distinct from X^n + a (mod Xr − 1, n)), output COMPOSITE;
6. Output PRIME;
Famoso è il loro articolo "PRIMES IN P" il cui abstract dice semplicemente: "We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite".
Alla prossima
Iscriviti a:
Post (Atom)
Post
