Test di Solovay-Strassen
Nel test di primalità di Solovay-Strassen, per determinare se un certo $n$ è composto, si sceglie un $b \in \mathbb{Z}_n \setminus \{0\}$ e si calcolano $b^{\frac{n-1}{2}}$ e $(\frac{b}{n})$. Se tali quantità sono congrue modulo $n$ il test viene passato, e si va a scegliere un altro $b$, altrimenti si può concludere che $n$ è composto.
Domanda: come faccio a calcolare $(\frac{b}{n})$? Per definizione $(\frac{b}{n}) = \prod_{i=1}^k (\frac{b}{p_i})^{\alpha_i}$, supposto che $n = \prod_{i=1}^k p_i^{\alpha_i}$, dove $(\frac{b}{p_i})$ è il simbolo di Legendre. Se conoscessi la scomposizione di $n$ non avrei motivi per fare il test (già dalla fattorizzazione si capisce se $n$ è primo o no), ma se non conosco la fattorizzazione, come calcolo $(\frac{b}{n})$?
Domanda: come faccio a calcolare $(\frac{b}{n})$? Per definizione $(\frac{b}{n}) = \prod_{i=1}^k (\frac{b}{p_i})^{\alpha_i}$, supposto che $n = \prod_{i=1}^k p_i^{\alpha_i}$, dove $(\frac{b}{p_i})$ è il simbolo di Legendre. Se conoscessi la scomposizione di $n$ non avrei motivi per fare il test (già dalla fattorizzazione si capisce se $n$ è primo o no), ma se non conosco la fattorizzazione, come calcolo $(\frac{b}{n})$?
Risposte
Per computare il simbolo di Jacobi puoi sfruttare varie proprietà e teoremi, come la legge di reciprocità quadratica: certo, hai bisogno della coprimalità di b e n, ma dato che b lo puoi scegliere a piacere...
non ho idea su come procedere, ma non mi convince $b^(alpha_i)$... è una svista? ciao.
"luca.barletta":
Per computare il simbolo di Jacobi puoi sfruttare varie proprietà e teoremi, come la legge di reciprocità quadratica: certo, hai bisogno della coprimalità di b e n, ma dato che b lo puoi scegliere a piacere...
Vero... $(\frac{b}{n}) = (-1)^{\frac{(b-1)(n-1)}{4}} (\frac{n}{b})$, e a questo punto mica è vietato conoscere la scomposizione di $b$.. giusto? Intanto grazie per la risposta.
"adaBTTLS":
non ho idea su come procedere, ma non mi convince $b^(alpha_i)$... è una svista? ciao.
Se ti riferisci alla produttoria direi di no, mi pare di aver applicato correttamente la definizione di simbolo di Jacobi...
@ Tipper
sì, mi rifervo alla produttoria definita come b/n, confrontata con la definizione di n... mi sono chiarita con i "simboli di Jacobi"... grazie. ciao.
sì, mi rifervo alla produttoria definita come b/n, confrontata con la definizione di n... mi sono chiarita con i "simboli di Jacobi"... grazie. ciao.
"Tipper":
[quote="luca.barletta"]Per computare il simbolo di Jacobi puoi sfruttare varie proprietà e teoremi, come la legge di reciprocità quadratica: certo, hai bisogno della coprimalità di b e n, ma dato che b lo puoi scegliere a piacere...
Vero... $(\frac{b}{n}) = (-1)^{\frac{(b-1)(n-1)}{4}} (\frac{n}{b})$, e a questo punto mica è vietato conoscere la scomposizione di $b$.. giusto? Intanto grazie per la risposta.
[/quote]
giusto
Ok, grazie ancora.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo