Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2011-04-19
2011-04-19
Mai, Tan V (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
07930337
ABSTRACT:
Techniques are described to multiply two numbers, A and B. In general, multiplication is performed by using Karatsuba multiplication on the segments of A and B and adjusting the Karatsuba multiplication based on the values of the most significant bits of A and B.
REFERENCES:
patent: 5166978 (1992-11-01), Quisquater
patent: 6404890 (2002-06-01), Lenstra
patent: 7363336 (2008-04-01), Montgomery
patent: 2002/0005323 (2002-01-01), Axe et al.
patent: 2003/0206628 (2003-11-01), Gura et al.
patent: 2003/0206629 (2003-11-01), Eberle et al.
patent: 2007/0083585 (2007-04-01), St Denis et al.
patent: 2008002822 (2008-01-01), None
Dyke, et al., “Area Efficient Hardware Implementation of Elliptic Curve Cryptography by Iteratively Applying Karatsuba's Method, Design, Automation and Test in Europe 2005”, Proceedings (2005); vol. 3, (2005),70-75.
Nedjah, et al., “A Reconfiguration Recursive and Efficient Hardware for Karatsuba-Offman's Multiplication Algorithm, Control Applications”, Proceedings of 2003 IEEE Conference; vol. 2, CCA 2003,(Jun. 23-25, 2003),1076-1081.
Montgomery: Five, Six, and Seven-Term Karatsuba-Like Formulae; IEEE Transactions on Computers, vol. 54, No. 3, Mar. 2005, 8 pages.
Sedlak: the RSA Cryptography Processor; Institut fur Theoretische lnformatik, Germany, Copyright 1998, Springer-Verlag, pp. 95-105, 14 pages total.
Montgomery: Modular Multiplication Without Trial Division; Mathematics of Computation, vol. 44, No. 170, Apr. 1985, pp. 519-521.
Barrett: Implementing the RivestShamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor; Computer Security Ltd, Aug. 1986; Advances in Cryptology—Crypto '86, LNCS 263, pp. 311-323; Copyright Springer-Verlag, Berlin, Heidelberg 1987.
Fischer et al: Duality Between Multiplicatio and Modular Reduction; Infineon Technologies AG, Secure Mobile Solutions, Munich, Germany; Intel Corp., Systems Tech. Labl, Hillsboro, OR; pp. 1-13.
Weimerskirch et al: Generalizations of the Karatsuba Algorithm for Polynomial Multiplication; communication Security Group, Dep't of Electrical Engineering & Info. Sciences, Bochum, Germany, Mar. 2002; pp. 1-23.
Koc et al: Analyzing and Comparing Montgomery Multiplication Algorithms; IEEE Micro, 16(3): Jun. 26-33, 1996; Dep't of Electrical & Computer Engineering, OSU, Corvallis, Oregon,; pp. 1-18.
Number Theory and Public Key Cryptography; Introduction to Number Theory, pp. 1-14.
Tenca et al: A Scalable Architecture for Montgomery Multiplication; Electrical & Computer Engineering; OSU, Corvallis, OR,; Cryptographic Hardware and Embedded Systems, CHES 99, C.K. Koc et al, Lecture Notes in computer Science, No. 1717, pp. 94-108, New York, NY: Springer-Verlag, 1999.
Phatak et al: Fast Modular Reduction for Large Wordlenghts via One Linear and One Cyclic Convolution, Computer Science & Electrical Engineering Dep't, Univ. of Mayland, Baltimore, MD; 8 pages.
Dhem: Design of an Efficient Public-Key Cryptographic Library for RISC-Based Smart Cards; Faculte Des Sciences appliquees Laboratoire de Microelectronique; Louvain-la-Neuve, Belgium, May 1998, 198 pages.
Office Action received for German Patent Application No. 11 2007 001 319.2, Mailed on Jan. 15, 2010, 8 pages of Office Action and English translation of 8 pages.
International Preliminary Report on Patentability for PCT Patent Application No. PCT/US2007/071746, mailed on Jan. 15, 2009, 2 Pages.
Office Action received for Chinese Patent Application No. 200780024552.4, Mailed on Jan. 8, 2010, 4 pages of Office Action and English translation of 6 pages.
Office Action received for Chinese Patent Application No. 200780024552.4, mailed on Jun. 21, 2010, 4 pages of Office Action and English translation of 6 pages.
International Search Report and Written Opinion for PCT Application No. PCT/US2007/071746, mailed on Dec. 17, 2007, 11 pages.
Bace Matthew M.
Gaubatz Gunnar
Gopal Vinodh
Hasenplaugh William C.
Grossman Tucker Perreault & Pfleger PLLC
Intel Corporation
Mai Tan V
LandOfFree
Multiplying two numbers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiplying two numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplying two numbers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2656975