Search

Reed-Solomon (RS) codes are used in many storage systems for failure recovery. In popular software implementations, RS codes are defined by using a parity check matrix that is either a Cauchy matrix padded with an identity or a Vandermonde matrix. The encoding complexity can be reduced by searching for a Cauchy matrix that has a smaller number of 1s in its bit matrices or exploiting Reed-Muller (RM) transform in the Vandermonde matrix multiplication. This paper proposes two new approaches. In our first approach, different constructions of finite fields are explored to further reduce the number of ‘1’s in the bit matrices of the Cauchy matrix and a new searching method is developed to find the minimum number of ‘1’s. Our second approach defines RS codes using parity check matrices in the format of a Vandermonde matrix concatenated with an identity matrix so that the RS en/decoding can be simplified. A modified scheme is developed to enable the application of the RM transform such that the number of multiplications can be reduced.

In today's technology, a sheer number of Internet of Things applications use hardware security modules for secure communications. The widely used algorithms in security modules, for example, digital signatures and key agreement, are based upon elliptic curve cryptography (ECC). A core operation used in ECC is the point multiplication, which is computationally expensive for many Internet of things applications. In many IoT applications, such as intelligent transportation systems and distributed control systems, thousands of safety messages need to be signed and verified within a very short time-frame. Considerable research has been conducted in the design of a fast elliptic curve arithmetic on finite fields using residue number systems (RNS). In this article, we propose an RNS-based ECC core hardware for the two families of elliptic curves that are short Weierstras and twisted Edwards curves. Specifically, we present RNS implementations for SECP256K1 and ED25519 standard curves. We propose an RNS hardware architecture supporting fast elliptic curve point-addition (ECPA), point-doubling (ECPD), and point-tripling (ECPT). We implemented different ECC point multiplication algorithms on the Xilinx FPGA platform. The test results confirm that the performance of our fully RNS ECC point multiplication is better than the fastest ECC point multiplication cores in the literature.

Hardware obfuscation is a technique that modifies the circuit to hide the functionality. Obfuscations through algorithmic modifications add protection in addition to circuit-level techniques, and their effects on the data paths can be analyzed and controlled at the architectural level. Many error-correcting coding and cryptography algorithms are based on finite field arithmetic. For the first time, this paper proposes a hardware obfuscation scheme achieved through varying finite field constructions and primitive element representations. Also the variations are effectively transformed to bit permuters controlled by obfuscation keys to achieve high level of security with very small complexity overheads. To illustrate the effectiveness, the proposed scheme is applied to obfuscate Reed-Solomon decoders, which are broadly used in communication and storage systems. For a (255, 239) RS decoder over finite field $GF(256)$GF(256), the proposed scheme achieves 1239 bits of independent obfuscation key with 4.4 percent area overhead, while yielding no penalty on the throughput and only one extra clock cycle of latency.

In this paper, we present new parallel polynomial multiplication formulas which result in subquadratic space complexity. The schemes are based on a recently proposed block recombination of polynomial multiplication formula. The proposed two-way, three-way, and four-way split polynomial multiplication formulas achieve the smallest space complexities. Moreover, by providing area-time tradeoff method, the proposed formulas enable one to choose a parallel formula for polynomial multiplication which is suited for a design environment.

Gaussian normal bases (GNBs) are special set of normal bases (NBs) which yield low complexity $GF\left(2^{m}\right)$ arithmetic operations. In this paper, we present new architectures for the digit-level single, hybrid-double, and hybrid-triple multiplication of $GF\left(2^{m}\right)$ elements based on the GNB representation for odd values of $m > 1$ . The proposed fully-serial-in single multipliers perform multiplication of two field elements and offer high throughput when the data-path capacity for entering inputs is limited. The proposed hybrid-double and hybrid-triple digit-level GNB multipliers perform, respectively, two and three field multiplications using the same latency required for a single digit-level multiplier, at the expense of increased area. In addition, we present a new eight-ary field exponentiation architecture which does not require precomputed or stored intermediate values.

