Cryptology and computational number theory. - An introduction.

*(English)*Zbl 0734.11072
Cryptology and computational number theory, Lect. Notes AMS Short Course, Boulder/CO (USA) 1989, Proc. Symp. Appl. Math. 42, 1-12 (1990).

[For the entire collection see Zbl 0722.00005.]

The development of number theoretic based cryptosystems over the past fifteen years is reviewed. Some easy number theoretic problems, such as the computation of \(2^ a (mod b)\), are introduced. It is noted that the arithmetic problems of primality testing and factoring are quite different with the problem of choosing large primes being easy. Conversely, factoring remains a hard problem although there exists no proof that this is necessarily so. The RSA cryptosystem is reviewed with the point observed that if one is able to factor, the system is insecure. Discrete logarithm and knapsack cryptosystems are also briefly described.

The development of number theoretic based cryptosystems over the past fifteen years is reviewed. Some easy number theoretic problems, such as the computation of \(2^ a (mod b)\), are introduced. It is noted that the arithmetic problems of primality testing and factoring are quite different with the problem of choosing large primes being easy. Conversely, factoring remains a hard problem although there exists no proof that this is necessarily so. The RSA cryptosystem is reviewed with the point observed that if one is able to factor, the system is insecure. Discrete logarithm and knapsack cryptosystems are also briefly described.

Reviewer: I.F.Blake (Waterloo / Ontario)

##### MSC:

11Y16 | Number-theoretic algorithms; complexity |

11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |

94A60 | Cryptography |

11Y11 | Primality |