Scheme for computing Montgomery division and Montgomery inverse

Cryptography – Particular algorithmic function encoding

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

713100, 708654, H04L 928, G06F 752, G06F 1500

Patent

active

060884533

ABSTRACT:
A scheme for performing high speed Montgomery division within the Montgomery space. Montgomery division Y=B.multidot.A.sup.-1 .multidot.2.sup.n mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0.ltoreq.A.ltoreq.N, a positive integer B, and an integer n which is satisfying n.gtoreq.L where L is a bit length of N in binary expression, is performed by obtaining a Montgomery inverse X=A.sup.-1 .multidot.2.sup.2n mod N from inputs A and N, and obtaining the Montgomery division Y=B.multidot.X.multidot.2.sup.-n mod N from the Montgomery inverse X and inputs B and N. Montgomery inverse X=A.sup.-1 .multidot.2.sup.2n mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0.ltoreq.A<N, and an integer n which satisfies n.gtoreq.L where L is a bit length of N in binary expression, is determined by obtaining an intermediate result C=A.sup.-1 .multidot.2.sup.k mod N and a parameter k satisfying L.ltoreq.k.ltoreq.2L from inputs A and N, and obtaining the Montgomery inverse X=C.multidot.2.sup.2n-k mod N from the intermediate result C and the parameter k and input N.

REFERENCES:
patent: 5227978 (1993-07-01), Kato
patent: 5321752 (1994-06-01), Iwamura et al.
patent: 5499299 (1996-03-01), Takenaka et al.
patent: 5666419 (1997-09-01), Yamamoto et al.
patent: 5724279 (1998-03-01), Benaloh et al.
patent: 5805703 (1998-09-01), Crandall
Peter L. Montgomery, "Modular Multiplication Without Trial Division", Mathematics of Computation, vol. 44, No. 170, Apr., 1985, pp. 519-521.
Burton S. Kaliski Jr., "The Montgomery Inverse And Its Applications", IEEE Transactions on Computers, vol. 44, No. 8, Aug. 1995, pp. 1064-1065.
Tetsutaro Kobayashi, et al., "Modular Inverse Algorithm Optimized By Initial Operations", Technical Report of IEICE, ISEC97-48, Nov., 1997, pp. 13-23.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Scheme for computing Montgomery division and Montgomery inverse does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scheme for computing Montgomery division and Montgomery inverse , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheme for computing Montgomery division and Montgomery inverse will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-549993

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.