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.

The main objective is to develop floating-point multiplication (FPM) using 5:3 compressor based Vedic multiplier (VM), Karatsuba algorithm (KA) and canonical signed digit (CSD) algorithm to overcom...

We obtain new bounds of exponential sums modulo a prime $p$ with binomials $ax^k + bx^n$. In particular, for $k=1$, we improve the bound of Karatsuba (1967) from $O(n^{1/4} p^{3/4})$ to $O\left(p^{3/4} + n^{1/3}p^{2/3}\right)$ for any $n$, and then use it to improve the bound of Akulinichev (1965) from $O(p^{5/6})$ to $O(p^{4/5})$ for $n | (p-1)$. The result is based on a new bound on the number of solutions and of degrees of irreducible components of certain equations over finite fields.

We continue the study of Mastrovito form of Karatsuba (MK) multipliers under the shifted polynomial basis (SPB). An MK multiplier utilizes Karatsuba algorithm and Mastrovito approach to optimize polynomial multiplication and modular reduction, which lead to a better space and time tradeoff for all trinomials. Based on this work, we make two types of contributions: 1) We derive a new modular reduction formulation for constructing Mastrovito matrix associated with special types of pentanomials, i.e., Types I, II, and Type C.1 pentanomial. Through related formulations, we demonstrate that Type I pentanomial is less efficient than Type II because of a more complicated modular reduction under the same SPB; conversely, Type C.1 pentanomial is as good as Type II under generalized polynomial basis (GPB). 2) We introduce a new MK multiplier for Type II pentanomial. It is shown that our proposal is only one $T_{X}$ slower than the fastest quadratic multipliers for Type II pentanomial, but its space complexity is roughly 3/4 of those schemes. To the best of our knowledge, it is the first time for hybrid multiplier to achieve such a time delay bound.

Multiplication is an essential step in a lot of calculations. In this paper we look at multiplication of 2 binary polynomials of degree at most n-1, modulo an irreducible polynomial of degree n with 2n input and n output qubits, without ancillary qubits, assuming no errors. With straightforward schoolbook methods this would result in a quadratic number of Toffoli gates and a linear number of CNOT gates. This paper introduces a new algorithm that uses the same space, but by utilizing space-efficient variants of Karatsuba multiplication methods it requires only O(n^{\log_2(3)}) Toffoli gates at the cost of a higher CNOT gate count: theoretically up to O(n^2) but in examples the CNOT gate count looks a lot better.

In this paper, we continue the study of bit-parallel multiplier using three-term Karatsuba algorithm (KA), recently introduced by Li et al. (VLSI Design 2018). The three-term KA is the simplest var...

Recently, hybrid multiplication schemes over the binary extension field $GF(2^{m})$ based on $n$ -term Karatsuba algorithm (KA) have been proposed for irreducible trinomials. Their complexities depend on a decomposition of $m$ and the choice of a generation polynomial. However, these multipliers have some limitations on a decomposition of $m$ or generation polynomial $x^{m}+x^{k}+1$ such that $m\geq 2k$ . In this paper, we loosen such limited conditions. We present a new hybrid bit-parallel multiplier based on $n$ -term KA for any irreducible trinomial $x^{m}+x^{k}+1\,\,(0 , where $m$ is decomposed as $m=nm_{0}+r$ with $0 and $1 . (Here, various values for $n,m_{0}$ and $r$ may be chosen.) To this end, we generalize the previously proposed multiplication scheme for $x^{nm_{0}+1}+x^{k}+1$ into $x^{nm_{0}+r}+x^{k}+1$ . We evaluate the explicit complexity of the proposed multiplier. Specific comparisons show that the proposed multiplier achieves the lowest space complexity with the same or lower time complexity among hybrid multipliers. Compared to the fastest multipliers, the time complexity of the proposed multiplier costs only $T_{X}$ higher while its space complexity is much lower (it has roughly 40% reduced space complexity), where $T_{X}$ is the delay of one 2-input XOR gate.

Recently, new multiplication schemes over the binary extension field $GF(2^{m})$ based on an $n$ -term Karatsuba algorithm have been proposed for irreducible trinomials. In this paper, we extend these schemes for trinomials to any irreducible polynomials. We introduce some new types of pentanomials and propose multipliers for those pentanomials utilizing the extended schemes. We evaluate the rigorous space and time complexities of the proposed multipliers, and compare those with similar bit-parallel multipliers for pentanomials. As a main contribution, the best space complexities of our multipliers are $\frac {1}2m^{2}+O\left({m^{\frac {3}2}}\right)$ AND gates and $\frac {1}2m^{2}+O\left({m^{\frac {3}2}}\right)$ XOR gates, which nearly correspond to the best results for trinomials. Also, specific comparisons for three fields $GF(2^{163})$ , $GF(2^{283})$ , and $GF(2^{571})$ recommended by NIST show that the proposed multiplier has roughly 40% reduced space complexity compared to the fastest multipliers, while it costs a few more XOR gate delay. It is noticed that our space complexity gain is much greater than the time complexity loss. Moreover, the proposed multiplier has about 21% reduced space complexity than the best-known space efficient multipliers, while having the same time complexity. The results show that the proposed multipliers are the best space optimized multipliers.

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

In 2012, Barbulescu, Detrey, Estibals and Zimmermann proposed a new framework to exhaustively search for optimal formulae for evaluating bilinear maps, such as Strassen or Karatsuba formulae. The main contribution of this work is a new criterion to aggressively prune useless branches in the exhaustive search, thus leading to the computation of new optimal formulae, in particular for the short product modulo X 5 and the circulant product modulo (X 5 − 1). Moreover , we are able to prove that there is essentially only one optimal decomposition of the product of 3 x 2 by 2 x 3 matrices up to the action of some group of automorphisms.

A Karatsuba algorithm (KA) is used for highly accurate multiplication using a divide and conquer approach. A new approach to a polynomial digit-serial multiplier that uses an optimal digit ...

We propose bit-parallel GF(2 m ) multipliers for irreducible trinomials using an n-term Karatsuba algorithm and Mastrovito approach, which are generalizations of the newly proposed multiplication scheme for a specific trinomial. The complexities of the proposed multipliers for GF(2 m ) depend on the choice of an irreducible trinomial x m + x k + 1 defining GF(2 m ) and values n, m 0 such that m = nm 0 or m = nm 0 + 1. It is possible to achieve a space-time tradeoff by choosing proper values for k, n, and m 0 . For the purpose of a specific comparison, we compare the proposed multipliers with the best-known multipliers for an odd m ∈ [399, 450] for which there exists an irreducible trinomial of degree m. As a result, the proposed multipliers achieve the lowest space complexities among similar bit-parallel multipliers (they have roughly 40% reduced space complexities compared with the fastest multiplier). On the other hand, their time complexities match or are at most 2T X higher than the fastest multipliers, where T X is the delay of one 2-input XOR gate.

Overlap-Free Karatsuba Algorithm (OFKA) combined with block recombination approach (OFKABR) can improve the complexity of the original OFKA to obtain efficient implementation of polynomial basis multiplication over finite field $GF(2^{m})$ . In this paper, we have further proposed a modified OFKABR (MOFKABR) strategy to reduce the space and time complexities of the best-known method. The proposed strategy is also extended to obtain a low-complexity versatile multiplier, which is designed to support the generalized multiplication on a wider range of field size for $m_{1}\leq m\leq m_{\lambda }$ . Using the proposed MOFKABR approach, the proposed digit-serial versatile multiplier can achieve subquadratic space complexity when compared with the existing digit-serial versatile multipliers.

This paper focuses on high-speed NEON-based constant-time implementations of multiplication of large polynomials in the NIST PQC KEM Finalists: NTRU, Saber, and CRYSTALS-Kyber. We use the Number Theoretic Transform (NTT)-based multiplication in Kyber, the Toom-Cook algorithm in NTRU, and both types of multiplication in Saber. Following these algorithms and using Apple M1, we improve the decapsulation performance of the NTRU, Kyber, and Saber-based KEMs at the security level 3 by the factors of 8.4, 3.0, and 1.6, respectively, compared to the reference implementations. On Cortex-A72, we achieve the speed-ups by factors varying between 5.7 and 7.5\(\times \) for the Forward/Inverse NTT in Kyber, and between 6.0 and 7.8\(\times \) for Toom-Cook in NTRU, over the best existing implementations in pure C. For Saber, when using NEON instructions on Cortex-A72, the implementation based on NTT outperforms the implementation based on the Toom-Cook algorithm by \(14\%\) in the case of the MatrixVectorMul function but is slower by \(21\%\) in the case of the InnerProduct function. Taking into account that in Saber, keys are not available in the NTT domain, the overall performance of the NTT-based version is very close to the performance of the Toom-Cook version. The differences for the entire decapsulation at the three major security levels (1, 3, and 5) are \(-4\), \(-2\), and \(+2\%\), respectively. Our benchmarking results demonstrate that our NEON-based implementations run on an Apple M1 ARM processor are comparable to those obtained using the best AVX2-based implementations run on an AMD EPYC 7742 processor. Our work is the first NEON-based ARMv8 implementation of each of the three NIST PQC KEM finalists.

We introduce a new class of irreducible pentanomials over $${\mathbb F}_{2}$$ of the form $$f(x) = x^{2b+c} + x^{b+c} + x^b + x^c + 1$$ . Let $$m=2b+c$$ and use f to define the finite field extension of degree m. We give the exact number of operations required for computing the reduction modulo f. We also provide a multiplier based on Karatsuba algorithm in $$\mathbb {F}_2[x]$$ combined with our reduction process. We give the total cost of the multiplier and found that the bit-parallel multiplier defined by this new class of polynomials has improved XOR and AND complexity. Our multiplier has comparable time delay when compared to other multipliers based on Karatsuba algorithm.

In Internet of Things (IoT), sensor devices should deliver the collected sensor data to the server after the data is encrypted. The encrypted data cannot be eavesdropped by adversaries but the side channel information including clock cycles and power consumption patterns during encryption operations can leak the secret information. For this reason, cryptography engineering should prevent potential threats by designing the cryptography functions in secure manner. In this paper, we explore the feasible side channel attacks on cryptography operations, particularly polynomial multiplication for Galois/Counter Mode of operation (GCM). We perform the horizontal Correlation Power Analysis (CPA) on the most well-known Lopez et al.’s polynomial multiplication and successfully extract the secret values from power consumption patterns. In order to prevent proposed attack model, we suggest a masked polynomial multiplication, ensuring a regular and constant-time solution without potential vulnerabilities including Look-up Table (LUT) access and branch statements. With proposed polynomial multiplication, we suggest the secure and efficient implementation of GCM on the low-end embedded processor. Finally, we further explore the long polynomial multiplication for Elliptic Curve Cryptography (ECC) operations. We exploit the combination of Karatsuba algorithm and proposed masked polynomial multiplication, which achieved the practically fast polynomial multiplication on embedded processors.

We investigate bounds for the multiplicities m ( β + i γ ) , where β + i γ ( β ⩾ 1 2 , γ > 0 ) denotes complex zeros of ζ ( s ) . It is seen that the problem can be reduced to the estimation of the integrals of the zeta-function over “very short” intervals. A new, explicit bound for m ( β + i γ ) is also derived, which is relevant when β is close to unity. The related Karatsuba conjectures are also discussed.

In this paper, we propose a new type of non-recursive Mastrovito multiplier for $\text {GF}(2^{m})$ using an $n$ -term Karatsuba algorithm (KA), where $\text {GF}(2^{m})$ is defined by an irreducible trinomial, $x^{m}+x^{k}+1, m=nk$ . We show that such a type of trinomial combined with the $n$ -term KA can fully exploit the spatial correlation of entries in related Mastrovito product matrices and lead to a low-complexity architecture. The optimal parameter $n$ is further studied. As the main contribution of this paper, the lower bound of the space complexity of our proposal is about $O({m^{2}}/{2})+m^{3/2})$ . Meanwhile, the time complexity matches the best Karatsuba multiplier known to date. To the best of our knowledge, it is the first time that Karatsuba-based multiplier has reached such a space complexity bound while maintaining a relatively low time delay.

