Search

Within the transport layer security (TLS) protocol version 1.3, RFC 7748 specifies elliptic curves targeted at the 128-bit and the 224-bit security levels. For the 128-bit security level, the Montgomery curve Curve25519 and its birationally equivalent twisted Edwards curve Ed25519 are specified; for the 224-bit security level, the Montgomery curve Curve448, the Edwards curve Edwards448 (which is isogenous to Curve448) and another Edwards curve which is birationally equivalent to Curve448 are specified. Our first contribution is to provide the presently best known 64-bit assembly implementations of Diffie–Hellman shared secret computation using Curve25519. The main contribution of this work is to propose new pairs of Montgomery–Edwards curves at the 128-bit and the 224-bit security levels. The new curves are nice in the sense that they have very small curve coefficients and base points. Compared to the curves in RFC 7748, the new curves lose two bits of security. The gain is improved efficiency. For Intel processors, we have made different types of implementations of the Diffie–Hellman shared secret computation using the new curves. The new curve at the 128-bit level is faster than Curve25519 for all types of implementations that we considered, while the new curve at the 224-bit level is faster than Curve448 using 64-bit sequential implementation using schoolbook multiplication, but is slower than Curve448 for vectorized implementation using Karatsuba multiplication. Overall, the new curves provide good alternatives to Curve25519 and Curve448.

Applications such as public-key cryptography are critically reliant on the speed of modular multiplication for their performance. This paper introduces a new block-based variant of Montgomery multiplication, the Block Product Scanning (BPS) method, which is particularly efficient using new 512-bit advanced vector instructions (AVX-512) on modern Intel processor families. Our parallel-multiplication approach also allows for squaring and sub-quadratic Karatsuba enhancements. We demonstrate $$1.9\,\times $$ 1.9 × improvement in decryption throughput in comparison with OpenSSL and $$1.5\,\times $$ 1.5 × improvement in modular exponentiation throughput compared to GMP-6.1.2 on an Intel Xeon CPU. In addition, we show $$1.4\,\times $$ 1.4 × improvement in decryption throughput in comparison with state-of-the-art vector implementations on many-core Knights Landing Xeon Phi hardware. Finally, we show how interleaving Chinese remainder theorem-based RSA calculations within our parallel BPS technique halves decryption latency while providing protection against fault-injection attacks.

Modular multiplication is one of the most time-consuming operations that account for almost 80% of computational overhead in a scalar multiplication in elliptic curve cryptography. In this paper, we present a new speed record for modular multiplication over 192-bit NIST prime P-192 on 8-bit AVR ATmega microcontrollers. We propose a new integer representation named Range Shifted Representation (RSR) which enables an efficient merging of the reduction operation into the subtractive Karatsuba multiplication. This merging results in a dramatic optimization in the intermediate accumulation of modular multiplication by reducing a significant amount of unnecessary memory access as well as the number of addition operations. Our merged modular multiplication on RSR is designed to have two duplicated groups of 96-bit intermediate values during accumulation. Hence, only one accumulation of the group is required and the result can be used twice. Consequently, we significantly reduce the number of load/store instructions which are known to be one of the most time-consuming operations for modular multiplication on constrained devices. Our implementation requires only 2888 cycles for the modular multiplication of 192-bit integers and outperforms the previous best result for modular multiplication over P-192 by a factor of 17%. In addition, our modular multiplication is even faster than the Karatsuba multiplication (without reduction) which achieved a speed record for multiplication on AVR processor.

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.

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.

This paper presents new speed records for multiprecision multiplication on the AVR ATmega family of 8-bit microcontrollers. For example, our software takes only 1,969 cycles for the multiplication of two 160-bit integers; this is more than 15 % faster than that demonstrated in previous work. For 256-bit inputs, our software is not only the first to break through the 6,000-cycle barrier; with only 4,771 cycles it also breaks through the 5,000-cycle barrier and is more than 21 % faster than previous work. We achieve these speed records by carefully optimizing the Karatsuba multiplication technique for AVR ATmega. One might expect that subquadratic-complexity Karatsuba multiplication is only faster than algorithms with quadratic complexity for large inputs. This paper shows that it is in fact faster than fully unrolled product-scanning multiplication already for surprisingly small inputs, starting at 48 bits. Our results thus make Karatsuba multiplication the method of choice for high-performance implementations of elliptic-curve cryptography on AVR ATmega microcontrollers.

Bourgain posed the problem of calculating $$\begin{aligned} \Sigma = \sup _{n \ge 1} ~\sup _{k_1 < \cdots < k_n} \frac{1}{\sqrt{n}} \left\| \sum _{j=1}^n e^{2 \pi i k_j \theta } \right\| _{L^1([0,1])}. \end{aligned}$$ It is clear that \(\Sigma \le 1\); beyond that, determining whether \(\Sigma < 1\) or \(\Sigma =1\) would have some interesting implications, for example concerning the problem whether all rank one transformations have singular maximal spectral type. In the present paper we prove \(\Sigma \ge \sqrt{\pi }/2 \approx 0.886\), by this means improving a result of Karatsuba. For the proof we use a quantitative two-dimensional version of the central limit theorem for lacunary trigonometric series, which in its original form is due to Salem and Zygmund.

The double-precision floating-point arithmetic, specifically multiplication, is a widely used arithmetic operation for many scientific and signal processing applications. In general, the double-precision floating-point multiplier requires a large 53×53 mantissa multiplication in order to get the final result. This mantissa multiplication exists as a limit on both area and performance bounds of this operation. This paper presents a novel way to reduce this large multiplication. The proposed approach in this paper allows to use less amount of multiplication hardware compared to the traditional method. The multiplication is done by using Karatsuba technique. This design is specifically targeting Field Programmable Gate Array (FPGA) platforms, and it has also been evaluated on ASIC flow. The proposed module gives excellent performance with efficient use of resources. The design is fully compatible with the IEEE standard precision. The proposed module has shown a better performance in comparison with the best reported multipliers in the literature.

We study an asymptotic behavior of the sum $\sum\limits_{n\le x}\frac{\D \tau(n)}{\D \tau(n+a)}$. Here $\tau(n)$ denotes the number of divisors of $n$ and $a\ge 1$ is a fixed integer.

The applicability of fast multiplication algorithms to sparse structures is discussed. Estimates for the degree of sparseness of matrices and polynomials are given for which fast multiplication algorithms have advantages over standard multiplication algorithms in terms of the multiplicative complexity. Specifically, the Karatsuba and Strassen algorithms are studied under the assumption of the uniform distribution of zero elements.

The Strassen approach to fast multiplication of large numbers with the use of the Fast Walsh Transformation (FWT) algorithm for calculation of discrete convolution is developed. A priori complexity estimates for the constructed algorithm, results of the comparative analysis with the Karatsuba-Offman, Schonhage-Strassen, and standard algorithms, and domains of its efficient application are given.