Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2008-07-15
2008-07-15
Malzahn, David H (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
10636321
ABSTRACT:
Multi-precision multiplication methods include storing a first operand and a second operand as a first array and a second array of n words. A first weighted sum is determined from multiple subproducts of corresponding words of the first operand and the second operand. The methods may further include iteratively determining a next weighted sum from a previous weighted sum and a recursively calculated intermediate product. The disclosed methods can be used in a variety of different applications (e.g., cryptography) and can be implemented in a number of software or hardware environments.
REFERENCES:
patent: 4037093 (1977-07-01), Gregg et al.
patent: 4435823 (1984-03-01), Davis et al.
patent: 4754421 (1988-06-01), Bosshart
patent: 4811269 (1989-03-01), Hirose et al.
patent: 5220606 (1993-06-01), Greenberg
patent: 5457804 (1995-10-01), Ohtomo
patent: 5880985 (1999-03-01), Makineni et al.
patent: 6026420 (2000-02-01), DesJardins et al.
patent: 6199087 (2001-03-01), Blake et al.
patent: 6233597 (2001-05-01), Tanoue et al.
patent: 6343305 (2002-01-01), Koc et al.
patent: 6421807 (2002-07-01), Nakamura et al.
patent: 6466959 (2002-10-01), Blake et al.
patent: 6766345 (2004-07-01), Stein et al.
patent: 6993136 (2006-01-01), Solinas
patent: 7003106 (2006-02-01), Ouyang
patent: 7031468 (2006-04-01), Hoffstein et al.
patent: 7082452 (2006-07-01), Stein et al.
patent: 7111166 (2006-09-01), Dror et al.
patent: 7133889 (2006-11-01), Parthasarathy et al.
patent: 2001/0024502 (2001-09-01), Ohkuma et al.
patent: 2002/0016773 (2002-02-01), Ohkuma et al.
patent: 2002/0039418 (2002-04-01), Dror et al.
patent: 2002/0041681 (2002-04-01), Hoffstein et al.
patent: 2003/0068037 (2003-04-01), Bertoni et al.
patent: 2003/0105791 (2003-06-01), Stein et al.
patent: 2003/0110196 (2003-06-01), Stein et al.
patent: 2003/0128841 (2003-07-01), Ouyang
patent: 2003/0133568 (2003-07-01), Stein et al.
patent: 2003/0135530 (2003-07-01), Parthasarathy et al.
patent: 2003/0140078 (2003-07-01), Feuser
patent: 2003/0206628 (2003-11-01), Gura et al.
patent: 2003/0206629 (2003-11-01), Eberle et al.
patent: 2003/0212729 (2003-11-01), Eberle et al.
patent: 2004/0107341 (2004-06-01), Hall et al.
patent: 2004/0109561 (2004-06-01), Koc et al.
patent: 2006/0269054 (2006-11-01), Dror et al.
Cormen et al.,Introduction to Algorithms, MIT, pp. 59-61 (1990).
De Win et al., “A fast software implementation for arithmetic operations in GF(2n),”Advances in Cryptology—ASIACRYPT 96, Proceedings, pp. 65-76 (1996).
Diffie et al., “New Directions in Cryptography,”IEEE Trans. Information Theory, pp. 644-654 (1976).
Erdem et al., “A Less Recursive Variant of Karatsuba-Ofman Algorithm for Multiplying Operands of Size a Power of Two,”16th IEEE Symposium on Computer Arithmetic, 8 pp (2003).
Erdem, “Improving the Karatsuba-Ofman Multiplication Algorithm for Special Applications,” Ph.D. Thesis, Oregon State University (2002).
Geddes et al.,Algorithms for Computer Algebra, Kluwer Academic Publishers, Boston Chapter 4, pp. 111-145 (1992).
Guajardo et al., “Efficient algorithms for elliptic curve cryptosystems,”Advances in Cryptology—CRYPTO 97, Proceedings, pp. 342-356 (1997).
IEEE P1363, “Standard specifications for public-key cryptography,” Draft Version 13 (Nov. 12, 1999).
Johnson et al., “The Elliptic Curve Digital Signature Algorithm (ECDSA),” Technical Report CORR 99-34, Dept. of C&O, University of Waterloo, Canada, 55 pp. (1999).
Karatsuba et al., “Multiplication of Multidigit Numbers on Automata,”Soviet Physics-Doklady, vol. 7, pp. 595-596 (1963).
Knuth,The Art of Computer Programming, vol. 2,Seminumerical Algorithms, Addison-Wesley, Reading, MA, pp. 265-294 (1998).
Koblitz, “Elliptic curve cryptosystems,”Mathematics of Computation, vol. 48, No. 177, pp. 203-209 (Jan. 1987).
Koç,High-Speed RSA Implementation: Version 2.0, RSA Laboratories, 73 pp. (Nov. 1994).
Koç et al., “Montgomery Multiplication in GF(2k),”Design, Codes and Cryptography, vol. 14, pp. 57-69 (1998).
Lidl et al.,Introduction to Finite Fields and Their Applications, Cambridge University Press, New York, NY, pp. 541-566 (1994).
Menezes,Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, Boston, MA, pp. 83-99 (1993).
Menezes et al.,Handbook of Applied Cryptography, CRC Press, Boca Raton, FL, pp. 591-630 (1997).
Miller, “Uses of Elliptic Curves in Cryptography,”Advances in Cryptology—CRYPTO 85, Proceedings, pp. 417-426 (1985).
Montgomery, “Modular Multiplication Without Trial Division,”Mathematics of Computation, vol. 44, pp. 519-521 (1985).
Mullin et al., “Optimal Normal Bases in GF(pn),”Discrete Applied Mathematics, vol. 22, pp. 149-161 (1988).
National Institute for Standards and Technology, Digital Signature Standard (DSS), FIPS PUB 186-2, 76 pp. (Jan. 2000).
Paar et al., “Fast Arithmetic Architectures for Public-Key Algorithms over Galois Fields GF((2n)m),”Advances in Cryptology—EURO-CRYPT 97, Proceedings, pp. 363-378 (1997).
Rivest et al., “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,”Communications of the ACM, vol. 21, No. 2, pp. 120-126 (Feb. 1978).
Schroeppel et al., “Fast Key Exchange with Elliptic Curve Systems,”Advances in Cryptology—CRYPTO 95, Proceedings, pp. 43-56 (1995).
Silverman, “Fast Multiplication in Finite Field GF (2N),”Cryptographic Hardware and Embedded Systems, pp. 122-134 (1999).
Office action mailed Feb. 1, 2007 in U.S. Appl. No. 10/636,326, filed Aug. 6, 2003 (published as U.S. Patent Application Publication No. 2004/0109561).
Office action mailed Jul. 18, 2007 in U.S. Appl. No. 10/636,326, filed Aug. 6, 2003 (published as U.S. Patent Application Publication No. 2004/0109561).
Office action mailed Feb. 13, 2008, in U.S. Appl. No. 10/636,326, filed Aug. 6, 2003 (published as U.S. Patent Application Publication No. 2004/0109561).
Erdem Serdar S.
Koç Çetin K.
Klarquist & Sparkman, LLP
Malzahn David H
The State of Oregon Acting by and Through the State Board of Hig
LandOfFree
Multiplication of multi-precision numbers having a size of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiplication of multi-precision numbers having a size of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplication of multi-precision numbers having a size of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3914491