Cryptology The Multiplicative Group Primitive Elements and Quadratic Residues

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. Primitive elements for powers of 2 [PDF]
2. Primitive elements for prime modules [PDF]
3. Primitive elements for prime powers [PDF]
4. The structure of the multiplicative group [PDF]
5. The JACOBI symbol [PDF]
6. Quadratic reciprocity [PDF]
7. Proof of the law of quadratic reciprocity [PDF]
8. Quadratic non-residues [PDF]
9. Primitive elements for special primes [PDF]
10. Some group theoretic trivia [PDF]
11. BLUM integers [PDF]
12. The multiplicative group modulo special BLUM integers [PDF]
13. The BBS sequence [PDF]
14. The BBS sequence for superspecial BLUM integers [PDF]

The complete appendix A as PDF file

Overview

This mathematical appendix treats in a closed form some number theoretic subjects that play a major role for cryptology. They relate to the multiplicative group of a residue class ring.

As we saw in the main text several results on the security of cryptographic procedures depend on the non-existence of efficient algorithms for some tasks.

Relevant problems and their (incomplete) solutions are:

1. Find a primitive element.
   • The complexity of the general case is unknown.
   • Exhaustion is efficient if ERH [*] holds.
   • There is a much more efficient probabilistic algorithm, that however doesn't even terminate in the worst case.
   • For many prime modules the solution is trivial.
   • Proving primitivity is efficient if the prime factors of the order of the multiplicative group are known. Otherwise the complexity is unknown.
   • For a composite module the problem reduces to its prime factors—if these are known.
2. Decide on quadratic residuosity.
   • For prime modules there is an efficient algorithm.
   • For a composite module the problem reduces to its prime factors—if these are known.
   • For composite modules with unknown prime factors the complexity is unknown. Presumably the problem is hard (as hard as prime decomposition).
3. Find a quadratic non-residue.
   • The complexity of the general case is unknown.
   • Exhaustion is efficient if ERH holds.
   • There is an efficient probabilistic algorithm, that however doesn't even terminate in the worst case.
   • For most primes the solution is trivial.
   • For a composite module the problem reduces to its prime factors—if these are known.

[*] charaterized by Martin HUXLEY in a limerick:

Tell the Riemann Hypothesis crew
That zeta alone will not do.
Precise applications
to nice situations
Require it for L-functions too.