Search

We present three greedy strategies for finding primitive polynomials of large degree over GF(2). Maximal length cellular automata (CAs) are used as tools to generate the primitive polynomials. The proposed strategies greedily synthesize (linear) CAs of different sizes, which are almost always of maximal length. Since the characteristic polynomial of a maximal length cellular automaton is primitive, characteristic polynomials of the synthesized CAs are claimed as primitive.

Combinatorial t-designs have nice applications in coding theory, finite geometries and engineering areas. t-designs can be constructed from image sets of a fixed size of some special polynomials. This paper constructs t-designs from the quadratic polynomial $$x^{4}+x^{3}$$ over $$\mathrm {GF}(2^{n})$$ and determine their parameters. We yield 2- $$\left( 2^n,3\cdot 2^{n-2},3\cdot 2^{n-2}\left( 3\cdot 2^{n-2}-1 \right) \right) $$ designs for n even and 3- $$\left( 2^n,2^{n-1},2^{n-1}\left( 2^{n-2}-1 \right) \right) $$ designs for n odd.

Binary extension finite fields ${\mathrm{ GF}}(2^{m})$ have received prominent attention in the literature due to their application in many modern public-key cryptosystems and error-correcting codes. In particular, the inversion over ${\mathrm{ GF}}(2^{m})$ is crucial for current and postquantum cryptographic applications. Schemes such as Fermat’s little theorem (FLT) and the Itoh–Tsujii algorithm (ITA) have been studied to achieve better performance; however, this arithmetic operation is a complex, expensive, and time-consuming task that may require thousands of gates, increasing its vulnerability chance to natural defects. In this work, we propose efficient hardware architectures based on cyclic redundancy check (CRC) as error detection schemes for state-of-the-art finite field inversion over ${\mathrm{ GF}}(2^{m})$ for a polynomial basis. To verify the derivations of the formulations, software implementations are performed. Likewise, hardware implementations of the original finite field inversions with the proposed error detection schemes are performed over Xilinx field-programmable gate array (FPGA) verifying that the proposed schemes achieve high error coverage with acceptable overhead.

In this article, we present the design of a high-performance simplified elliptic curve integrated encryption scheme (S-ECIES) cryptoprocessor. The cryptoprocessor was designed using a Montgomery ladder scalar multiplier, which was implemented with three finite field multipliers to improve the computational time of the scalar multiplication ${kP}$ , and using random curves and Gaussian normal bases over GF(2163) and GF(2233). Also, considering the National Institute of Standards and Technology (NIST) recommendations, a true random number generator is implemented to generate a secret key $k$ , which is used during the encryption process. The S-ECIES cryptoprocessor was synthesized on field-programmable gate array (FPGA) Stratix IV EP4SGX230KF40C2, simulated in ModelSim, and verified in hardware using the DE4 board and SignalTap tool. According to the synthesis results, the scalar multiplication operation is performed in 5.31 and $8.77~\mu \text{s}$ for GF(2163) and GF(2233), respectively. Also, the encryption process is performed in 20.70 and $30.90~\mu \text{s}$ for GF(2163) and GF(2233), respectively, and the decryption process is calculated in 8.10 and $11.9~\mu \text{s}$ for GF(2163) and GF(2233), respectively. The consumption power for the S-ECIES is 921 and 935 mW for GF(2163) and GF(2233), respectively.

Let G be isomorphic to GL n ⁢ ( q ) {\mathrm{GL}_{n}(q)} , SL n ⁢ ( q ) {\mathrm{SL}_{n}(q)} , PGL n ⁢ ( q ) {\mathrm{PGL}_{n}(q)} or PSL n ⁢ ( q ) {\mathrm{PSL}_{n}(q)} , where q = 2 a {q=2^{a}} . If t is an involution lying in a G-conjugacy class X, then, for arbitrary n, we show that, as q becomes large, the proportion of elements of X which have odd order product with t tends to 1. Furthermore, for n at most 4, we give formulae for the number of elements in X which have odd order product with t, in terms of q.

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.

A custom hardware coprocessor is described to improve the efficiency of applications using arithmetic in the Galois field GF(2) and the extension fields GF( $2^{m}$ ). The evaluation of such processor enhancements requires a variety of test exercises based on GF(2) arithmetic. Various test procedures are presented, which leverage the properties of finite fields to exercise the GF(2) arithmetic coprocessor incorporated with a 32-bit field-programmable gate array (FPGA)-based soft processor (Nios II). Up to 60 times speed improvement was achieved in typical calculations using the coprocessor. Resume —Un coprocesseur personnalise a ete decrit pour ameliorer l’efficacite des applications utilisant l’arithmetique en extension de Galois GF(2) et l’extension de corps GF(2m). L’evaluation des ameliorations d’un tel processeur necessite une variete d’exercices tests qui se basent sur l’arithmetique de GF(2). De nombreux tests de procedures ont ete presentes, ils exploitent les proprietes des corps finis afin d’exercer le coprocesseur arithmetique GF(2). Ce dernier a ete incorpore sur une matrice de portes programmables par l’utilisateur (FPGA) a 32 bits en se basant sur un processeur embarque (Nios II). La vitesse des calculs a ete amelioree jusqu’a 60 fois en utilisant le processeur.

We give an elementary proof that by multiplication on left and right by affine permutations A, B ∈ AGL(3, 2) each permutation π : GF(2)3 → GF(2)3 may be reduced to one of the 4 permutations for which the 3 × 3-matrices consisting of the coefficients of quadratic terms of coordinate functions have as an invariant the rank, which is either 3, or 2, or 1, or 0, respectively. For comparison, we evaluate the number of classes of affine equivalence by the Pólya enumerative theory.

The algebraic operations with the dense matrices and blocks are bounding the scalability of block Lanczos–Montgomery method, that is used for the linear part in the RSA decomposition problem. This paper explores the possibility of implementation of the following algebraic operations over field $$\mathbb{F}_2$$ on GPU: (1) multiplication of two 64k × 64k matrices; (2) multiplication of two N × 64k blocks. For matrix multiplication, we consider two algorithms: (a) the “naive” algorithm; (b) the “fast” algorithm by 4 Russians. For block multiplication, we consider just the “naive” algorithm. It seems that by now this is the only work where BLAS acceleration over $$\mathbb{F}_2$$ are relatively successful accelerated on GPU.

During the past decade, elliptic curve cryptography (ECC) has been widely deployed in different scenarios as the main asymmetric cryptosystem due to its smaller key length and relatively higher speed compared with other asymmetric cryptosystems. The most critical operation in ECC computation is point multiplication. In some popular applications such as signature verification schemes, the double point multiplication can be exploited. In this paper, we propose an algorithm and its corresponding architecture to speed up the double point multiplication using a modified binary differential addition chain. The proposed method is highly parallelizable and has been implemented on Virtex-4, Virtex-5, and Virtex-7 over ${{GF}}(2^{163})$ , ${{GF}}(2^{233})$ , and ${{GF}}(2^{283})$ , respectively. Experimental results using hardware implementation on Virtex-4 indicate that the proposed architecture achieves 63% and 16% improvements compared with the previous double point multiplication implementation in terms of required time and efficiency over ${ {GF}}(2^{233})$ , respectively. Additionally, the proposed architecture shows time reduction compared with twice the execution time of the best previous single point multiplication by 39% while achieving 258% higher efficiency. The proposed architecture has also been implemented on ASIC, and the results show that the proposed work improves time and energy consumption compared with the previous work.

This paper presents how the steps that used to determine a multiplicative inverse by method based on the Euclidean algorithm, can be used to find a greatest common divisor for polynomials in the Galois field (2^n ).

The quasi-circular vegetation patches (QVPs) are better objects for studying the ecosystem evolution, functioning, and maintenance in the Yellow River Delta, China. Remote sensing with linear change detection technique is an effective approach for mapping the vegetation dynamics. In this paper, the multitemporal Kauth-Thomas transformation (MKT) change detection technique with the decision tree classifier was used to map the QVPs based on the modified intensity-hue-saturation pansharpened April and August Gaofen-2 images. Results indicated that mapping the QVPs could be performed well using the approaches used in this paper. The precision, recall rate, and F-measure were 66.7%, 52.9%, and 59.0%, respectively. In the future, patch splitting techniques and more test areas should be tested for improving the detection accuracy of the QVPs. In addition, an assessment on the possibility of change in brightness and greenness between multitemporal images for mapping the dominant communities of the QVPs should be performed, which were important for the establishment, evolution, and disappearance of the QVPs.