An overview is given of the scientific results obtained by Anatolii Alekseevich Karatsuba between the early 1990s and 2008.

We present a new type of bit-parallel non-recursive Karatsuba multiplier over $GF(2^m)$ generated by an arbitrary irreducible trinomial. This design effectively exploits Mastrovito approach and shifted polynomial basis (SPB) to reduce the time complexity and Karatsuba algorithm to reduce its space complexity. We show that this type of multiplier is only one $T_X$ slower than the fastest bit-parallel multiplier for all trinomials, where $T_X$ is the delay of one 2-input XOR gate. Meanwhile, its space complexity is roughly 3/4 of those multipliers. To the best of our knowledge, it is the first time that our scheme has reached such a time delay bound. This result outperforms previously proposed non-recursive Karatsuba multipliers.

This survey contains enlarged version of a mini-course which was read by the author in November 2015 during “Chinese - Russian workshop of exponential sums and sumsets”. This workshop was organized by professors Chaohua Jia (Institute of Mathematics, Academia Sinica) and Ke Gong (Henan University) in Academy of Mathematics and System Science, CAS (Beijing). The author is warmly grateful to them for the support and hospitality. The survey contains the Introduction, three parts and Conclusion. The basic definitions and results concerning the complete Kloosterman sums are given in the Introduction. The method of estimating of incomplete Kloosterman sums to moduli equal to the raising power of a fixed prime is described in the first part. This method is based on one idea of A. G. Postnikov which reduces the estimate of such sums to the estimate of the exponential sums with polynomial by I. M. Vinogradov’s mean value theorem. A. A. Karatsuba’s method of estimating of incomplete sums to an arbitrary moduli is described in the second part. This method is based on a very precise estimate of the number of solutions of one symmetric congruence involving inverse residues to a given modulus. This estimate plays the same role in thie problems under considering as Vinogradov’s mean value theorem in the estimating of corresponding exponential sums. The method of J. Bourgain and M. Z. Garaev is described in the third part. This method is based on very deep “sum-product estimate” and on the improvement of A. A. Karatsuba’s bound for the number of solutions of symmetric congruence. The Conclusion contains a series of recent results concerning the estimates of short Kloosterman sums.