We show that the step “modulo the degree- $n$ field generating irreducible polynomial” in the classical definition of the $GF(2^{n})$ multiplication operation can be avoided. This leads to an alternative representation of the finite field multiplication operation. Combining this representation and the Chinese Remainder Theorem, we design bit-parallel $GF(2^{n})$ multipliers for irreducible trinomials $u^n+u^k+1$ on $GF(2)$ where $1 . For some values of $n$ , our architectures have the same time complexity as the fastest bit-parallel multipliers—the quadratic multipliers, but their space complexities are reduced. Take the special irreducible trinomial $u^{2k}+u^k+1$ for example, the space complexity of the proposed design is reduced by about $1/8$ , while the time complexity matches the best result. Our experimental results show that among the 539 values of $n$ such that $4 and $x^n+x^k+1$ is irreducible over $GF(2)$ for some $k$ in the range $1 , the proposed multipliers beat the current fastest parallel multipliers for 290 values of $n$ when $(n-1)/3 \le k \le n/2$ : they have the same time complexity, but the space complexities are reduced by $8.4$ percent on average.

We present an $r$ -th root extraction algorithm over a finite field $\mathbb {F}_q$ . Our algorithm precomputes a primitive $r^s$ -th root of unity $\xi$ where $s$ is the largest positive integer satisfying $r^s| q-1$ , and is applicable for the cases when $s$ is small. The proposed algorithm requires one exponentiation for the $r$ -th root computation and is favorably compared to the existing algorithms.

Security protocols such as Transport Layer Security implement the Elliptic curve digital signature algorithm (ECDSA) over different binary extension fields defined by the National Institute of Standards and Technology (NIST). Specifically, such multiple cipher-suite support is a security recommendation. Binary extension field arithmetic processors are expensive, especially if more than one field is supported. In this context, this article introduces a novel lightweight digit-serial parallel-in-serial-out (DS-PISO) design for versatile multiplication (DS-VPISO) targeting the NIST-like fields in resource constrained embedded systems where the crypto module allocation is limited. The proposed DS-VPISO multiplier offers competitive area (up to 40 percent area savings) compared to existing multiple field multiplier schemes based on results conducted on bit-serial implementations using Intel's Field programmable gate arrays. The article first presents a DS-PISO self-dual Gaussian normal basis multiplication architecture based on the trace mapping. After this, the article extends the new trace based DS-PISO multiplier to construct an architecture for the first versatile DS-PISO multiplication (DS-VPISO) targeting NIST's binary fields. The latter extension to versatile multiplication is based on novel architectures for versatile cyclic shifts and versatile multiplication by normal elements.

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.

Besides Karatsuba’s algorithm, optimal Toeplitz matrix-vector product (TMVP) formulae is another approach to design $GF(2^n)$ subquadratic multipliers. However, when $GF(2^n)$ elements are represented using a polynomial basis or its generalization—shifted polynomial basis—this approach is currently appliable only to fields $GF(2^n)$ generated by an irreducible trinomial or a special type of irreducible pentanomials, but not to a general irreducible pentanomial. The reason is that no transformation matrix, which transforms the Mastrovito matrix into a Toeplitz matrix, has been found. In this article, we propose such a transformation matrix and its inverse matrix for an arbitrary irreducible pentanomial.

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.

This paper presents a formal method for designing cryptographic processor datapaths on the basis of arithmetic circuits over Galois fields (GFs). The proposed method describes GF arithmetic circuits in the form of hierarchical graph structures, where nodes represent sub-circuits whose functions are defined by arithmetic formulae over GFs, and edges represent data dependency between nodes. In this paper, we first introduce the application of graph representation to arithmetic circuits over extension fields of ${\mbi {GF}}({{\mbi {p}}^{\mbi {m}}})$ $({\mbi {p}} \geq {\bf 2})$ and composite fields, which are commonly used in the design of cryptographic processors. The newly proposed graph representation can be formally verified through symbolic computation techniques based on polynomial reduction and Grobner basis. We then demonstrate the capabilities of the proposed approach through an experimental design of a 128-bit AES (Advanced Encryption Standard) datapath including multiplicative inversion circuits over the composite field ${\mbi {GF}}{(((2^2)^2)^2})$ . The results show that the proposed method can describe such practical datapaths, as well as that complete verification of such a datapath can be carried out within a short period of time.

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.

The choice of radix is crucial for multivalued logic synthesis. Practical examples, however, reveal that it is not always possible to find the optimal radix when taking into consideration actual physical parameters of multivalued operations. In other words, each radix has its advantages and disadvantages. Our proposal is to synthesize logic in different radices, so it may benefit from their combination. The theory presented in this paper is based on Reed-Muller expansions over Galois field arithmetic. The work aims to first estimate the potential of the new approach and to second analyze its impact on circuit parameters down to the level of physical gates. The presented theory has been applied to real-life examples focusing on cryptographic circuits where Galois Fields find frequent application. The benchmark results show that the approach creates a new dimension for the trade-off between circuit parameters and provides information on how the implemented functions are related to different radices.

Since its acceptance as the adopted symmetric-key algorithm, the Advanced Encryption Standard (AES) and its recently standardized authentication Galois/Counter Mode (GCM) have been utilized in various security-constrained applications. Many of the AES-GCM applications are power and resource constrained and require efficient hardware implementations. In this paper, different application-specific integrated circuit (ASIC) architectures of building blocks of the AES-GCM algorithms are evaluated and optimized to identify the high-performance and low-power architectures for the AES-GCM. For the AES, we evaluate the performance of more than 40 S-boxes utilizing a fixed benchmark platform in 65-nm CMOS technology. To obtain the least complexity S-box, the formulations for the Galois Field (GF) subfield inversions in GF(24) are optimized. By conducting exhaustive simulations for the input transitions, we analyze the average and peak power consumptions of the AES S-boxes considering the switching activities, gate-level netlists, and parasitic information. Additionally, we present high-speed, parallel hardware architectures for reaching low-latency and high-throughput structures of the GCM. Finally, by investigating the high-performance GF(2128) multiplier architectures, we benchmark the proposed AES-GCM architectures using quadratic and subquadratic hardware complexity GF(2128) multipliers. It is shown that the performance of the presented AES-GCM architectures outperforms the previously reported ones in the utilized 65-nm CMOS technology.

Efficient finite field multiplication is crucial for implementing public key cryptosystem. To achieve this, multipliers using Gaussian normal basis have been widely explored in previous works. In this paper, based on proposed Gaussian normal basis Montgomery (GNBM) representation, a semi-systolic even-type GNBM multiplier is developed. Analysis shows that the proposed architecture saves about 57 percent space complexity and 50 percent time complexity when compared with the only existing semi-systolic even-type GNB multiplier. Moreover, due to properties of regularity and modularity, the proposed multiplier is very suitable for VLSI implementation.

Normal basis has been widely used for the representation of binary field elements mainly due to its low-cost squaring operation. Optimal normal basis type II is a special class of normal basis exhibiting very low multiplication complexity and is considered as a safe choice for hardware implementation of cryptographic applications. In this paper, high-speed architectures for binary field multiplication using reordered normal basis are proposed, where reordered normal basis is referred to as a certain permutation of optimal normal basis type II. Complexity comparison shows that the proposed architectures are faster compared to previously presented architectures in the open literature using either an optimal normal basis type II or a reordered normal basis. One advantage of the new word-level architectures is that the critical path delay is a constant (not a function of word size). This enables the multipliers to operate at very high clock rates regardless of the field size or the number of words. Hardware implementation of some practical size multipliers for elliptic curve cryptography is also included.

Multiplication is one of the most important operations in finite field arithmetic. It is used in cryptographic and coding applications, such as elliptic curve cryptography and Reed-Solomon codes. In this paper, we consider the finite field multiplication used in elliptic curve cryptography and design concurrent error detection circuits. It is shown in the literature that the Montgomery multiplication can be used in cryptography to accelerate the scalar multiplication. Here, we use a parity-based concurrent error detection approach to increase the reliability of different Montgomery multipliers available in the literature. First, we consider bit-serial Montgomery multiplication and propose an error detection circuit. Then, we apply the same technique on the digit-serial Montgomery multiplication. Finally, we consider low time-complexity bit-parallel Montgomery multiplication and design the required components to implement the concurrent error detection circuits. ASIC implementations have been completed to analyze the time and area overheads of the proposed schemes. Also, the error detection capability is investigated by software simulations. We show that our approach results in efficient error detection schemes with small time and area overheads.

International audience; This paper deals with binary field multiplication. We use the bivariate representation of binary field called Double Polynomial System (DPS) presented in [11]. This concept generalizes the composite field representation to every finite field. As shown in [11], the main interest of DPS representation is that it enables to use Lagrange approach for multiplication, and in the best case, Fast Fourier Transform approach, which optimizes Lagrange approach. We use here a different strategy from [11] to perform reduction, and we also propose in this paper, some new approaches for constructing DPS. We focus on DPS, which provides a simpler and more efficient method for coefficient reduction. This enables us to avoid a multiplication required in the Montgomery reduction approach of [11], and thus to improve the complexity of the DPS multiplier. The resulting algorithm proposed in the present paper is subquadratic in space Oðn 1:31 Þ and logarithmic in time. The space complexity is 33 percent better than in [11] and 18 percent faster. It is asymptotically more efficient than the best known method [6] (specifiably more efficient than [6] when n ! 3;000). Furthermore, our proposal is available for every n and not only for n a power of two or three.

