Public-key Cryptography: Theory and Practice

3.4. Elementary Number-theoretic Computations

Now that we know how to work in and in the residue class rings , , we address some important computational problems associated with these rings. In this chapter, we restrict ourselves only to those problems that are needed for setting up various cryptographic protocols.

3.4.1. Primality Testing

One of the simplest and oldest questions in algorithmic number theory is to decide if a given integer , n