![[JoGu]](../../JGU.gif) |
CryptologyIII.5 Hard Number Theoretic Problems |
|
|
CryptologyIII.5 Hard Number Theoretic Problems |
|
The complete chapter as PDF file
The following table gives an overview over cryptologically relevant number theoretic computational problems.
»Efficient« means »computable with polynomial cost«, »ERH« means »if the extended Riemann hypothesis holds«, »prob.« means »by a probabilistic algorithm«.
| Computational problem | efficient? | treated in |
|---|---|---|
| Primality test | yes | 3.1 – 3.8 |
| [For a prime number p] | ||
| Finding a primitive element Finding a quadratic nonresidue Quadratic residuosity Taking a square root Discrete logarithm |
yes (ERH or prob.) yes (ERH or prob.) yes yes (ERH or prob.) ? (probably no) |
A.2, A.9 A.8 A.6 follows in Section 3 4.1, 4.6 |
| [For a composite integer n] | ||
| Factoring RSA inversion (e-th root) Computation of EULER function Computation of CARMICHAEL function Finding a primitive element Quadratic residuosity Taking a square root Discrete logarithm |
? (probably no) ? (probably no) ? (probably no) ? (probably no) ? (probably no) ? (probably no) ? (probably no) ? (probably no) |
2.2, 2.4 2.2 2.2 2.2 A.4 A.11 follows in Section 5 follows in Section 1 |
The following figure shows the connection between computational problems for a composite integer n. An arrow from A to B indicates that problem B reduces to Problem A by an efficient (maybe probabilistic) algorithm. For an unidirectional arrow the reverse direction is unknown. Reductions indicated by red arrows will be proved in this chapter (sometimes only in the case where n is a product of two primes.)
The task denoted by »Pol. fact.« means factoring polynomials in one variable over the residue class ring Z/nZ. We'll not treat it in these lecture notes.
![[Reductions]](Reduct.png)