There are a variety of ways of applying the Karatsuba idea to multi-digit multiplication. These apply particularly well in the context where digits do not use the full word-length of the computer, so that partial products can be safely accumulated without fear of overflow. Here we re-visit the “arbitrary degree” version of Karatsuba and show that the cost of this little-known variant has been over-estimated in the past. We also attempt to definitively answer the question as to the cross-over point where Karatsuba performs better than the classic method.

In this paper, we first present an enhancement of the well-known Karatsuba 2-way and 3-way algorithms for characteristic three fields, denoted by $\mathbb {F}_{3^{n}}$ where n≥1. We then derive a 3-way polynomial multiplication algorithm with five 1/3 sized multiplications that use interpolation in $\mathbb {F}_{9}$ . Following the computation of the arithmetic and delay complexity of the proposed algorithm, we provide the results of our hardware implementation of polynomial multiplications over $\mathbb {F}_{3}$ and $\mathbb {F}_{9}$ . The final proposal is a new 3-way polynomial multiplication algorithm over $\mathbb {F}_{3}$ that uses three polynomial multiplications of 1/3 of the original size over $\mathbb {F}_{3}$ and one polynomial multiplication of 1/3 of the original size over $\mathbb {F}_{9}$ . We show that this algorithm represents about 15% reduction of the complexity over previous algorithms for the polynomial multiplications whose sizes are of practical interest.

Using the Karatsuba method, we obtain new estimates for Kloosterman sums modulo a prime, which, under certain constraints on the number of summands, are sharper than similar estimates found earlier.

In this paper we introduce an accelerator for the ECC kP operation in two different types of Galois fields i.e. GF(p) and GF(2n). In order to ensure fast execution of the multiplication in both cases we integrated the carry bit separation technique to speed-up the multiplication in GF(p). The two most important contributions of this paper are that the partial multiplier applied is used for both types of Galois field and the second one is that our design is resistant against Horizontal Collision Correlation Analysis. The latter was verified in 20 test runs per supported elliptic curve.

This paper describes an $\sim {\cal O}(n)$ pre-compute technique to speed up the Karatsuba algorithm for multiplying two numbers., 6 pages

The recursion tree resulting from Karatsuba’s formula is built here using an interleaved splitting scheme rather than the traditional left/right one. This allows an easier access to the nodes of the tree and some of them are initially flattened all at once into a single recursive formula. The whole tree is then flattened further into a convolution formula involving less elementary multiplications than the usual Cauchy product—leading to iterative (rather than recursive) implementations of the algorithm. Unlike the traditional splitting scheme, the interleaved approach may also be applied to infinite power series, and the corresponding formulas are also given.

Efficient circuits for multiplication of binary polynomials use what are known as Karatsuba recurrences. These methods divide the polynomials of size (i.e. number of terms) \(k \cdot n\) into k pieces of size n. Multiplication is performed by treating the factors as degree-\((k-1)\) polynomials, with multiplication of the pieces of size n done recursively. This yields recurrences of the form \( M(k n) \le \alpha M(n) + \beta n + \gamma ,\) where M(t) is the number of binary operations necessary and sufficient for multiplying two binary polynomials with t terms each. Efficiently determining the smallest achievable values of (in order) \(\alpha , \beta , \gamma \) is an unsolved problem. We describe a search method that yields improvements to the best known Karatsuba recurrences for k = 6, 7 and 8. This yields improvements on the size of circuits for multiplication of binary polynomials in a range of practical interest.

Using Karatsuba's method, we obtain estimates for Kloosterman sums modulo a prime, in which the number of terms is less than an arbitrarily small fixed power of the modulus. These bounds refine similar results obtained earlier by Bourgain and Garaev. Bibliography: 16 titles.

In the literature, the generalized $(a, b)$ - way Karatsuba algorithm (KA) is a well-known high-precision technique for implementing a subquadratic digit-serial multiplication. We present here the corrections to the space and complexities pertaining to addition operations in $(a, b)$ -way KA approach.

Vedic mathematics is the system of mathematics followed in ancient Indian and it is applied in various mathematical branches. The word “Vedic” represents the storehouse of all knowledge. Because using Vedic Mathematics, the arithmetical problems are solved easily. The mathematical algorithms are formed from 16 sutras and 13 up-sutras. But there are some limitations in each sutra. Here, two sutras Nikhilam sutra and Karatsuba algorithm are considered. In this research paper, a novel algorithm for binary multiplication based on Vedic mathematics is designed using bit reduction technique. Though Nikhilam sutra is used for multiplication, it is not used in all applications. Because it is special in multiplication. The remainder is derived from this sutra by reducing the remainder bit size to N-2 bit. Here, the number of bits of the remainder is constantly maintained as N-2 bits. By using Karatsuba algorithm, the overall structure of the multiplier is designed. Unlike the conventional Karatsuba algorithm, the proposed algorithm requires only one multiplier with N-2 bits only. The speed of the proposed algorithm is improved with balancing the area and the power. Even though there is a deviation in lower order bits, this method shows larger difference in higher bit lengths.

A new bit-parallel Montgomery multiplier for GF ( 2 m ) is presented, where the field is generated with an irreducible trinomial. We first present a slightly generalized version of a newly proposed divide and conquer approach. Then, by combining this approach and a carefully chosen Montgomery factor, we can implement field multiplication using a composition of small polynomial multiplications and Montgomery squarings, which are simpler and more efficient. As a result, the proposed multiplier roughly saves m 2 2 logic gates compared with the fastest multipliers, with time complexity as good as or better than previous Karatsuba-based multipliers for the same class of fields. HighlightsWe construct a bit-parallel Montgomery multiplier over GF ( 2 m ) generated with all the irreducible trinomials using squaring operations.The space complexity of our proposal saves about m 2 / 2 logic gates than any other Montgomery or Mastrovito multipliers for trinomials, and matches the Karatsuba multiplier.The time complexity of our proposal is slightly higher than the fastest multipliers, but no more than 2 T X .

The Arkhipov–Karatsuba multivariate system of congruences modulo any prime greater than the degrees of forms in this system is solvable for any right-hand sides and any number of variables larger than 8(n + 1)mlog2(rn) + 12(n + 1)m + 4(n + 1), where n is the degree of the forms in the system and $$m = \left( {\begin{array}{*{20}{c}} {n + r - 1} \\ {r - 1} \end{array}} \right)$$ is the number of congruences.

We prove $\ell^{p}L^{p}$ decoupling inequalities for a class of moment manifolds. These inequalities imply optimal mean value estimates for multidimensional Weyl sums of the kind considered by Arkhipov, Chubarikov, and Karatsuba and by Parsell. In our proofs we take a new point of view on the Bourgain--Demeter--Guth induction on scales argument. This point of view substantially simplifies even the proof of $\ell^{2}L^{p}$ decoupling for the moment curve., v2: 39 pages, revised following the referee report

For each function on bit strings, its restriction to bit strings of any given length can be computed by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We describe instruction sequences of this kind that compute the function on bit strings that models multiplication on natural numbers less than $2^N$ with respect to their binary representation by bit strings of length $N$, for a fixed but arbitrary $N > 0$, according to the long multiplication algorithm and the Karatsuba multiplication algorithm. We find among other things that the instruction sequence expressing the former algorithm is longer than the one expressing the latter algorithm only if the length of the bit strings involved is greater than $2^8$. We also go into the use of an instruction sequence with backward jump instructions for expressing the long multiplication algorithm. This leads to an instruction sequence that it is shorter than the other two if the length of the bit strings involved is greater than $2$., 14 pages, the preliminaries of this paper and arXiv:1308.0219 are the same; 16 pages, results sharpened and presentation improved; 22 pages, combined with arXiv:1312.1812; 22 pages, typos corrected and explanation added

In this paper we obtain a new constant in the Polya-Vinogradov inequality. Our argument follows previously established techniques which use the Fourier expansion of an interval to reduce to Gauss sums. Our improvement comes from approximating an interval by a function with slower decay on the edges and this allows for a better estimate of the l 1 norm of the Fourier transform. This approximation induces an error for our original sums which we deal with by combining some ideas of Hildebrand with Garaev and Karatsuba concerning long character sums.

This paper presents an efficient arithmetic in extension field based on Cyclic Vector Multiplication Algorithm that reduces calculation costs over cubic extension for elliptic curve pairing cryptography. In addition, we evaluate the calculation costs compared to Karatsuba-based method.

Efficient polynomial multiplication formulae are required for cryptographic computation. From elliptic curve cryptography to homomorphic encryption, many cryptographic systems need efficient multiplication formulae. The most widely used multiplication formulae for cryptographic systems are the Karatsuba-like polynomial multiplication formulae. In this paper, these formulae and Montgomery’s work yielding more efficient such formulae are introduced. Moreover, recent efforts to improve these results are discussed by presenting associated techniques. The state of art for this area is also discussed.

We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial-size modulus q. For a polynomial L, we provide zero-knowledge arguments allowing a prover to convince a verifier that committed L-bit bitstrings x, y and z are the binary representations of integers X, Y and Z satisfying \(Z=X+Y\) over \(\mathbb {Z}\). The complexity of our arguments is only linear in L. Using them, we construct arguments allowing to prove inequalities \(X

Recently, we present a novel Mastrovito form of nonrecursive Karatsuba multiplier for all trinomials. Specifically, we found that related Mastrovito matrix is very simple for equally spaced trinomial (EST) combined with classic Karatsuba algorithm (KA), which leads to a highly efficient Karatsuba multiplier. In this paper, we consider a new special class of irreducible trinomial, namely, xm+xm/3+1. Based on a three-term KA and shifted polynomial basis (SPB), a novel bit-parallel multiplier is derived with better space and time complexity. As a main contribution, the proposed multiplier costs about 2/3 circuit gates of the fastest multipliers, while its time delay matches our former result. To the best of our knowledge, this is the first time that the space complexity bound is reached without increasing the gate delay.

Finite field arithmetics are often used in linear block codes such as BCH and Reed–Solomon codes and also in cryptographic algorithms. Finite field multipliers play an important role and consume a significant amount of area in VLSI design. This paper presents an improved generalized Karatsuba multiplier. Optimization of the Karatsuba multiplication algorithm can be done by splitting the product terms into two alternative forms and expressing all the terms in the repeated fashion. We have compared the hardware requirement of our proposed multiplier with the original Karatsuba multiplier. The proposed multiplier requires lesser number of additions compared to original Karatsuba multiplier and the overall area is reduced by 53.75% (without reduction) and 52.08% (with reduction). The proposed multiplier is also faster than the original Karatsuba multiplier by 3.63% (without reduction) and 3.91% (with reduction). The proposed modified Karatsuba multiplier is also applied to compute key equation in RS(47, 41) decoder which is applied in intelligent home networking. All the simulation works were done using Xilin14.3 ISE simulator and the multipliers were implemented in Vertex 5 FPGA device family.

Gaussian normal basis (GNB) of the even-type is popularly used in elliptic curve cryptosystems. Efficient GNB multipliers could be realised by Toeplitz matrix-vector decomposition to realise subquadratic space complexity architectures. In this study, Dickson polynomial representation is proposed as an alternative way to represent an GNB of characteristic two. The authors have derived a novel recursive Dickson–Karatsuba decomposition to achieve a subquadratic space-complexity parallel GNB multiplier. By theoretical analysis, it is shown that the proposed subquadratic multiplier saves about 50% bit-multiplications compared with the corresponding subquadratic GNB multiplication using Toeplitz matrix-vector product approach.

It is well-known that the $(a,b)$ -way Karatsuba algorithm (KA) with $a\neq b$ is used for efficient digit-serial multiplication with subquadratic space complexity architecture. In this paper, based on $(a,b)$ -way KA decomposition, we have derived a novel $k$ -way block recombination KA (BRKA) decomposition for digit-serial multiplication. The proposed $k$ -way BRKA is formed by a power of 2 polynomial decomposition. By theoretical analysis, it is shown that $k$ -way BRKA can provide the necessary tradeoff between space and time complexity. Using (4,2)-way KA to construct the proposed $k$ -way BRKA architecture in $GF(2^{409})$ , it is shown that the proposed 2-way BRKA approach requires less area, and the proposed 8-way BRKA approach requires less computation time and less area-time product compared to compared the existing $(a,b)$ -way KA decomposition.

The WG stream ciphers are based on the WG (Welch-Gong) transformation and possess proved randomness properties. In this paper we propose nine new hardware designs for the two classes of WG(29,11) and WG-16. For each class, we design and implement three versions of standard, pipelined and serial. For the first time, we use the polynomial basis (PB) representation to design and implement the WG(29,11) and WG-16. We consider traditional PB multiplier for the WG(29,11), and, the traditional and Karatsuba multipliers for the WG-16. For efficient field operations, we propose an irreducible trinomial for the WG(29,11). For the WG-16, a new formulation of its permutation which requires only 8 multipliers is introduced. In these designs, the multipliers in the transforms arefurther reduced by utilizing a novel computation for the trace of the multiplication of two field elements. We have implemented theproposed designs in ASIC using CMOS 65 nm technology. The results show that the proposed standard WG(29,11) consumes less area and slightly enhances the normalized throughput, compared to the existing counterparts. For the WG-16, throughput of theproposed pipelined instance outperforms the previous designs. Moreover, the speed of the proposed WG-16 designs meet the peak bit rates for the 4 G specifications.

We consider a problem first studied by Karatsuba, of giving lower bounds for the Riemann zeta function in short intervals of the critical line. We give an upper bound for the measure of the set where a lower bound of Karatsuba and Garaev fails to hold, and we also show a conjecture of Karatsuba holds for almost all values of t.

This paper presents several methods for reducing the number of bit operations for multiplication of polynomials over the binary field. First, a modified Bernstein’s 3-way algorithm is introduced, followed by a new 5-way algorithm. Next, a new 3-way algorithm that improves asymptotic arithmetic complexity compared to Bernstein’s 3-way algorithm is introduced. This new algorithm uses three multiplications of one-third size polynomials over the binary field and one multiplication of one-third size polynomials over the finite field with four elements. Unlike Bernstein’s algorithm, which has a linear delay complexity with respect to input size, the delay complexity of the new algorithm is logarithmic. The number of bit operations for the multiplication of polynomials over the finite field with four elements is also computed. Finally, all these new results are combined to obtain improved complexities.

One of the most cost-critical operations when applying Shor's algorithm to binary elliptic curves is the underlying field arithmetic. Here, we consider binary fields $${\mathbb {F}}_{2^n}$$F2n in polynomial basis representation, targeting especially field sizes as used in elliptic curve cryptography. Building on Karatsuba's algorithm, our software implementation automatically synthesizes a multiplication circuit with the number of $$T$$T-gates being bounded by $$7\cdot n^{\log _2(3)}$$7·nlog2(3) for any given reduction polynomial of degree $$n=2^N$$n=2N. If an irreducible trinomial of degree $$n$$n exists, then a multiplication circuit with a total gate count of $${\mathcal {O}}(n^{\log _2(3)})$$O(nlog2(3)) is available.