Teorema cinese del resto e residui quadratici
Si dimostra che conoscere le radici di un residuo quadratico modulo n=pq equivale a conoscere p e q, dove questi sono 2 primi.
Il passaggio che mi sfugge è il seguente:
Sia $a in ZZ_n$ un residuo quadratico modulo n.
dato che $ ZZ_n ~~ (ZZ_p xx ZZ_q ) $ allora per il teorema del resto per trovare le radici di a è sufficiente trovarle modulo un primo.
Il TdR l' ho presente, ho anche provato a considerare il sistema di congruenze modulo p e n, ma comunque non riesco a risalire al ragionamento esatto che porta a questa semplificazione... capisco che probabilmente sarà un ovvietà, ma su queste cose un pò mi perdo...
Il passaggio che mi sfugge è il seguente:
Sia $a in ZZ_n$ un residuo quadratico modulo n.
dato che $ ZZ_n ~~ (ZZ_p xx ZZ_q ) $ allora per il teorema del resto per trovare le radici di a è sufficiente trovarle modulo un primo.
Il TdR l' ho presente, ho anche provato a considerare il sistema di congruenze modulo p e n, ma comunque non riesco a risalire al ragionamento esatto che porta a questa semplificazione... capisco che probabilmente sarà un ovvietà, ma su queste cose un pò mi perdo...
Risposte
Non mi sembra così ovvio. Curiosità: che testo è?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo