 |
Business | Industries | Finance | Tax |
| Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
|
|||||
| First Prev [ 1 2 ] Next Last |
Generally, modular exponentiation problems take the form where given base b, exponent e, and modulus m, one wishes to calculate c such that:
If b, e, and m are non-negative and b < m, then a unique solution c exists and has the property 0 ≤ c < m. For example, given b = 5, e = 3, and m = 13, the solution c works out to be 8.
Modular exponentiation problems similar to the one described above are considered easy to do, even if the numbers involved are enormous. On the contrary, computing the discrete logarithm (finding b given c, e, and m) is believed to be difficult. This one way function behavior makes modular exponentiation a good candidate for use in cryptographic algorithms.
The most straightforward method to calculating a modular exponent is to calculate be directly, then to take this number modulo m. Consider trying to compute c, given b = 4, e = 13, and m = 497:
One could use a calculator to compute 413; this comes out to 67,108,864. Taking this value modulo 497, the answer c is determined to be 445.
Note that b is only one digit in length and that e is only two digits in length, but the value be is 10 digits in length.
In strong cryptography, b is often at least 256 binary digits (77 decimal digits). Consider b = 5 * 1076 and e = 17, both of which are perfectly reasonable values. In this example, b is 77 digits in length and e is 2 digits in length, but the value be is 1304 decimal digits in length. Such calculations are possible on modern computers, but the sheer enormity of such numbers causes the speed of calculations to slow considerably. As b and e increase even further to provide better security, the value be becomes unwieldy.
The time required to perform the exponentiation depends on the operating environment and the processor. If exponentiation is performed as a series of multiplications, then this requires O(e) time to complete.
A second method to compute modular exponentiation requires more operations than the first method. Because the required memory footprint is substantially less, however, operations take less time than before. The end result is that the algorithm is faster.
This algorithm makes use of the fact that, given two integers a and b, the following two equations are equivalent:
The algorithm follows:
Note that in every pass through step 3, the equation holds true. When step 3 has been executed e times, then, c contains the answer that was sought.
The example b = 4, e = 13, and m = 497 is presented again. The algorithm passes through step 3 thirteen times:
The final answer for c is therefore 445, as in the first method.
Like the first method, this requires O(e) time to complete. However, since the numbers used in these calculations are much smaller than the numbers used in the first algorithm's calculations, the constant factor in this method tends to be smaller.
| Politics | Business | Finance |
 |
 |
 |
|