Reed-Muller expressions and their various extensions and generalizations for binary and multiple-valued logic functions are an important class of discrete function representations that are often used in practical applications. These expressions can be uniformly viewed as discrete polynomial expressions over finite fields GF(2) and GF(q) or the field of rational numbers in the case of expressions with integer-valued coefficients. The optimization of them in the number of product terms count is performed by selecting either positive or negative literals (polarities) for variables in the functions to be represented. Since there are no ways to select in advance the polarity for variables that will result in most compact expression for a given function, all possible expressions have to be generated and the simplest of them selected. This is a task computationally very demanding, the complexity of which is O(q^n \times C), where C is the time to calculate a particular polarity. Since the reduction of the first factor may lead to missing the most compact expression, the reduction of C is the single option to speed up the procedure. In this paper, we propose an approach to the solution of this problem by exploiting the notion of extended dual polarity, which provides a simple way of ordering polarities to obtain an effective way of finding the optimal one by reducing the time to move between them. The method still implies exhaustive search, but it is an optimized search, which may be expressed in very simple rules resulting in efficient implementation. Experimental results illustrate the effectiveness of the proposed method.

Multiplication and squaring are main finite field operations in cryptographic computations and designing efficient multipliers and squarers affect the performance of cryptosystems. In this paper, we consider the Montgomery multiplication in the binary extension fields and study different structures of bit-serial and bit-parallel multipliers. For each of these structures, we study the role of the Montgomery factor, and then by using appropriate factors, propose new architectures. Specifically, we propose two bit-serial multipliers for general irreducible polynomials, and then derive bit-parallel Montgomery multipliers for two important classes of irreducible polynomials. In this regard, first we consider trinomials and provide a way for finding efficient Montgomery factors which results in a low time complexity. Then, we consider type-II irreducible pentanomials and design two bit-parallel multipliers which are comparable to the best finite field multipliers reported in the literature. Moreover, we consider squaring using this family of irreducible polynomials and show that this operation can be performed very fast with the time complexity of two XOR gates.

L'articolo descrive una nuova rappresentazione degli elementi nei campi finiti di tipo GF(2^m) che consente la realizzazione di architetture hardware parallele più efficienti e flessibili rispetto ai più recenti contributi presentati nella letteratura tecnica. La rappresentazione trova impiego nella realizzazione di circuiti per operazioni crittografiche, codici per la correzione dell'errore, etc. SOMMARIO DELL'ARTICOLO: This work studies efficient bit-parallel multiplication in GF(2^m) for irreducible pentanomials, based on the so-called Shifted Polynomial Bases (SPBs). We derive a closed expression of the reduced SPB product for a class of polynomials x^m+x^(k_s)+ x^(k_(s-1))+... +x^(k_1)+1, with k_s-k_1

Error correction software for Bose-Chaudhuri-Hochquenghem (BCH) codes is optimized for general purpose processors that do not equip hardware for Galois field arithmetic. The developed software applies parallelization with a table lookup method to reduce the number of iterations, and maximum parallelization under a cache size limitation is sought for a high throughput implementation. Since this method minimizes the number of lookup tables for encoding and decoding processes, a large parallel factor can be chosen for a given cache size. The naive word length of a general purpose CPU is used as a whole by employing the developed mask elimination method. The tradeoff of the algorithm complexity and the regularity is examined for several syndrome generation methods, which leads to a simple error detection scheme that reuses the encoder and a simplified syndrome generation method requiring only a small number of Galois field multiplications. The parallel factor for Chien search is increased much by transforming the error locator polynomial so that it contains symmetric exponents of positive and negative signs. The experimental results demonstrate that the developed software cannot only provide sufficient throughput for real-time error correction of NAND flash memory in embedded systems but also enhance the reliability of file systems in general purpose computers.

