Modular multiplication method and calculating device

Details Modular multiplication method and calculating device Modular multiplication method and calculating device

2007-04-17

2007-04-17

Ngo, Chuong D. (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C380S028000

Reexamination Certificate

active

10282107

ABSTRACT:
To provide a modular multiplication method and a calculating device that do not rely on the Montgomery technique, wherein the number of times of multiply-add calculations is reduced to shorten a calculation time for calculation speed-up, there is no limitation in input value, and it is possible to execute a remainder calculation exceeding the calculable maximum bit length of a multiply-add unit that is used. Assuming that N=2n−M and X=α×2n+β, a relation of XmodN=(α×M+β)modN is derived, which is utilized. n represents a maximum bit number where “1” is assigned in N, a solution of 2n+1modN is set as b, A×B is set as X, XmodN is transferred to (X/2n+1×b+Xmod2n+1)modN and further transferred to (X·n/2n+1×b+X·nmod2n+1)modN, calculations of X·n/2n+1×b+X·nmod2n+1are repeated until a bit length of X·n becomes n+1, X·n−N is derived and a derived result is set as a solution of “A×BmodN”.

REFERENCES:
patent: 5513133 (1996-04-01), Cressel et al.
patent: 6415310 (2002-07-01), Takenaka et al.
patent: 6697831 (2004-02-01), Cookman et al.
patent: 11-212456 (1999-08-01), None
patent: 2000-132376 (2000-05-01), None
patent: 2001-51832 (2001-02-01), None
“Hardware Implementation of Montgomery's Modular Multiplication Algorithm” by Stephen E. Eldridge and Colin D. Walter, IEEE in 1993.

Affiliated with

Also associated with

Rating

Modular multiplication method and calculating device does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Modular multiplication method and calculating device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modular multiplication method and calculating device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3728730