Computing A*B (mod N) efficiently in ANSI C

ABSTRACT

The modular product computation A*B (mod N) is a bottleneck for some public-key encryption algorithms, as well as many exact computations implemented using the Chinese Remainder Theorem. We show how to compute A*B (mod N) efficiently, for single-precision A, B, and N, on a modern RISC architecture (Intel 80860) in ANSI C. On this architecture, our method computes A*B (mod N) faster than ANSI C computes A%N, for unsigned longs A and N.

REFERENCES

• 1: ANSI C. Draft Proposed American National Standard Programming Language C. ANSI, NY, 1988.
• 2: Blakeley, G.R. "A Computer Algorithm for Calculating the Product AB modulo M". IEEE Trans. Comps. C-32, 5 (May 1983), 497-500.
• 3: DoD. Reference Manual for the Ada® Programming Language. ANSI/MIL-STD-1815A-1983, USGPO, 1983.
• 4: J. K. Gibson, A generalisation of Brickell's algorithm for fast modular multiplication, BIT, v.28 n.4, p.755-763, 1988 [doi>10.1007/BF01954895]
• 5: R T. Gregory , E V. Krishnamurthy, Methods and applications of error-free computation, Springer-Verlag New York, Inc., New York, NY, 1984
• 6: Intel Corp. i860^¿ 64-bit Microprocessor Programmer's Reference Manual. #240329-002, 1989.
• 7: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: K. Kukihara, Euclidean type algorithm for multiplication modulo P II, Journal of Information Processing, v.12 n.2, p.147-153, Jan. 1989
• 9: Joel Moses, Algebraic simplification: a guide for the perplexed, Communications of the ACM, v.14 n.8, p.527-537, Aug. 1971 [doi>10.1145/362637.362648]
• 10: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 11: M R. Schroeder, Number theory in science and communication, Springer-Verlag New York, Inc., New York, NY, 1984
• 12: Wang, P. "MACSYMA--A Symbolic Manipulation System". Proc. Int'l. Comp. Symp. (1975), Vol. I, 103-109.
• 13: Taiichi Yuasa, Design and implementation of Kyoto Common Lisp, Journal of Information Processing, v.13 n.3, p.284-295, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Design, Languages, Theory