In this paper, we propose a class of binary sequences induced by monomial permutation polynomials over \(\mathrm {GF}(2^{p})\) and study the period property and the shift-equivalence of these binary sequences. In particularly, we give a necessary and sufficient condition for such a sequence to have maximal period. Moreover, we also give a necessary and sufficient condition for two such sequences to be shift equivalent.

In this article, a new architecture of bit-serial polynomial basis (PB) multipliers over the binary extension field $GF(2^m)$ G F ( 2 m ) generated by irreducible trinomials is presented. Bit-serial $GF(2^m)$ G F ( 2 m ) PB multiplication offers a performance/area trade-off that is very useful in resource constrained applications. The architecture here proposed is based on LFSR ( Linear-Feedback Shift Register ) and can perform a multiplication in $m$ m clock cycles with a constant propagation delay of $T_{A} + T_{X}$ T A + T X . These values match the best time results found in the literature for bit-serial PB multipliers with a slight reduction of the space complexity. Furthermore, the proposed architecture can perform the multiplication of two operands for $t$ t different finite fields $GF(2^m)$ G F ( 2 m ) generated by $t$ t irreducible trinomials simultaneously in $m$ m clock cycles with the inclusion of $t(m-1)$ t ( m - 1 ) flipflops and $tm$ t m XOR gates.

Gaofen 2 (GF-2) high spatial resolution imagery has been recognized as an important data source for mapping vegetation pattern dynamics. The Kauth-Thomas (KT) indices of brightness, greenness, and wetness derived from single-date imagery has also been proved to be better than the common vegetation indices in monitoring the vegetation, mapping land desertification, and classifying land covers. However, for change detection of vegetation status, multitemporal Kauth-Thomas (MKT) transformation is found to be a more effective approach. In this paper, the parameters defining the KT dimensions for single-date mIHS pansharpeniing GF-2 data (acquired on April 30, 2016) were derived. Then, the MKT transformation matrix was proposed using a linear transformation process, which could be applied to GF-2 digital number image data for detecting vegetation pattern dynamics in the future.

At SODA 2017 Lokshtanov et al. presented the first worst-case algorithms with exponential speedup over exhaustive search for solving polynomial equation systems of degree d in n variables over finite fields. These algorithms were based on the polynomial method in circuit complexity which is a technique for proving circuit lower bounds that has recently been applied in algorithm design. Subsequent works further improved the asymptotic complexity of polynomial method-based algorithms for solving equations over the field \(\mathbb {F}_2\). However, the asymptotic complexity formulas of these algorithms hide significant low-order terms, and hence they outperform exhaustive search only for very large values of n.

GF(2)-grammars are a recently introduced grammar family that has some unusual algebraic properties and is closely connected to the family of unambiguous grammars. By using the method of formal power series, we establish strong conditions that are necessary for subsets of \(a_1^* a_2^* \cdots a_k^*\) to be described by some GF(2)-grammar. By further applying the established results, we settle the long-standing open question of proving the inherent ambiguity of the language \(\{ \, a^n b^m c^\ell \mid n \ne m \text { or } m \ne \ell \, \}\), as well as give a new, purely algebraic, proof of the inherent ambiguity of the language \(\{ \, a^n b^m c^\ell \mid n = m \text { or } m = \ell \, \}\).

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.

The paper investigates the state complexity of two operations on regular languages, known as GF(2)-concatenation and GF(2)-inverse (Bakinova et al., “Formal languages over GF(2)”, LATA 2018), in the case of a one-symbol alphabet. The GF(2)-concatenation is a variant of the classical concatenation obtained by replacing Boolean logic in its definition with the GF(2) field; it is proved that GF(2)-concatenation of two unary languages recognized by an m-state and an n-state DFA is recognized by a DFA with 2 m n states, and this number of states is necessary in the worst case, as long as m and n are relatively prime. This operation is known to have an inverse, and the state complexity of the GF(2)-inverse operation over a unary alphabet is proved to be exactly 2 n − 1 + 1 , with the proof based on primitive polynomials over GF(2). For a generalization of the GF(2)-inverse, called the GF(2)-star, the state complexity in the unary case is exactly 2 n .

