26/02/2024, 21:21
27/02/2024, 07:19
hydro ha scritto:Per conoscere l’unicità devi conoscere la fattorizzazione di $p$, o quantomeno tutti i suoi divisori congrui a $1$ modulo $4$.
27/02/2024, 09:05
27/02/2024, 16:12
P_1_6 ha scritto:hydro ha scritto:Per conoscere l’unicità devi conoscere la fattorizzazione di $p$, o quantomeno tutti i suoi divisori congrui a $1$ modulo $4$.
Grazie
C'è un altro modo ma usa i residui quadratici:
L'algoritmo di Cornacchia
27/02/2024, 16:26
hydro ha scritto:P_1_6 ha scritto:hydro ha scritto:Per conoscere l’unicità devi conoscere la fattorizzazione di $p$, o quantomeno tutti i suoi divisori congrui a $1$ modulo $4$.
Grazie
C'è un altro modo ma usa i residui quadratici:
L'algoritmo di Cornacchia
Quello ti dice solo se esiste una soluzione, non se la soluzione è unica.
27/02/2024, 22:51
28/02/2024, 08:09
hydro ha scritto:No, non funziona così. L'algoritmo di Cornacchia prende in input una radice di $-1$ modulo $p$ e ti restituisce, se esiste, una soluzione di $x^2+y^2=p$. Nessuno ti garantisce che ogni radice di $-1$ dia luogo ad una soluzione diversa, nessuno ti garantisce che ogni soluzione si possa trovare tramite l'algoritmo e oltretutto se $p$ è composito conoscere le radici di $-1$ modulo $p$ è essenzialmente equivalente a conoscere la fattorizzazione di $p$. Questo è spiegato anche sulla pagina di Wikipedia, ma l'idea è semplice: se $x^2=y^2=-1\mod p$ allora $(x-y)(x+y)=0 \mod p$ e quindi $\gcd(p,x-y)\ne 1$, a patto ovviamente che $x\ne \pm y$.
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.