next up previous
Next: About this document Up: Contents Previous: Predicting how many computer

Fast algorithms and slow algorithms, easy problems and hard problems

If we plug some 100-digit numbers m and k into the formulae from the preceding section, we see that there is a tremendous difference between the number of steps required by the naive algorithm and the number of steps required by the repeated-squaring algorithm. The first is considered a slow algorithm--it would take millenia to complete for 100-digit inputs. The repeated-squaring algorithm is considered a fast algorithm. Even for 100-digit inputs, a reasonable, current-day computer would complete the algorithm in seconds.

Since we have a fast algorithm for the modular exponentiation problem, we say that this problem is ``easy'' to solve. Some computational problems are inherently difficult in that there is no fast algorithm to solve it. For many computational problems, we don't know whether they are easy or not: nobody has announced a fast algorithm but nobody has proved that no fast algorithm exists.

Aside from perfect secrecy, cryptography is based on the dichotomy between easy problems and hard problems. For example, we want encryption and decryption to be easy for someone who knows the key, but we want cracking (decryption without the key) to be hard.


Lisa Eckstein
Tue Oct 22 00:20:45 EDT 1996