This redirect may meet Wikipedia's criteria for speedy deletion as an article that contains no content whatsoever, or consists only of external links, categories, a "see also" section, a rephrasing of the title, chat-like comments, template tags, and/or images. Disambiguation pages and redirects are not eligible for this criterion. A very short article may still be a valid stub if there is sufficient context to identify the subject. See CSD A3.
If this redirect does not meet the criteria for speedy deletion, or you intend to fix it, please remove this notice, but do not remove this notice from pages that you have created yourself. If you created this page and you disagree with the given reason for deletion, you can click the button below and leave a message explaining why you believe it should not be deleted. You can also visit the talk page to check if you have received a response to your message. Note that this redirect may be deleted at any time if it unquestionably meets the speedy deletion criteria, or if an explanation posted to the talk page is found to be insufficient.
Note to administrators: this redirect has content on its talk page which should be checked before deletion. Administrators: check links, talk, history (last), and logs before deletion. Consider checking Google.This page was last edited by Garfield Garfield (contribs | logs) at 19:31, 30 September 2014 (UTC) (10 years ago) |
We define a ≡ b (mod c) if (a - b)/c is an integer. Define the function f(x, y, z) ≡ xy (mod z), such that f ∈ {0, 1, ... , z - 1}. Then w = f(x, y, z) can be computed efficiently, even when x, y, z > 10300 by the following recursive algorithm (we assume that the integers x > 0, y > -1, and z > 0):
- if y = 0, return 1.
- if y is even, put u = f(x, y/2, z) and return (u*u) mod z
- return {x*f(x, y - 1, z}} mod z
- Analysis
- The numbers computed are always less than z2, and the final answer is less than z.
- The method of computing w as xy and then reducing w modulo z is not feasible for large numbers. For example, computing f(10, 10300, 17) in this way, would involve computing a number w consisting of a 1 followed by 10300 zeros. If one atom were used to write each zero, then the observable universe would not contain enough atoms to write out w, since the observable universe contains at most 1082 atoms. The final answer, in any case is less than 17, and the above algorithm for the discrete exponential would compute it in fewer than 2400 steps, since 10300 < 16300 < 21200, and every two steps cut the exponent in half.
Applications
The discrete exponential function is essential to a number of important cryptographic protocols, including: