MODULAR EXPONENTIATION

Authors

  • Sorin Iftene

DOI:

https://doi.org/10.47839/ijc.2.3.229

Keywords:

Modular exponentiation, basic techniques, fixed-exponent techniques, fixed-base techniques, techniques based on modulus particularities, binary fan-in technique

Abstract

Exponentiation is a fundamental operation in computational number theory. Primality testing and cryptography are important working fields in which the exponentiation is heavily used. In this paper we survey the most popular methods for modular exponentiation: basic techniques, fixed-exponent techniques, fixed-base techniques, and techniques based on modulus particularities. Some aspects related to parallelism are also discussed.

References

S. Iftene. Modular exponentiation. Pre- Proceedings of the NATO Advanced Research Workshop “Concurent Information Proccesing and Computing”, July 5-10, 2003, Sinaia, Romania, pp. 125-144

F.L. Tiplea, S. Iftene, C. Hritcu, I. Goriac, R.M. Gordan and E. Erbiceanu. MpNT: A Multi-Precision Number Theory Package. Number-Theoretic Algorithms (I). Technical Report TR03-02 (2003), Faculty of Computer Science “Al.I.Cuza” University of Iasi. http://www.infoiasi.ro/~tr/tr.pl.cgi

E.G. Thurber. On addition chains l(mn) ? l(n)-b and lower bounds for c(r), Duke Mathematical Journal 40 (1973), pp. 907-913

B. Moller. Improved Techniques for Fast Exponentiation. Proceedings of the Workshop “Information Security and Cryptology ICISC 2002”, pp. 298-312

A. Brauer. On Addition Chains, Bulletin of the American Mathematical Society 45 (1939), pp. 736-739

A. C. Yao. On the evaluation of powers, SIAM Journal on Computing 5 (1976), pp. 100-103

D.E. Knuth. The Art of Computer Programming. Seminumerical Algorithms. Addison-Wesley, third edition, 1997

D.E. Knuth. The Art of Computer Programming. Seminumerical Algorithms. Addison-Wesley, second edition, 1981

D.R. Stinson. Some observations on parallel algorithms for fast exponentiation in GF(2n). SIAM Journal on Computing 19 (4) (1990), pp. 711-717

M. Nocker. Some remarks on parallel exponentiation. Extended abstract. Proceedings of the Workshop “International Symposium on Symbolic and Algebraic Computation ISSAC 2000”, pp. 250-257

E. F. Brickell, D. M. Gordon, K. S. McCurley and D. B. Wilson. Fast Exponentiation with Precomputation: Algorithms and Lower Bounds,preprint,1995. http://research.microsoft.com/~dbwilson/bgmw/

P. De Rooij. Efficient exponentiation using precomputation and vector addition chains. Proceedings of the Workshop “EUROCRYPT 1994”, pp. 389-399

C. H. Lim and P.J. Lee. More flexible exponentiation with precomputation. Proceedings of the Workshop“CRYPTO 1994”, pp. 95-107

D. J. Bernstein. Pippenger's exponentiation algorithm, preprint, 1991. http://cr.yp.to/papers.html

R. L. Rivest, A. Shamir and L. M. Adelman. A Method for Obtaining Digital Signatures and Public-key Cryptosystems. Communications of the ACM 2 (21) (1978), pp. 120-126.

T. Collins, D. Hopkins, S. Langford and M. Sabin. Public Key Cryptographic Apparatus and Method. United States Patent 5, 848, 159 (1997)

H. Garner. The residue number system. IRE Transactions on Electronic Computers EC-8 (1959), pp. 140-147.

J.-J. Quisquater and C. Couvreur. Fast decipherment algorithm for the RSA public-key cryptosystem. IEE Electronics Letters 8 (21) (1982), pp. 905-907.

Downloads

Published

2014-08-01

How to Cite

Iftene, S. (2014). MODULAR EXPONENTIATION. International Journal of Computing, 2(3), 49-55. https://doi.org/10.47839/ijc.2.3.229

Issue

2003, Volume 2, Issue 3

Section

Articles

License

International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
•    Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
•    Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
•    Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.