AKIT
English Eesti

quadratic residue problem

ruutjääkide probleem

olemus
kõrgemate jääkide probleemi erijuht,
kombinatoorikaprobleem:
- on teada kordarvuline moodul \(n=pq\),
kus algarvud \(p\) ja \(q\) ei ole teada,
ja on teada arv \(y\in\mathbf{Z}_n\)
- tuleb otsustada, kas \(y\) on ruutjääk,
st kas leidub \(x\in\mathbb{Z}_n\) nii et \(x^2 \equiv y\pmod{n}\)

ülevaateid
https://en.wikipedia.org/wiki/Quadratic_residuosity_problem

https://www.iacr.org/archive/pkc2016/96140177/96140177.pdf

https://lucatrevisan.wordpress.com/2009/05/04/cs276-lecture-25/