Method for generating the multiplicative inverse in a finite...

Details Method for generating the multiplicative inverse in a finite... Method for generating the multiplicative inverse in a finite...

2003-12-15

2009-08-11

Malzahn, David H (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

07574469

ABSTRACT:
The essence of the invention is an effective method for generating the multiplicative inverse in a finite field GF(p) where p is prime, i.e. for generating the modular inverse. This method is derived from the Extended Euclidean Algorithm (EEA). The method is for binary execution of operations during the process of generating the modular inverse, with respect to the lowest number of addition, subtraction and shift operations possible. The proposed method avoids redundant operations for converting odd and negative values, which are performed in methods currently in use. To achieve that, negative numbers are represented in the two's complement code, values in the control part of the EEA are shifted to the left, and a new definition of the boundary and control conditions is utilized in the procedure. Minimizing the number of additions and subtractions is desirable for calculations with large numbers often encountered in cryptography.

REFERENCES:
patent: 7461115 (2008-12-01), Eberle et al.
patent: 2001/0054052 (2001-12-01), Arazi
patent: 2003/0208518 (2003-11-01), Gura et al.
Lorencz, Robert, “New Algorithm for Classical Modular Inverse” Cryptographic Hardware and Embedded Systems. International Workshop, Aug. 13, 2002, pp. 57-70.
Kaliski, B. S. “The Montgomeral Inverse and Its Applications” IEEE Transactions on Computers, IEEE Inc., New York, US; vol. 44, No. 8, Aug. 1, 1995, pp. 1064-1065.
Lenstra, A. K. “Computational Methods in Public Key Cryptology” Citibank N.A. and Technische Universiteit Eindhoven, Aug. 12, 2001.

Affiliated with

Also associated with

Rating

Method for generating the multiplicative inverse in a finite... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for generating the multiplicative inverse in a finite..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating the multiplicative inverse in a finite... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4090477