Discrete exponential function: Difference between revisions

Revision as of 18:53, 30 September 2014

Revision as of 18:54, 30 September 2014

Line 5:

*'''Analysis'''

*The numbers computed are always less than z², and the final answer is less than z.

*The method of computing w as x^y and then reducing w modulo z is not feasible for large numbers. For example, computing f(10, 10³⁰⁰, 17) in this way, would involve computing a number w consisting of a 1 followed by 10³⁰⁰ zeros. If one atom were used to write each zero, then the observable universe would not contain enough atoms to write out w, since itthe observable universe contains fewer than 10⁸² atoms. The final answer, in any case, will be less than 17, and the above algorithm for the discrete exponential would compute it in fewer than 2400 steps, since 10³⁰⁰ < 16³⁰⁰ < 2¹²⁰⁰, and every two steps the exponent is cut in half.