Fault-based cryptanalysis has been developed to effectively break both private-key and public-key cryptosystems, making robust finite field multiplication a very important research topic in recent years. However, no robust normal basis multiplier has been proposed in the literature. Therefore, this investigation presents a semisystolic Gaussian normal basis multiplier. Based on the proposed Gaussian normal basis multiplier, both concurrent error detection and correction capabilities can be easily achieved using time redundancy technology with no hardware modification.

In this paper, we study exponentiation in the specific finite fields F, with very special exponents such as those that occur in algorithms for computing square roots. Here, q is a prime power, q = pk, where k > 1, and k is odd. Our algorithmic approach improves the corresponding exponentiation resulted from the better rewritten exponent. To the best of our knowledge, it is the first major improvement to the Tonelli-Shanks algorithm, for example, the number of multiplications can be reduced to at least 60 percent on the average when p= 1 (mod 16). Several numerical examples are given that show the speedup of the proposed methods.

A high performance architecture of elliptic curve scalar multiplication based on the Montgomery ladder method over finite field GF(2m) is proposed. A pseudo-pipelined word serial finite field multiplier with word size w, suitable for the scalar multiplication is also developed. Implemented in hardware, this system performs a scalar multiplication in approximately 6lceilm/wrceil(m-1) clock cycles and the gate delay in the critical path is equal to TAND + lceillog2(w/k)rceilTXOR, where TAND and TXOR are delays due to two-input AND and XOR gates respectively and 1 les k Lt w is used to shorten the critical path.

This paper presents an algebraic testing method for detecting stuck-at faults in the polynomial-basis (PB) bit-parallel (BP) multiplier circuits over GF(2m). The proposed technique derives the test vectors from the expressions of the inner product (IP) variables without any requirement of the ATPG tool. This low- complexity testing method requires (2m + 1) test vectors for detecting single stuck-at faults in the AND part and multiple stuck-at faults in the EXOR part of the multiplier circuits. The test vectors are independent of the multiplier's structure, as proposed in (T. A. Gulliver et al., 1991), but are dependent on m. For the multiplier circuits, the test set is found to be smaller in size than the ATPG-generated test set. The test set provides 100 percent single stuck-at fault coverage.

In this paper, three small classes of finite fields GF(2m) are found for which low complexity bit-parallel multipliers are proposed. The proposed multipliers have lower complexities compared to those based on the irreducible pentanomials. It is also shown that there does not always exist an irreducible all-one polynomial, equally-spaced polynomial, or trinomial for the new classes of fields.

In this paper, we extend previously known results on the complexities of normal elements. Using algorithms that exhaustively test field elements, we are able to provide the distribution of the complexity of normal elements for binary fields with degree extensions up to 39. We also provide current results on the smallest known complexity for the remaining degree extensions up to 512 by using a combination of constructive theorems and known exact values. We give an algorithm to exhaustively search field elements by using Gray codes, which allows us to reuse previous computations. We compare this with a standard method. We analyze this algorithm and show both experimentally and asymptotically that the Gray code optimization gives substantial savings. The total computation of the distribution of the complexity of normal elements for degrees up to 39 in our experiments allows us to draw several conjectures. In particular, our data provides remarkable evidence for the conjecture that the complexity of normal elements follows a normal distribution. Finally, we conjecture that there is no linear bound on the minimum complexity with respect to the degree of the extension.

We present an innovative methodology for accelerating the elliptic curve point formulae over prime fields. This flexible technique uses the substitution of multiplication with squaring and other cheaper operations, by exploiting the fact that field squaring is generally less costly than multiplication. Applying this substitution to the traditional formulae, we obtain faster point operations in unprotected sequential implementations. We show the significant impact our methodology has in protecting against Simple Side-Channel Attacks (SSCA). We modify the ECC point formulae to achieve a faster atomic structure when applying atomicity side-channel protection. In contrast to previous atomic operations that assumed squarings are undistinguishable from multiplications, our new atomic structure offers true SSCA-protection because it includes squaring in its formulation. We also extend our implementation to parallel architectures such as SIMD (Single-Instruction Multiple-Data). With the introduction of a new coordinate system and with the flexibility of our methodology, we present, to our knowledge, the fastest formulae for SIMD-based schemes that are capable of executing 3 and 4 operations simultaneously. Finally, a new parallel SSCA-protected scheme is proposed for multiprocessor/parallel architectures by applying the atomic structure presented in this work. Our parallel and atomic operations are shown to be significantly faster than previous implementations.