Variants of the union and concatenation operations on formal languages are investigated, in which Boolean logic in the definitions (that is, conjunction and disjunction) is replaced with the operations in the two-element field GF(2) (conjunction and exclusive OR). Union is thus replaced with symmetric difference, whereas concatenation gives rise to a new GF(2)-concatenation operation, which is notable for being invertible. All operations preserve regularity, and for a pair of languages recognized by an m-state and an n-state DFA, their GF(2)-concatenation is recognized by a DFA with m ⋅ 2 n states, and this number of states is in the worst case necessary. Similarly, the state complexity of GF(2)-inverse is 2 n + 1 . Next, a new class of formal grammars based on GF(2)-operations is defined, and it is shown to have the same computational complexity as ordinary grammars with union and concatenation: in particular, simple parsing in time O ( n 3 ) , fast parsing in the time of matrix multiplication, and parsing in NC2.

Systolic finite field multiplier over $\textit {GF}(2^{m})$ based on the National Institute of Standards and Technology (NIST) recommended pentanomials or trinomials can be used as a critical component in many cryptosystems. In this paper, for the first time, we propose a novel low-complexity unified (hybrid field size) systolic multiplier for NIST pentanomials and trinomials over $\textit {GF}(2^{m})$ . We have proposed a computation-core-based design strategy to obtain the desired low-complexity unified multiplier for both NIST pentanomials and trinomials. The proposed multiplier can swift between pentanomial-based and trinomial-based multipliers through a control signal. First of all, a novel strategy is briefly introduced to implement a certain matrix-vector multiplication, which can be packed as a standard computation core (or computation core like). Then, based on the computation-core concept, a novel unified multiplication algorithm is derived that it can realize both the pentanomial-based and trinomial-based multiplications. After that, an efficient systolic structure is presented that it can fully employ the introduced computation core. A detailed example of the proposed unified multiplier (for $\textit {GF}(2^{163})$ and $\textit {GF}(2^{233})$ ) is also presented. Both the theoretical and field-programmable gate array implementation results show that the proposed design has efficient performance in area-time-power complexities, e.g., the proposed design (the one performs $\textit {GF}(2^{163})$ and $\textit {GF}(2^{233})$ multiplications) is found to have at least 14.2% and 13.3% less area-delay product and power-delay product than the combination of the existing individual $\textit {GF}(2^{163})$ and $\textit {GF}(2^{233})$ multipliers (best among all competing designs), respectively. Because of its structural regularity and functional flexibility, the proposed unified multiplier can be used as an intellectual property core for various cryptosystems.

This paper proposes a compact and highly efficient $$\textit{GF}(2^8)$$ inversion circuit design based on a combination of non-redundant and redundant Galois field (GF) (or finite field) arithmetic. The proposed design utilizes an optimal normal basis and redundant GF representations, called polynomial ring representation and redundantly represented basis, to implement $$\textit{GF}(2^8)$$ inversion using a tower field $$\textit{GF}((2^4)^2)$$ . The flexibility of the redundant representations provides efficient mappings from/to the $$\textit{GF}(2^8)$$ . This paper evaluates the efficacy of the proposed circuit by gate counts and logic synthesis with a 65-nm CMOS standard cell library in comparison with conventional circuits. Consequently, we show that the proposed circuit achieves approximately 25% higher area–time efficiency than the conventional best inversion circuit in our environment. We also demonstrate that AES S-Box with the proposed circuit achieves the best area–time efficiency.

In recent years, subquadratric-and-quadratric Toeplitz matrix–vector product (TMVP) computations are widely used for the implementation of binary field multiplication in elliptic curve cryptography. Pure subquadratric TMVP structure involves significantly less space complexity and long computational delay, while quadratric TMVP structure involves larger space complexity and less computation delay. To optimise the tradeoff between time and space complexities, this study presents a novel hybrid multiplier for Gaussian normal basis (GNB) in GF(2 m ) which combines subquadratic and quadratic structures. From the theoretical analysis, it is shown that the proposed hybrid multiplier can save ∼18% space complexity and 12% time complexity than the existing GNB multiplier with pure TMVP decomposition.

