[This page is auto-generated; please prefer to read the article’s PDF Form.]
All the algorithms and their C methods presented below will apply both to exponentiation and modular-exponentiation, with slight changes. The methods are shown for modular-exponentiation and so contain many uses of modulo n operation done via “% n”, to reduce the multiplication results modulo n. Removing these “% n” occurrences will give us the methods for normal exponentiation.
This close similarity between the algorithms for these two exponentiations can be proven using the following relation from Modular Arithmetic. Here, x, y and n are any positive integers:
|
|
Copyright © 2021 Nitin Verma. All rights reserved.