olemus
kombinatoorikaprobleem:
(i) on teada kordarvuline moodul \(n=pq\),
kus \(p\) ja \(q\) on algarvud
(ii) ei ole teada
- astendaja \(d\), mis on arvu \(p-1\) jagaja
- arv \(y\in\mathbb{Z}_n\)
(iii) tuleb otsustada, kas leidub selline
\(x\in\mathbb{Z}_n\), mille korral \(x^d \equiv y\pmod{n}\)
=
a certain combinatorics problem
that is harder to solve than factorization

erijuht
ruutjääkide probleem : kui \(d=2\)

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

https://www.ijert.org/a-survey-report-on-partially-homomorphic-encryption-techniques-in-cloud-computing

https://www.di.ens.fr/~stern/data/St65.ps

https://en.wikipedia.org/wiki/Computational_hardness_assumption