Galois field (GF) multipliers play a major role in the engineering applications such as cryptography and error correcting codes. This paper proposes systolic vector m-bit GF(p) and GF ( 2 m ) multipliers ( m = log 2 p ), where four numbers of m 2 -bit GF multiplications can be done in parallel. Similarly, twelve and sixteen numbers of GF ( 2 m 4 ) and m 4 -bit GF(p) multiplications can be done in parallel respectively. Also, this paper proposes non vector flexible GF ( 2 m ) and m-bit GF(p) multipliers, where the m can be varied from 2 to the maximum allowable value. Our proposed systolic vector parallel GF ( 2 16 ) multiplier achieves 95.8% of improvement in throughput over reconfigurable bit serial design [7] . Similarly, the proposed systolic vector parallel 16-bit GF(p) multiplier achieves 82.5% of improvement in throughput over reconfigurable bit serial design [23] using 45 nm CMOS technology.

In this paper, we propose two new algorithms and their hardware implementations for the normal basis multiplication over GF( $p^{m}$ ), where $p \in \{2, 3\}$ . In this case, the proposed multipliers are designed using serial and digit-serial hardware architectures. The normal basis multipliers over GF( $2^{m}$ ) and GF( $3^{m}$ ) are based on two proposed algorithms to compute the multiplication matrices $T_{k}$ in order to speed-up the execution time and to reduce the area resources. It can be seen that the new hardware architecture for the NB multiplier over GF( $2^{m}$ ) has the best characteristics of area complexity presented by Reyhani [16] and time complexity presented by Azarderakhsh and Reyhani [31] . The proposed hardware architectures for the normal basis multipliers over GF(2163), GF(2233), GF(2283),GF(2409), GF(389) and GF(3233) were described in VHDL, and simulated and synthesized using Modelsim and Quartus Prime v16, respectively.

In this study high-performance and high-speed field-programmable gate array (FPGA) implementations of polynomial basis Itoh–Tsujii inversion algorithm (ITA) over GF(2 m ) constructed by irreducible trinomials and pentanomials are presented. The proposed structures are designed by one field multiplier and k -times squarer blocks or exponentiation by 2 k , where k is a small positive integer. The k -times squarer blocks have an efficient tree structure with low critical path delay, and the multiplier is based on a proposed high-speed digit-serial architecture with minimum hardware resources. Furthermore, to reduce the computation time of ITA, the critical path of the circuit is broken to finer path using several registers. The computation times of the structure on Virtex-4 FPGA family are 0.262, 0.192 and 0.271 µs for GF(2163), GF(2193) and GF(2233), respectively. The comparison results with other implementations of the polynomial basis Itoh–Tsujii inversion algorithm verify the improvement in the proposed architecture in terms of speed and performance.

Many important graphs are bipartite and cubic (i.e. bipartite and trivalent, or “bicubic”). We explain concisely how the Hamilton cycles of this type of graph are characterized by a single determinantal condition over GF ( 2 ) . Thus algebra may be used to derive results such as those of Bosak, Kotzig, and Tutte that were originally proved differently.

In this paper, an efficient high-speed architecture of Gaussian normal basis (GNB) multiplierover binary finite field GF(2 m ) is presented. The structure is constructed by using some regular modules for computation of exponentiation by powers of 2 and low-cost blocks for multiplication by normal elements of the binary field. For the powers of 2 exponents, the modules are implemented by some simple cyclic shifts in the normal basis representation. As a result, the multiplier has a simple structure with a low critical path delay. The efficiency of the proposed multiplier is examined in terms of area and time complexity based on its implementation on Virtex-4 field programmable gate array family and also its application specific integrated circuit design in 180 nm complementary metal-oxide-semiconductor technology. Comparison results with other structures of the GNB multiplier verify that the proposed architecture has better performance in terms of speed and hardware utilisation.

