next up previous
Next: 1.6 GMP and other Up: 1 Multiple Precision Arithmetic Previous: 1.4 Using the shift

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 p2 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 3p2 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 p2 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!

Kapil Hari Paranjape 2002-10-20