Single and multiple precision sequential large multipliers for field-programmable gate arrays

This paper presents single and multiple precision sequential large multiplier designs for field-programmable gate arrays. Both designs use the Karatsuba Ofman method. They are pipelined and can generate a full size (double operand size) or a single size product. The syntheses results show that the sequential large Karatsuba Ofman multiplier (SLKOM) implementations have up to 2.23 times less delay compared with the standard sequential large multipliers implementations presented in previous research. The 2048-bit multiple precision sequential Karatsuba Ofman large multiplier (MPSLKOM) implementation can simultaneously execute eight 256-bit multiplications. The MPSLKOM implementations use roughly 1% more registers and up to 3% more LUTs than the SLKOM implementations.

PDF

___

[1] FIPS P. 186-2. Digital Signature Standard (DSS). Gaithersburg, MD, USA: National Institute of Standards and Technology (NIST), 2000.
[2] Menezes AJ, Van Oorschot PC, Vanstone SA. Handbook of Applied Cryptography. Boca Raton, FL, USA: CRC press, 1996.
[3] Bodrato M. Towards optimal Toom-Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0. In: Arithmetic of Finite Fields, June 2122 2007; Madrid, Spain: Springer. pp. 116-133.
[4] Karatsuba A, Ofman Y. Multiplication of multidigit numbers on automata. English translation in Soviet PhysicsDoklady 1963; 7: 595-596.
[5] Quan G, Davis JP, Devarkal S, Buell DA. High-level synthesis for large bit-width multipliers on FPGAs: a case study. In: Proceedings of the 3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis; 1921 September 2005; Jersey City, NJ, USA: ACM. pp. 213-218.
[6] Gao S, Chabini N, Al-Khalili D, Langlois P. Optimised realisations of large integer multipliers and squarers using embedded blocks. IET Comput Digit Tec 2007; 1: 9-16.
[7] Athow JL, Al-Khalili AJ. Implementation of large-integer hardware multiplier in Xilinx FPGA. In: 15th IEEE International Conference on Electronics, Circuits and Systems, ICECS; 31 August3 September 2008; St. Julians, Malta: IEEE. pp. 1300-1303.
[8] Bessalah H, Messaoudi K, Issad M, Anane N, Anane M. Left to right serial multiplier for large numbers on FPGA. In: The 3rd International Design and Test Workshop; 2022 December 2008; Monastir, Tunisia: IEEE. pp. 288-293.
[9] Banescu S, De Dinechin F, Pasca B, Tudoran R. Multipliers for floating-point double precision and beyond on FPGAs. ACM Comp Ar 2011; 38: 73-79.
[10] Jaiswal M, Cheung RC. Area-efficient architectures for large integer and quadruple precision floating point multipliers. In: The 20th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM); 29 April1 May 2012; Toronto, Canada: IEEE. pp. 25-28.
[11] Gao S, Al-Khalili D, Chabini N, Langlois P. Asymmetric large size multipliers with optimised FPGA resource utilisation. IET Comput Digit Tec 2012; 6: 372-383.
[12] Senturk A, Gok M. Pipelined large multiplier designs on FPGAs. In: The 15th Euromicro Conference on Digital System Design; 58 September 2012; Izmir, Turkey: IEEE. pp. 809-814.