Systolic all-one-polynomial (AOP) multipliers usually suffer from the problem of high register complexity, especially in field-programmable gate array (FPGA) platforms where the register resources are not that abundant. In this paper, we have shown that the AOP-based systolic multipliers can easily achieve low register-complexity implementations and the proposed architectures can be employed as computation cores to derive efficient implementations of systolic Montgomery multipliers based on trinomials. First, we propose a novel data broadcasting scheme in which the register complexity involved within existing AOP-based systolic multipliers is significantly reduced. We have found out that the modified AOP-based structure can be packed as a standard computation core. Next, we propose a novel Montgomery multiplication algorithm that can fully employ the proposed AOP-based computation core. The proposed Montgomery algorithm employs a novel precomputed-modular operation, and the systolic structures based on this algorithm fully inherit the advantages brought from the AOP-based core (low register complexity, low critical-path delay, and low latency) except some marginal hardware overhead brought by a precomputation unit. The proposed architectures are then implemented by Xilinx ISE 14.1 and it is shown that compared with the existing designs, the proposed designs achieve at least 61.8% and 47.6% less area-delay product and power-delay product than the best of competing designs, respectively.

RSA algorithm is one of the most popular and secure public key cryptographic algorithms and has been widely used in many real-life applications. The security of the RSA algorithm lies in the difficulty of factoring large integers efficiently and the General Number Field Sieve (GNFS) algorithm is the most efficient algorithm for factoring integers greater than 110 digits at present. In this paper, targeted to speed up the factorization process of RSA, we discuss the current research about solving large and sparse linear systems over GF(2), which is one of the most time-consuming steps of the GNFS algorithm. With that, we propose an improved parallel block Lanczos (IBL) algorithm to reduce the communication cost of solving large and sparse linear systems over GF(2). More specifically, we firstly re-implement the parallel block Lanczos algorithm from the BSP paradigm to Open MPI. To further improve the performance, we then reorganize and redesign the algorithm to reduce the synchronization and communication costs during the outer product step. After this, we integrate the improved parallel block Lanczos algorithm with the GNFS algorithm. Finally, theoretical and experimental results demonstrate that the IBL algorithm greatly enhances the performance of GNFS compared with previous parallel block Lanczos (PBL) algorithm, in terms of both execution time and speedup.

In this paper, we have shown that a regular Toeplitz matrix-vector product (TMVP) can be transformed into a Toeplitz block TMVP (TBTMVP) using a suitable permutation matrix. Based on the TBTMVP representation, we have proposed a new $(a,b)$ -way TBTMVP decomposition algorithm for implementing a digit-serial multiplication. Moreover, it is shown that, based on iterative block recombination, we can improve the space complexity of the proposed TBTMVP decomposition. From the synthesis results, we have shown that the proposed TBTMVP-based multiplier involves less area, less area-delay product, and higher throughput compared with the existing digit-serial multipliers.

Digit-serial finite field multipliers over GF($2^{m}$) with subquadratic space complexity are critical components to many applications such as elliptic curve cryptography. In this paper, we propose a pair of novel digit-serial multipliers based on bivariate polynomial basis (BPB). Firstly, we have proposed a novel digit-serial BPB multiplication algorithm based on a new decomposition strategy. Secondly, the proposed algorithm is properly mapped into a pair of pipelined and non-pipelined digit-serial multipliers. Lastly, through the detailed complexity analysis and comparison, the proposed designs are found to have less area-time complexities than the competing ones.

Let V be a finite-dimensional vector space over a finite field and let f be a trilinear alternating form over V. For such forms, we introduce two new invariants. Together with a generalized radical polynomial used for classification of forms in dimension 8 over GF(2), they are sufficient to distinguish between all trilinear alternating forms in dimension 9 over GF(2). To prove the completeness of the list of forms, we computed their groups of automorphisms. There are 31 degenerate and 317 nondegenerate forms. We point out some forms with either small or large automorphism group.

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.

This paper proposes an efficient pipelined architecture of elliptic curve scalar multiplication (ECSM) over GF( ${2}^{m}$ ). The architecture uses a bit-parallel finite-field (FF) multiplier accumulator (MAC) based on the Karatsuba-Ofman algorithm. The Montgomery ladder algorithm is modified for better sharing of execution paths. The data path in the architecture is well designed, so that the critical path contains few extra logic primitives apart from the FF MAC. In order to find the optimal number of pipeline stages, scheduling schemes with different pipeline stages are proposed and the ideal placement of pipeline registers is thoroughly analyzed. We implement ECSM over the five binary fields recommended by the National Institute of Standard and Technology on Xilinx Virtex-4 and Virtex-5 field-programmable gate arrays. The three-stage pipelined architecture is shown to have the best performance, which achieves a scalar multiplication over GF( ${2^{163}}$ ) in 6.1 $\mu \text{s}$ using 7354 Slices on Virtex-4. Using Virtex-5, the scalar multiplication for ${m} = 163$ , 233, 283, 409, and 571 can be achieved in 4.6, 7.9, 10.9, 19.4, and 36.5 $\mu \text{s}$ , respectively, which are faster than previous results.

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.

