Teoria dei numeri
Salve,
mi sono iscritto al forum da appena 5 giorni, sono un pensionato che ha la passione per i numeri primi e diverse lacune in campo matematico, ho però lavorato come analista-programmatore per 40 anni, mi considero più uno sperimentale (a mio agio con i numeri) che un teorico (sempre un po' in difficoltà con le formule e le dimostrazioni).
Il problema che volevo sottoporre alla vostra attenzione riguarda i residui quadratici; ho cercato nella rete internet qualcosa che potesse dirmi se il problema era in qualche modo conosciuto ho consultato le note sui residui quadratici del matematico Mauro Fiorentini, nel vostro sito ho letto le note sulla teoria dei residui quadratici del dott. Roberto Volpe. Il teorema? (congettura perché non sono arrivato a formulare alcuna dimostrazione) è il seguente: se esistono due qualsiasi residui quadratici di un numero intero dispari P a partire dalla radice quadrata di P+1 sino a (P-1)/2 che danno il medesimo risultato allora P è un numero composto oppure, se esiste un qualsiasi residuo quadratico che a sua volta corrisponde a un quadrato allora P è un numero composto; esempio: lo pseudoprimo di Carmichael 561 ha radice quadrata = 23 quindi prendendo 24x24=576 MOD(561)=15 e 75x75=5625 MOD(561)=15 i residui corrispondono quindi 561 è un numero composto, oppure prendendo 25x25=625 MOD(561) = 64 che è il quadrato di 8 allora P è un numero composto; più che un test di primalità sarebbe un test di non primalità.
L,'algoritmo che ho creato, scritto in fortran 95, è nel 50% dei casi più veloce di circa 7 volte rispetto al piccolo teorema di Fermat sino a numeri della grandezza di 20 cifre, per numeri superiori del tipo di milioni di cifre ci vorrebbe il linguaggio C e la biblioteca GMP.
Nella speranza di conoscere dei riscontri in merito saluto tutti - Stefano Morozzi
mi sono iscritto al forum da appena 5 giorni, sono un pensionato che ha la passione per i numeri primi e diverse lacune in campo matematico, ho però lavorato come analista-programmatore per 40 anni, mi considero più uno sperimentale (a mio agio con i numeri) che un teorico (sempre un po' in difficoltà con le formule e le dimostrazioni).
Il problema che volevo sottoporre alla vostra attenzione riguarda i residui quadratici; ho cercato nella rete internet qualcosa che potesse dirmi se il problema era in qualche modo conosciuto ho consultato le note sui residui quadratici del matematico Mauro Fiorentini, nel vostro sito ho letto le note sulla teoria dei residui quadratici del dott. Roberto Volpe. Il teorema? (congettura perché non sono arrivato a formulare alcuna dimostrazione) è il seguente: se esistono due qualsiasi residui quadratici di un numero intero dispari P a partire dalla radice quadrata di P+1 sino a (P-1)/2 che danno il medesimo risultato allora P è un numero composto oppure, se esiste un qualsiasi residuo quadratico che a sua volta corrisponde a un quadrato allora P è un numero composto; esempio: lo pseudoprimo di Carmichael 561 ha radice quadrata = 23 quindi prendendo 24x24=576 MOD(561)=15 e 75x75=5625 MOD(561)=15 i residui corrispondono quindi 561 è un numero composto, oppure prendendo 25x25=625 MOD(561) = 64 che è il quadrato di 8 allora P è un numero composto; più che un test di primalità sarebbe un test di non primalità.
L,'algoritmo che ho creato, scritto in fortran 95, è nel 50% dei casi più veloce di circa 7 volte rispetto al piccolo teorema di Fermat sino a numeri della grandezza di 20 cifre, per numeri superiori del tipo di milioni di cifre ci vorrebbe il linguaggio C e la biblioteca GMP.
Nella speranza di conoscere dei riscontri in merito saluto tutti - Stefano Morozzi
Risposte
Certamente è vero, se $p$ è primo allora ogni $n$ che è un quadrato modulo $p$ ha esattamente due radici quadrate e sono $\pm m$ per qualche $m$; se wlog \(m\in [0,\ldots,(p-1)/2]\) allora \(-m\in [(p+1)/2,\ldots,p-1]\). Ergo, se trovi due radici quadrate in $[0,\ldots,(p-1)/2]$ certamente $p$ dev'essere composto (e a maggior ragione se le trovi in \([\sqrt{p+1},\ldots,(p-1)/2]\)). Penso che si possa rendere questo un algoritmo probabilistico in maniera formale, il problema è che sospetto sia al meglio subesponenziale, e quindi radicalmente peggio del miglior algoritmo di primalità esistente che è polinomiale.
La seconda cosa che hai detto invece è più interessante ed è la base dei migliori metodi di fattorizzazione noti al giorno d'oggi: l'osservazione è che se esiste un $n\in [\sqrt{p},\ldots,p-1]$ tale che $n^2\in [0,\ldots,p-1]$ è un il quadrato di un intero $m$, allora $n^2\equiv m^2\mod p$, il che equivale a dire che $(n-m)(n+m)\equiv 0\mod p$. Segue che $\gcd(p,n-m)$ contiene un fattore non banale di $p$. Se ti interessa approfondire cerca "quadratic sieve" e per la sua versione più raffinata "number field sieve".
La seconda cosa che hai detto invece è più interessante ed è la base dei migliori metodi di fattorizzazione noti al giorno d'oggi: l'osservazione è che se esiste un $n\in [\sqrt{p},\ldots,p-1]$ tale che $n^2\in [0,\ldots,p-1]$ è un il quadrato di un intero $m$, allora $n^2\equiv m^2\mod p$, il che equivale a dire che $(n-m)(n+m)\equiv 0\mod p$. Segue che $\gcd(p,n-m)$ contiene un fattore non banale di $p$. Se ti interessa approfondire cerca "quadratic sieve" e per la sua versione più raffinata "number field sieve".
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo