The power of logarithmic quantizations and computations has been recognized as a useful tool in optimizing the performance of large ML models. In this article, we provide results that demonstrate significantly better quantization signal-to-noise ratio performance thanks to multiple-base logarithmic number systems (MDLNS) in comparison with the floatingpoint quantizations that use the same number of bits. On a hardware level, we present details about our Xilinx VCU-128 FPGA design for dot product and matrixvector computations. The MDLNS matrix-vector design significantly outperforms equivalent fixed-point binary designs in terms of area (A) and time (T) complexity and power consumption as evidenced by a 4× scaling of AT2metric for VLSI performance, and 57% increase in computational throughput per watt compared to fixed-point arithmetic.

Primality generation is the cornerstone of several essential cryptographic systems. The problem has been a subject of deep investigations, but there is still a substantial room for improvements. Typically, the algorithms used have two parts – trial divisions aimed at eliminating numbers with small prime factors and primality tests based on an easy-to-compute statement that is valid for primes and invalid for composites. In this paper, we will showcase a technique that will eliminate the first phase of the primality testing algorithms. The computational simulations show a reduction of the primality generation time by about 30 percent in the case of 1024-bit RSA key pairs. This can be particularly beneficial in the case of decentralized environments for shared RSA keys as the initial trial division part of the key generation algorithms can be avoided at no cost. This also significantly reduces the communication complexity. Another essential contribution of the paper is the introduction of a new one-way function that is computationally simpler than the existing ones used in public-key cryptography. This function can be used to create new random number generators, and it also could be potentially used for designing entirely new public-key encryption systems.

Permission-less distributed ledgers provide a promising approach to deal with the Internet of Things (IoT) paradigm. Since IoT devices mostly generate data transactions and micro payments, distributed ledgers that use fees to regulate the network access are not an optimal choice. In this paper, we study a feeless architecture developed by IOTA and designed specifically for the IoT. Due to the lack of fees, malicious nodes can exploit this feature to generate an unbounded number of transactions and perform denial of service attacks. We propose to mitigate these attacks through verifiable delay functions. These functions, which are non-parallelizable, hard to compute and easy to verify, have been formulated only recently. In our work, we design a denial of service prevention mechanism which addresses network heterogeneity, limited node computational capabilities and hardware-specific implementation optimizations. Verifiable delay functions have mostly been studied from a theoretical point of view, but little has been done in tangible applications. Hence, this paper can be considered as a pioneer work in the field, since it builds a bridge between this theoretical mathematical framework and a real-world problem.

This paper proposes a computational method for 2D 8×8 DCT based on algebraic integers. The proposed algorithm is based on the Loeffler 1D DCT algorithm, and it is shown to operate with exact computation—i.e., error-free arithmetic—up to the final reconstruction step (FRS). The proposed algebraic integer architecture maintains error-free computations until an entire block of DCT coefficients having size 8×8 is computed, unlike algorithms in the literature which claim to be error-free but in fact introduce arithmetic errors between the column- and row-wise 1D DCT stages in a 2D DCT operation. Fast algorithms are proposed for the final reconstruction step employing two approaches, namely, the expansion factor and dyadic approximation. A digital architecture is also proposed for a particular FRS algorithm, and is implemented on an FPGA platform for on-chip verification. The FPGA implementation operates at 360 MHz, and is capable of a real-time throughput of$3.6\cdot 10^8$2D DCTs of size 8×8 every second, with corresponding pixel rate of$2.3\cdot 10^{10}$pixels per second. The digital architecture is synthesized using 180 nm CMOS standard cells and shows a chip area of 7.41 mm$^2$. The CMOS design is predicted to operate at 893 MHz clock frequency, at a dynamic power consumption 13.22 mW/MHz$\cdot$V$_{sup}^2$.

This paper introduces a new method for computing matrix exponential based on truncated Neumann series. The efficiency of the method is based on smart factorizations for evaluation of several Neumann series that can be done in parallel and divided across different processors with low communication overhead. A physical realization on FPGA is provided for proof-of-concept. The method is verified to be advantageous over the usual Horner's rule approach for polynomial evaluation. The hardware verification shows a reduction of 62% in time required for processing for series approximations with 9 terms. Software verification demonstrates a 30% reduction in time compared to Horner's rule and the trade-offs between using a higher precision approach is illustrated.

A joint numerical representation based on both Gaussian and Eisenstein integers is proposed. This Gauss-Eisenstein representation maps complex numbers into four-tuples of integers with arbitrarily high precision. The representation furnishes the computation of the 3-, 6-, and 12-point discrete Fourier transform (DFT) at any desired accuracy. The associated fast algorithms based on the Gauss-Eisenstein integers are error-free up to the final reconstruction step, which can be realized in hardware as a multiplierless implementation. The introduced methods are compared with competing algorithms in terms of arithmetic complexity. We propose three FRS architectures based on the following methods: Dempster-McLeod representation, expansion factor, and addition aware quantization. The Gauss-Eisenstein 12-point DFT is physically realized on a Xilinx Virtex 6 FPGA device with maximum clock frequency of 302 MHz for the expansion factor FRS with real-time throughput of 3:62 × 109 coefficients/s. The FPGA verified digital designs were synthesized, mapped, placed and finally routed for 0:18mm CMOS technology assuming a 1.8 V DC supply employing Austria Micro Systems (AMS) standard-cell library (hitkit version 4.11). The routed ASIC is predicted to operate at a maximum frequency of 505 MHz for the expansion factor FRS with potential real-time throughput of 6:06 × 109coefficients/s.

This paper extends the choice available for secure real number implementations with two new contributions. We will consider the numbers represented in form a-φ b where φ is the golden ratio, and in form (-1)s.2e where e is a fixed-point number. We develop basic arithmetic operations together with some frequently used elementary functions. All the operations are implemented and benchmarked on SHAREMIND secure multi-party computation framework. It turns out that the new proposals provide viable alternatives to standard floating- and fixed-point implementations from the performance/error viewpoint in various settings. However, the optimal choice still depends on the exact requirements of the numerical algorithm to be implemented.

An 8‐point discrete cosine transform (DCT) fast algorithm based on the Loeffler DCT factorisation and algebraic integer (AI) representation is proposed. The proposed algorithm is an error‐free implementation of the Loeffler algorithm and it is capable of computing the 8‐point DCT multiplierlessly. Decoding architectures are also proposed for mapping AI encoded quantities back to usual fixed point arithmetic using canonical signed digit representation and the expansion factor method. The proposed algorithm is mapped into systolic‐array digital architectures and physically realised as digital prototype circuits using field‐programmable gate array technology on a Reconfigurable Open Architecture Computing Hardware board and mapped to 0.18 μm complementary metal–oxide–semiconductor technology using AMS Encounter Digital Implementation libraries at 1.8 V supply.

In this paper, we study a generalization of addition chains where$k$previous values are summed together on each step instead of only two values as in traditional addition chains. Such chains are called$k$-chains and we show that they have applications in finding efficient parallelizations in problems that are known to be difficult to parallelize. In particular, 3-chains improve computations of inversions in finite fields using hybrid-double multipliers. Recently, it was shown that this operation can be efficiently computed using a ternary algorithm but we show that 3-chains provide a significantly more efficient solution.

The discrete cosine transform (DCT) is a widely-used and important signal processing tool employed in a plethora of applications. Typical fast algorithms for nearly-exact computation of DCT require floating point arithmetic, are multiplier intensive, and accumulate round-off errors. Recently proposed fast algorithm arithmetic cosine transform (ACT) calculates the DCT exactly using only additions and integer constant multiplications, with very low area complexity, for null mean input sequences. The ACT can also be computed non-exactly for any input sequence, with low area complexity and low power consumption, utilizing the novel architecture described. However, as a trade-off, the ACT algorithm requires 10 non-uniformly sampled data points to calculate the eight-point DCT. This requirement can easily be satisfied for applications dealing with spatial signals such as image sensors and biomedical sensor arrays, by placing sensor elements in a non-uniform grid. In this work, a hardware architecture for the computation of the null mean ACT is proposed, followed by a novel architectures that extend the ACT for non-null mean signals. All circuits are physically implemented and tested using the Xilinx XC6VLX240T FPGA device and synthesized for 45 nm TSMC standard-cell library for performance assessment.

Fast inversion in finite fields is crucial for high-performance cryptography and codes. We present techniques to exploit the recently proposed hybrid-double multipliers for fast inversions in binary fields GF(2m) with normal bases. A hybrid-double multiplier computes a double multiplication, the product of three elements in GF(2m), with a latency comparable to the latency of single multiplication of two elements. Traditional approaches, such as Itoh-Tsujii, cannot utilize hybrid-double multipliers. We devise a new inversion algorithm based on ternary representations that exploits their potential. The algorithm reduces the latency of inversion significantly for the fields recommended by NIST if hybrid-double multipliers are employed. For example, the algorithm computes an inversion in GF(2163) with only five double multiplications whereas the Itoh-Tsujii algorithm requires nine single or double multiplications. We propose a new inverter architecture using this new algorithm and a hybrid-double multiplier. We show that it is faster than the existing techniques by providing ASIC synthesis results using 65-nm CMOS technology. For example, our inverter for GF(2163) achieves about 34 percent shorter computation time than an inverter using the Itoh-Tsujii algorithm and a single multiplier.

In this paper we offer new algorithms for one of the most common operations in public key cryptosystems: the inversion over binary Galois fields. The new algorithms are based on using double-base and triple-base representations. They are provably more economical-in terms of the average number of multiplications-than the popular Itoh-Tsujii algorithm. In addition to having fewer multiplications, the new inversion algorithms offer further implementation advantages because they allow more efficient computation of squarings and, in some cases, require fewer temporary variables. The new algorithms are straightforwardly usable in both software and hardware implementations.

An area efficient row-parallel architecture is proposed for the real-time implementation of bivariate algebraic integer (AI) encoded 2-D discrete cosine transform (DCT) for image and video processing. The proposed architecture computes 8 × 8 2-D DCT transform based on the Arai DCT algorithm. An improved fast algorithm for AI-based 1-D DCT computation is proposed along with a single channel 2-D DCT architecture. The design improves on the four-channel AI DCT architecture that was published recently by reducing the number of integer channels to one and the number of eight-point 1-D DCT cores from five down to two. The architecture offers exact computation of 8 × 8 blocks of the 2-D DCT coefficients up to the FRS, which converts the coefficients from the AI representation to fixed-point format using the method of expansion factors. Prototype circuits corresponding to FRS blocks based on two expansion factors are realized, tested, and verified on FPGA-chip, using a Xilinx Virtex-6 XC6VLX240T device. Post place-and-route results show a 20% reduction in terms of area compared to the 2-D DCT architecture requiring five 1-D AI cores. The area-time and area-time2complexity metrics are also reduced by 23% and 22% respectively for designs with eight-bit input word length. The digital realizations are simulated up to place and route for ASICs using 45 nm CMOS standard cells. The maximum estimated clock rate is 951 MHz for the CMOS realizations indicating 7.608·109pixels/s and a 8 × 8 block rate of 118.875 MHz.

In this paper, a multi-encoding approach using wavelet based subband coding is proposed to accomplish error free calculations from exact representation of Daubechies 4-tap wavelet filter coefficients using the algebraic integer (AI) representation. By mapping the irrational coefficients to a convenient AI basis, the proposed architecture is designed employing a parallel channel model having two data paths carrying integer sequences. The computations done in the AI architecture are exactly accurate and are done entirely in a multiplier-free circuit. The design is implemented on a Xilinx Virtex-6 device at 172 MHz and hardware co-simulated with an ML605 board at 100 MHz. AI mapping facilitates simplicity and error-free calculations. The proposed architecture has a single final reconstruction step (FRS). Booth encoding has been adopted at the FRS to minimize the error which can be incurred at this point. This paper provides a hardware and power analysis for different bit lengths. An example output image sequence for the mandrill image is also provided.

Scalar multiplication in elliptic curve cryptography is the most computational intensive operation. Efficiency of this operation can be significantly improved in hardware implementations by using Frobenius endomorphisms which require integer toτ-adic nonadjacent form conversion. Because conversion is one of the limiting factors in some of Koblitz curve-based cryptosystems, it has become an interesting problem. In this paper, we propose two algorithms and a novel hardware architecture to double the speed of integer toτ-adic nonadjacent form conversion.

An algebraic integer (AI)-based time-multiplexed row-parallel architecture and two final reconstruction step (FRS) algorithms are proposed for the implementation of bivariate AI encoded 2-D discrete cosine transform (DCT). The architecture directly realizes an error-free 2-D DCT without using FRSs between row-column transforms, leading to an 8 × 8 2-D DCT that is entirely free of quantization errors in AI basis. As a result, the user-selectable accuracy for each of the coefficients in the FRS facilitates each of the 64 coefficients to have its precision set independently of others, avoiding the leakage of quantization noise between channels as is the case for published DCT designs. The proposed FRS uses two approaches based on: 1) optimized Dempster-Macleod multipliers, and 2) expansion factor scaling. This architecture enables low-noise high-dynamic range applications in digital video processing that requires full control of the finite-precision computation of the 2-D DCT. The proposed architectures and FRS techniques are experimentally verified and validated using hardware implementations that are physically realized and verified on field-programmable gate array (FPGA) chip. Six designs, for 4-bit and 8-bit input word sizes, using the two proposed FRS schemes, have been designed, simulated, physically implemented, and measured. The maximum clock rate and block rate achieved among 8-bit input designs are 307.787 MHz and 38.47 MHz, respectively, implying a pixel rate of 8 × 307.787≈2.462 GHz if eventually embedded in a real- time video-processing system. The equivalent frame rate is about 1187.35Hz for the image size of 1920 × 1080. All implementations are functional on a Xilinx Virtex-6 XC6VLX240T FPGA device.

Koblitz curves are a special set of elliptic curves and have improved performance in computing scalar multiplication in elliptic curve cryptography due to the Frobenius endomorphism. Double-base number system approach for Frobenius expansion has improved the performance in single scalar multiplication. In this paper, we present a new algorithm to generate a sparse and joint τ-adic representation for a pair of scalars and its application in double scalar multiplication. The new algorithm is inspired from double-base number system. We achieve 12% improvement in speed against state-of-the-art τ-adic joint sparse form.

A time-multiplexed row-parallel architecture is pro- posed for the real-time implementation of bivariate algebraic integer (AI) encoded 2-D discrete cosine transform (DCT) of images and video sequences. The architecture is based on the Arai algorithm with AI encoding. This leads to an 8×8 2-D DCT which is entirely free of quantization errors. The error free coefficients may be converted into a regular arithmetic format using a final reconstruction step (FRS) at the output stage. The accuracy of the FRS allows each of the 64 coefficients to have its precision set independent of other coefficients without the leakage of quantization noise between coefficient channels. Our architecture leads to low-noise applications in digital video compression, coding, and other image processing applications that rely on the fast systolic computation of the 2-D DCT. A prototype of the 2-D DCT is physically realized, tested, and verified on chip, using a Xilinx Virtex-4 S×35-10ff668 device. The maximum clock rate was Fclock= 121 MHz, implying an equivalent frame sample rate of 466 Hz, for an image frame size of 1920 × 1080, which is a common high definition video format.

Single and double scalar multiplications are the most computational intensive operations in elliptic curve based cryptosystems. Improving the performance of these operations is generally achieved by means of integer recoding techniques, which aim at minimizing the scalars' density of nonzero digits. The hybrid binary-ternary number system provides both short representations and small density. In this paper, we present three novel algorithms for both single and double scalar multiplication. We present a detailed theoretical analysis, together with timings and fair comparisons over both tripling-oriented Doche-Ichart-Kohel curves and generic Weierstrass curves. Our experiments show that our algorithms are almost always faster than their widely used counterparts.

In this paper, we shall introduce several new algorithms for integer multiplication that are based on specific multiple-radix representation of one of the multiplicands. We provide extensive theoretical analysis and experimental results for multipliers based on the new representations on 0.18 μm CMOS technology. They provide a clear picture about the advantages of the new method in 64-bit hardware implementations compared to array-based classical multiplier and radix-8-based multiplier. The proposed multipliers have better area and power consumption compared to reference multipliers.

Multi-exponentiation is a common and time consuming operation in public-key cryptography. Its elliptic curve counterpart, called multi-scalar multiplication is extensively used for digital signature verification. Several algorithms have been proposed to speed-up those critical computations. They are based on simultaneously recoding a set of integers in order to minimize the number of general multiplications or point additions. When signed-digit recoding techniques can be used, as in the world of elliptic curves, Joint Sparse Form (JSF) and interleaving w-NAF are the most efficient algorithms. In this paper, a novel recoding algorithm for a pair of integers is proposed, based on a decomposition that mixes powers of 2 and powers of 3. The so-called Hybrid Binary-Ternary Joint Form require fewer digits and is sparser than the JSF and the interleaving w-NAF. Its advantages are illustrated for elliptic curve double-scalar multiplication; the operation counts show a gain of up to 19%.

This paper proposes to represent the floating-point multipliers required to perform IDCT implementations using a rational Diophantine (i.e. ratio of integers) approximation with a common denominator, which is not necessarily a power of two. A case study to support this proposal is presented by applying the proposed scheme to Chenpsilas IDCT algorithm. Results show better performance when applying the proposed scheme compared to the traditional shift process. Similar studies can be obtained for any other potential up-scaling factor, and by modifying any other potential IDCT fast algorithm.

We describe algorithms for point multiplication on Koblitz curves using multiple-base expansions of the form $k = \sum \pm \tau^a (\tau-1)^b$ and $k= \sum \pm \tau^a (\tau-1)^b (\tau^2 - \tau - 1)^c.$ We prove that the number of terms in the second type is sublinear in the bit length of $k$, which leads to the first provably sublinear point multiplication algorithm on Koblitz curves. For the first type, we conjecture that the number of terms is sublinear and provide numerical evidence demonstrating that the number of terms is significantly less than that of $\tau$-adic non-adjacent form expansions. We present details of an innovative FPGA implementation of our algorithm and performance data demonstrating the efficiency of our method. We also show that implementations with very low computation latency are possible with the proposed method because parallel processing can be exploited efficiently.

This paper explores the use of the double-base number system (DBNS) for constant integer multiplication. The DBNS recoding scheme represents integers - in this case constants in a multiple-radix way in the hope of minimizing the number of additions to be performed during constant multiplication. On the theoretical side, we propose a formal proof which shows that our recoding technique diminishes the number of additions in a sublinear way. Therefore, we prove Lefevre's conjecture that the multiplication by an integer constant is achievable in sublinear time. In a second part, we investigate various strategies and we provide numerical data showcasing the potential interest of our approach.

This paper presents a novel error-free (infinite-precision) architecture for the fast implementation of both 8/spl times/8 2D discrete cosine transform and inverse DCT. The architecture uses a new algebraic integer quantization of a 1D radix-8 DCT that allows the separable computation of a 2D 8/spl times/8 DCT without any intermediate number representation conversions. This is a considerable improvement on previously introduced algebraic integer encoding techniques to compute both DCT and IDCT which eliminates the requirements to approximate the transformation matrix elements by obtaining their exact representations and hence mapping the transcendental functions without any errors. Using this encoding scheme, an entire 8/spl times/8 1D DCT-SQ (scalar quantization) algorithm can be implemented with only 24 adders. Apart from the multiplication-free nature, this new mapping scheme fits to this algorithm, eliminating any computational or quantization errors and resulting short-word-length and high-speed-design.

In this paper we propose an architecture for the implementation of fault-tolerant computation for a high throughput multirate equalizer used in a 1 Gbps asymmetrical wireless LAN. Exploiting the algebraic structure of the modulus replication residue number system (MRRNS) minimizes the area overhead, and the area cost to correct a fault in a single computational channel is 82.7%. Generalized results for single error correction showing significant area savings are also presented.

The multidimensional logarithmic number system (MDLNS), which has similar properties to the classical logarithmic number system (LNS), provides more degrees of freedom than the LNS by virtue of having two, or more, orthogonal bases and has the ability to use multiple MDLNS components, or digits. Unlike the LNS, there is no monotonic relationship between standard binary representations and MDLNS representations. Using look-up tables (LUTs) to perform the mapping function can be unrealistic for hardware implementations when large binary ranges or multiple digits are used. This work proposes a novel range-addressable technique for using look-up tables that allows efficient conversion from binary-to-single or multidigit MDLNS with varying accuracies, depending on the selected implementation.

A novel encoding scheme is introduced with applications to error-free computation of discrete wavelet transforms (DWT) based on Daubechies wavelets. The encoding scheme is based on an algebraic integer decomposition of the wavelet coefficients. This work is a continuation of our research into error-free computation of DCTs and IDCTs, and this extension is timely since the DWT is part of the new standard for JPEG2000. This encoding technique eliminates the requirements to approximate the transformation matrix elements by obtaining their exact representations. As a result, we achieve error-free calculations up to the final reconstruction step where we are free to choose an approximate substitution precision based on a hardware/accuracy trade-off.

The multi-dimensional logarithmic number system (MDLNS), with similar properties to the logarithmic number system (LNS), provides more degrees of freedom than the LNS by virtue of having two orthogonal bases and the ability to use multiple digits. Unlike the LNS, there is no direct functional relationship between binary/floating point representation and the MDLNS representation. Traditionally look-up tables (LUTs) were used to move from the binary domain to the MDLNS domain. This method can be unrealistic for hardware implementation when large binary ranges or multiple digits are used. This paper introduces a range addressable technique for table look-up arrays that allows efficient conversion from binary to single or multi-digit MDLNS.

A recently introduced double-base number representation has proved to be successful in improving the performance of several algorithms in cryptography and digital signal processing. The index-calculus version of this number system can be regarded as a two-dimensional extension of the classical logarithmic number system. This paper builds on previous special results by generalizing the number system both in multiple dimensions (multiple bases) and by the use of multiple digits. Adopting both generalizations the paper shows that large reductions in hardware complexity are achievable compared to an equivalent precision logarithmic number system.

In this paper, we propose new algorithms for multiple modular exponentiation operations. The major aim of these algorithms is to speed up the performance of some cryptographic protocols based on multiexponentiation. Our new algorithms are based on binary-like complex arithmetic, introduced by K. Pekmestzi (1989) and generalized in this paper.

In this paper, we analyze some of the main properties of a double base number system, using bases 2 and 3; in particular, we emphasize the sparseness of the representation. A simple geometric interpretation allows an efficient implementation of the basic arithmetic operations and we introduce an index calculus for logarithmic-like arithmetic with considerable hardware reductions in lookup table size. We discuss the application of this number system in the area of digital signal processing; we illustrate the discussion with examples of finite impulse response filtering.

This paper describes techniques for using locally connected analog cellular neural networks (CNNs) to implement digital arithmetic arrays; the arithmetic is implemented using a recently disclosed Double-Base Number System (DBNS). The CNN arrays are targeted for low power low-noise DSP applications where lower slew rate during transitions is a potential advantage. Specifically, we demonstrate that a CNN array, using a simple nonlinear feedback template, with hysteresis, can perform arbitrary length arithmetic with good performance in terms of stability and robustness. The principles presented in this paper can also be used to implement arithmetic in other number systems such as the binary number system.

In this paper we introduce an algebraic integer encoding scheme for the basis matrix elements of 8/spl times/8 DCTs and IDCTs. In particular, we encode the function cos(/spl pi//16) and generate the other matrix elements using standard trigonometric identities. This encoding technique eliminates the requirement to approximate the matrix elements; rather we use algebraic 'placeholders' for them. Using this encoding scheme we are able to produce a multiplication free implementation of the Feig-Winograd algorithm.

Presents a rigorous theoretical analysis of the main properties of a double-base number system, using bases 2 and 3. In particular, we emphasize the sparseness of the representation. A simple geometric interpretation allows an efficient implementation of the basic arithmetic operations, and we introduce an index calculus for logarithmic-like arithmetic with considerable hardware reductions in look-up table size. Two potential areas of applications are discussed: applications in digital signal processing for computation of inner products and in cryptography for computation of modular exponentiations.

In this paper, we propose new algorithms for multiple modular exponentiation operations. The major aim of these algorithms is to speed up the performance of some cryptographic protocols based on multi-exponentiation. The algorithms proposed are based on binary-like complex arithmetic, introduced by K. Pekmestzi (1989) and generalized in this paper.

In the paper a new and interesting algorithm for computing the matrix polynomial is proposed. The comparison demonstrates that this is the most efficient algorithm among the existing algorithms. Furthermore we argue that the approach is optimal in the framework of the discussed algorithms. A new interesting number system is proposed in order to derive the approach.>