Search

In this paper, we presented a method of minimizing the number of overlapped partial products in the accumulation of four-term Karatsuba multiplication. This method reduced the summation of 13 overlapped partial products to 9 and the summation of 40 overlapped partial products to 24 in the case of four-term Karatsuba multiplication and eight-term Karatsuba multiplication, respectively. Moreover, to deal with the problem of negative multiplicands introduced by the choice in the evaluation of four-term Karatsuba multiplication, we further presented a method of converting negative multiplicands to non-negative multiplicands. In this way, our method would lead to the reduction of summation complexity and not using signed multipliers. Compared to the original Karatsuba multiplication designs, our proposed Karatsuba-like multiplication with optimal interpolation would lead to up to 7.7% reduction in ADP (area-delay-product) in ASIC implementations, and up to 20.2% reduction in ADP compared with built-in designs of Synopsys Design Compiler.

Being able to detect program runtime complexity is useful in many tasks (e.g., checking expected performance and identifying potential security vulnerabilities). In this work, we introduce a new dynamic approach for inferring the asymptotic complexity bounds of recursive programs. From program execution traces, we learn recurrence relations and solve them using pattern matching to obtain closed-form solutions representing the complexity bounds of the program. This approach allows us to efficiently infer simple recurrence relations that represent nontrivial, potentially nonlinear polynomial and non-polynomial, complexity bounds. We present Dynaplex, a tool that implements these ideas to automatically generate recurrence relations from execution traces. Our preliminary results on popular and challenging recursive programs show that Dynaplex can learn precise relations capturing worst-case complexity bounds (e.g., O ( n log n ) for mergesort, O (2 n ) for Tower of Hanoi and O ( n 1.58 ) for Karatsuba’s multiplication algorithm).

In this paper we introduce a unified field multiplier for the EC kP operation in two different types of Galois fields. The most important contributions of this paper are that the multiplier is based on the 4-segment Karatsuba multiplication method and that it is inherent resistant against selected horizontal attacks., Comment: Author's version accepted for DTIS-2018; the final publication is available at https://ieeexplore.ieee.org/abstract/document/8368560

Modular multiplication of very long integers is a key building block of fully homomorphic encryption and elliptic curve cryptography. The Karatsuba algorithm reduces the multiplication complexity by decomposing the operands into shorter segments. However, in the case of long numbers, adding up the segment products to derive the final product and then carrying out modular reduction as in previous designs can take many clock cycles. This paper focuses on moduli in the format of Solinas prime and proposes to integrate modular reduction into every segment product of the Karatsuba integer multiplication. As a result, the length of the intermediate results is further reduced and they can be added up simultaneously by using a carry-save adder at the cost of small area increase. Additionally, the computation scheduling are optimized to reduce the required number of registers and multiplexers. Complexity analysis shows that, for decomposition factors of 2, 3 and 4, our design requires on average 18.5% less clock cycles with only 5.9% area overhead and similar critical path compared to carrying out the modular reduction on the final product.