Matematicamente.it

Per conoscere l’unicità devi conoscere la fattorizzazione di $p$, o quantomeno tutti i suoi divisori congrui a $1$ modulo $4$.

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

ho scritto tutto quello che so su questo argomento qui:
https://www.academia.edu/115482663/Pyth ... torizazion

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.

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.

Non solo ti dice se ci sono più soluzioni ma ti dice anche quali sono

$x^2 \equiv -1 (mod 365)$ $-> x=27$

$x \equiv 365 (mod 27) $ $ -> x=14$

$[14,sqrt(365-14^2)]=(14,13)$

$x^2 \equiv -1 (mod 365)$ $-> x=173$

$x \equiv 365 (mod 173)$ $-> x=19 $

$[19,sqrt(365-19^2)]=(19,2)$

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$.

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$.

Grazie
Ho imparato un'altra cosa