In this contribution, we introduce a low-complexity bit-parallel algorithm for computing square roots over binary extension fields. Our proposed method can be applied to any type of irreducible polynomials. We derive explicit formulas for the space and time complexities associated with the square root operator when working with binary extension fields generated using irreducible trinomials. We show that, for those finite fields, it is possible to compute the square root of an arbitrary field element with equal or better hardware efficiency than the one associated with the field squaring operation. Furthermore, a practical application of the square root operator in the domain of field exponentiation computation is presented.

Elliptic-Curve cryptography (ECC) is promising for enabling information security in constrained embedded devices. In order to be efficient on a target architecture, ECCs require accurate choice/tuning of the algorithms that perform the underlying mathematical operations. This paper contributes with a cycle-level analysis of the dependencies of ECC performance from the interaction between the features of the mathematical algorithms and the actual architectural and microarchitectural features of an ARM-based Intel XScale processor. Another contribution is the cycle-level analysis of a modified ARM processor that includes a word-level finite field polynomial multiplier (poly_mul) in its data path. This extension constitutes a good trade-off between applicability in a number of contexts, the simplicity of integration within the processor, and performance. This paper points out the most advantageous mix of elliptic curve (EC) parameters both for the standard ARM-based Intel XScale platform and for the one equipped with the polyjnul unit. In particular, the latter case allows for more than 41 percent execution time reduction on the considered benchmarks. Last, this paper investigates the correlation between the possible architectural organizations of a processor equipped with poly_mul unit(s) and EC benchmark performance. For instance, only superscalar pipelines can exploit the features of out-of-order execution and only very complex organizations (for example, four way superscalar) can exploit a high number of available ALUs. Conversely, we show that there are no benefits in endowing the processor with more than one poly_mul, and we point out a possible trade-off between performance and complexity increase: A two-way in-order/out-of-order pipeline allows +50 percent and +90 percent of Instructions per Cycle (IPC), respectively. Finally, we show that there are no critical constraints on the latency and pipelining capability of the polyjnul unit for the basic EC point multiplication.

In this paper, a new GF(2m) multiplier for standard-basis representation is developed. The proposed multiplier implements the Mastrovito multiplication scheme and can be designed for every field GF(2m). A minimum-area implementation of the first block of Mastrovito multiplier and a high-speed delay-driven tree architecture for the second block of the Mastrovito multiplier are employed in the new circuit. Multiplier complexity and delay are analytically evaluated for many polynomial classes. Timing and area occupation performances of the proposed multiplier are also calculated for many fields used in Reed-Solomon codes applications and compared with those of previously proposed solutions. The comparison shows that the proposed multiplier outperforms previous architectures for every considered GF(2m) field. The effectiveness of the proposed solution in a real application is verified by implementing in a 0.25 mum CMOS technology the key equation solving block of a (255, 239) Reed-Solomon decoder. The use of the proposed multiplier in this application results in a substantial speed improvement without any penalty in the silicon area occupation.

This paper presents a technique for representing multiple-output binary and word-level functions in GF(JV) (where N = pm, p is a prime number, and m is a nonzero positive integer) based on decision diagrams (DDs). The presented DD is canonical and can be made minimal with respect to a given variable order. The DD has been tested on benchmarks, including integer multiplier circuits, and the results show that it can produce better node compression (more than an order of magnitude in some cases) compared to shared binary DDs (BDDs). The benchmark results also reflect the effect of varying the input and output field sizes on the number of nodes. Methods of graph-based representation of characteristic and encoded characteristic functions in GF(iV) are also presented. Performance of the proposed representations has been studied in terms of average path lengths and the actual evaluation times with 50,000 randomly generated patterns on many benchmark circuits. All of these results reflect that the proposed technique can outperform existing techniques.

This paper presents the generalized theory and an efficient graph-based technique for the calculation and representation of coefficients of multivariate canonic polynomials over arbitrary finite fields in any polarity. The technique presented for computing coefficients is unlike polynomial interpolation or matrix-based techniques and takes into consideration efficient graph-based forms which can be available as an existing resource during synthesis, verification, or simulation of digital systems. Techniques for optimization of the graph-based forms for representing the coefficients are also presented. The efficiency of the algorithm increases for larger fields. As a test case, the proposed technique has been applied to benchmark circuits over GF(2m). The experimental results show that the proposed technique can significantly speed up execution time.