A High-Performance Hardware Design for Computing Bézout's Coefficients Using Extended Stein's Algorithm

Bézout's Coefficients are critical mathematical constructs in cryptography, particularly for public key cryptographic applications requiring increasingly large keys. As software-based methods for calculating these coefficients approach their performance limits, hardware implementations present a promising alternative for faster and more efficient computation. This paper proposes a scalable 64-bit hardware implementation for the computation of Bézout's coefficients using a previously proposed Extended Stein's Algorithm Implementation which replaces the multiplication and division operations found in Extended Euclid's Algorithm with addition and binary shift operations. The algorithm uses a Controller and Datapath approach with the aim of shifting hardware complexity from the Datapath to the control logic, thus shortening the critical path and improving performance. The hardware implementation efficiency is evaluated, its advantages and limitations are discussed. The results demonstrate that the proposed implementation achieves efficient computation of Bézout's coefficients with a minimum clock period of 8 ns when synthesized on a Basys 3 Artix-7 FPGA. The design effectively balances performance and resource utilization, requiring 1628 LUTs and 535 FFs while maintaining scalability for larger bit sizes. This work establishes a foundation for future research into hardware accelerated cryptographic computations, particularly in applications requiring fast modular inverses and efficient key generation.