Computing Modular Exponentiation for Fixed-Exponent
Pages 89 - 94
Abstract
Exponentiation is computing ge, where g is an element of a group G and e is a positive integer. In modular exponentiation the underlying group is Zn or Z*n. This paper describe the methods to compute exponentiation where a fixed-exponent e is raised to several bases g of a group G. We describe modular exponentiation based on Bernstein's algorithm for multiplication by constant. We also present a modified approach to modular exponentiation based on k-ary String Replacement (SR(k)) representation.
References
[1]
E. Bach and J. Shallit. Algorithmic number theory: Efficient algorithms. MIT Press, Reading, Massachusetts, 1997.
[2]
D. J. Bernstein. Pippenger's exponentiation algorithm, 2002.
[3]
R. Bernstein. Multiplication by integer constants. Software - Practice and Experience, 16(7):641--652, November 1986.
[4]
E. F. Brickell, D. M. Gordon, K. S. McCurely, and D. B. Wilson. Fast exponentiation with precomputation. In Advances in Cryptology - EUROCRYPT' 92, pages 200--207. Lecture Notes in Computer Science, 658, Springer-Verlag, Berlin, May 1993.
[5]
J. H. Cheon, S. Jarecki, T. Kwan, and M. Lee. Fast exponentiation using split exponents. IEEE Transactions on Information Theory, 57(3):1816--1826, March 2011.
[6]
H. Cohen. A course in computational algebraic number theory. Springer-Verlag, Berlin, 1996.
[7]
D. Gollmann, Y. Han, and C. J. Mitchell. Redundant integer representations and fast exponentiation. Design, Codes and Cryptography, 7(1-2):135--151, April 1996.
[8]
D. M. Gordon. A survey of fast exponentiation methods. Journal of Algorithms, 27(1):129--146, April 1998.
[9]
M. Joye and M. Tunstall. Exponent recoding and regular exponentiation algorithms. In Progress in Cryptology - AFRICACRYPT' 2009, pages 334--349. Lecture Notes in Computer Science, 5580, Springer-Verlag, Berlin, June 2009.
[10]
M. Joye and S. Yen. Optimal left-to-right binary signed-digit recoding. IEEE Transactions on Computers, 49(7):740--748, July 2000.
[11]
D. E. Knuth. The Art of Computer Programming, Seminumerical Algorithms. Addison-Wesley, 1998.
[12]
K. Koyama and Y. Tsurnoka. Speeding up elliptic cryptosystems by using a signed binary window method. In Advances in Cryptology - CRYPTO' 92, pages 345--357. Lecture Notes in Computer Science, 740, Springer-Verlag, Berlin, August 1993.
[13]
A. J. Menezes, P. C. Oorschot, and S. A. Vanstone. Handbook of applied cryptography. CRC Press, 1998.
[14]
F. Morain and J. Olivos. Speeding up the computations on an elliptic curve using addition-subtraction chains. Theoretical Informatics and Applications, 24:531--543, 1990.
[15]
K. Okeya, K. Schmidt-Samoa, C. Spahn, and T. Takagi. Signed binary representations revisited. In Advances in Cryptology - CRYPTO' 2004, pages 123--139. Lecture Notes in Computer Science, 3152, Springer-Verlag, Berlin, August 2004.
[16]
P. Rooij. Efficient exponentiation using precomputation and vector addition chain. In Advances in Cryptology - EUROCRYPT' 94, pages 389--399. Lecture Notes in Computer Science, 950, Springer-Verlag, Berlin, May 1995.
[17]
V. Shoup. A Computational Introduction to Number Theory and Algebra. Cambridge University Press, 2009.
[18]
H. C. van Tilborg and S. Jajodia. Encyclopedia of Cryptography and Security. Springer, 2011.
Index Terms
- Computing Modular Exponentiation for Fixed-Exponent
Recommendations
Hardware Designs for Decimal Floating-Point Addition and Related Operations
Decimal arithmetic is often used in commercial, financial, and Internet-based applications. Due to the growing importance of decimal floating-point (DFP) arithmetic, the IEEE 754 Draft Standard for Floating-Point Arithmetic (IEEE P754) includes ...
Bipartite Modular Multiplication Method
This paper proposes a new fast method for calculating modular multiplication. The calculation is performed @using a new representation of residues modulo M called KT -residue. This representation enables the multiplier to be split into two parts which ...
Accurate Floating-Point Product and Exponentiation
Several different techniques and softwares intend to improve the accuracy of results computed in a fixed finite precision. Here, we focus on a method to improve the accuracy of the product of floating-point numbers. We show that the computed result is ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2015
142 pages
ISBN:9781450336505
DOI:10.1145/2835043
Copyright © 2015 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
In-Cooperation
- ACM India: ACM India
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 29 October 2015
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
Compute '15
Acceptance Rates
Overall Acceptance Rate 114 of 622 submissions, 18%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 88Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)1
Reflects downloads up to 04 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in