1.5 Faster Algorithms

There are algorithms for multiplication and division that are asymptotically much faster than the above procedures; when multiplying numbers of size p we have taken p² steps above, which can asymptotically be reduced to a constant multiple of p log(p). However, the constant is large and it is likely that we will not need to look at those methods for the integers of the size we will be dealing with.

Similarly, we have taken 3p² steps for division whereas division can be reduced to multiplication upto a constant factor and hence is again accomplished in a constant multiple of p log(p) steps.

It will probably suffice for cryptological applications to make the asymmetric assumption that the cryptographer (encryption/decryption process) uses multiplication that takes p² steps while the cryptanalyst (the ``code-breaker'') uses multiplication that takes p log(p) steps. If the cryptosystems that we design are secure under such asymmetric assumptions they will also be secure under more symmetric assumptions!