{'fraction_non_alphanumeric': 0.026599568655643422, 'fraction_numerical': 0.0050323508267433505, 'mean_word_length': 5.13215859030837, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Low-Latency Architecture for the Parallel Extended GCD Algorithm of Large Numbers

The extended Greatest Common Divisor (GCD) is an extension of the GCD operation, which computes not only the GCD of integers a and b but also the Bezout's coefficients that are integers x and y such that ax + by =3D GCD(a,b). Recently, the large-number extended GCD algorithm is used in the core function of the next-generation blockchain systems and served as the most time-consuming operation. Considering the efficiency, speeding up this operation is urgently desired. However, the extended GCD, which is rarely explored in literature, is extremely hard to parallelize because of long serial operations with strong data dependency. In this paper, we propose a low- latency architecture for the extended GCD of large numbers by utilizing many algorithmic transformations and architectural optimizations. Firstly, a parallel extended GCD algorithm is well studied and modified to be practical in hardware. Secondly, a high-parallel architecture is designed for the selected extended GCD, where the trade-off is well evaluated between computation latency and power consumption. Finally, the architecture is coded using Verilog language and synthesized under the TSMC 28- nm CMOS technology. The experimental results for the 1024-bit extended GCD show that our design significantly outperforms the prior arts.