Toeplitz matrix–vector product (TMVP) decomposition is an important approach for designing and implementing subquadratic multiplier. In this Letter, a symmetric matrix (SM), which is the sum of a symmetric TM and Hankel matrix, is proposed. Applying the symmetry property, 2-way, 3-way and n-way splitting methods of SMVP is presented. On the basis of 2-way splitting method, the recursive formula of SMVP is presented. Using the two cases n = 4 and 8, the SMVP decomposition approach has less space complexity than 2-way TMVP, TMVP block recombination and symmetric TMVP for even-type Gaussian normal basis multiplication.

A famous conjecture about group algebras of torsion-free groups states that there is no zero divisor in such group algebras. A recent approach to settle the conjecture is to show the non-existence of zero divisors with respect to the length of possible ones, where by the length we mean the size of the support of an element of the group algebra. The case length $2$ cannot be happen. The first unsettled case is the existence of zero divisors of length $3$. Here we study possible length $3$ zero divisors in rational group algebras and in the group algebras over the field with $p$ elements for some prime $p$.

The paper investigates the state complexity of two operations on regular languages, known as GF(2)-concatenation and GF(2)-inverse (Bakinova et al., “Formal languages over GF(2)”, LATA 2018), in the case of a one-symbol alphabet. The GF(2)-concatenation is a variant of the classical concatenation obtained by replacing Boolean logic in its definition with the GF(2) field; it is proved that GF(2)-concatenation of two unary languages recognized by an m-state and an n-state DFA is recognized by a DFA with 2mn states, and this number of states is necessary in the worst case, as long as m and n are relatively prime. This operation is known to have an inverse, and the state complexity of the GF(2)-inverse operation over a unary alphabet is proved to be exactly \(2^{n-1}+1\).

GF(2)-grammars, recently introduced by Bakinova et al. (“Formal languages over GF(2)”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: \(K \odot L\) is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form \(\{a^n b^{f(n)} \,\mid \, n \geqslant 1\}\), with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.

In this paper, we study the construction of diffusion matrices with suitable symmetric properties for cryptographic applications. The most famous example of diffusion matrices with symmetries are the circulant ones. In this paper, we focus on the less known dyadic family. Considering the link between optimal diffusion matrices and MDS codes, we use a coding theory approach based on additive codes over \(\textit{GF}(2)^m\). With this method, we could build diffusion matrices not only derived from a finite field but derived from the whole linear group \(\textit{GL}(m,2)\). We present some theoretical and experimental results, particularly efficient in the context of hardware implementation.

Substitution Box or S-Box had been generated using 4-bit Boolean Functions (BFs) for Encryption and Decryption Algorithm of Lucifer and Data Encryption Standard (DES) in late sixties and late seventies respectively. The S-Box of Advance Encryption Standard have also been generated using Irreducible Polynomials over Galois field GF(28) adding an additive constant in early twenty first century. In this chapter Substitution Boxes have been generated from Irreducible or Reducible Polynomials over Galois field GF(pq). Binary Galois fields have been used to generate Substitution Boxes. Since the Galois Field Number or the Number generated from coefficients of a polynomial over a particular Binary Galois field (2q) is similar to log2q + 1 bit BFs. So generation of log2q + 1 bit S-Boxes is possible. Now if p = prime or non-prime number then generation of S-Boxes is possible using Galois field GF (pq), where, q = p − 1.

In this work, we construct a compact composite AES S-Box by deriving a new low multiplicative complexity GF (24) inversion circuit. A deterministic tree search algorithm is applied to search for constructions that are optimum in terms of multiplicative complexity. From the results, the circuit with the smallest gate count is selected for GF (24) inversion. To the best of our knowledge, the proposed AES S-Box requires the smallest gate count to date with the size of 112 gates and depth of 25 gates.