Montgomery Multiplication in GF(2k)

We show that the multiplication operation c=a · b · r^-1 in the field GF(2^k can be implemented significantly faster in software than the standard multiplication, where r is a special fixed element of the field. This operation is the finite field analogue of the Montgomery multiplication for modular multiplication of integers. We give the bit-level and word-level algorithms for computing the product, perform a thorough performance analysis, and compare the algorithm to the standard multiplication algorithm in GF(2^k. The Montgomery multiplication can be used to obtain fast software implementations of the discrete exponentiation operation, and is particularly suitable for cryptographic applications where k is large.     

Polynomial Basis Multiplication over GF(2 m )

In this paper, we describe, analyze and compare various multipliers. Particularly, we investigate the standard modular multiplication, the Montgomery multiplication, and the matrix–vector multiplication techniques.     

Bit-Parallel Arithmetic Implementations over Finite Fields GF(2 m ) with Reconfigurable Hardware

Galois (or finite) fields are used in a wide number of technical applications, playing an important role in several areas such as cryptographic schemes and algebraic codes, used in modern digital communication systems. Finite field arithmetic must be fast, due to the increasing performance needed by communication systems, so it might be necessary for the implementation of the modules performing arithmetic over Galois fields on semiconductor integrated circuits. Galois field multiplication is the most costly arithmetic operation and different approaches can be used. In this paper, the fundamentals of Galois fields are reviewed and multiplication of finite-field elements using three different representation bases are considered. These three multipliers have been implemented using a bit-parallel architecture over reconfigurable hardware and experimental results are presented to compare the performance of these multipliers.     

Scalable and Systolic Architecture for Computing Double Exponentiation Over GF(2 m )

Double-exponentiation is a crucial arithmetic operation for many cryptographic protocols. Several efficient double-exponentiation algorithms based on systolic architecture have been proposed. However, systolic architectures require large circuit space, thus increasing the cost of the protocol. This would be a drawback when designing circuits in systems requiring low cost and low power consumption. However, some cost savings can be attained by compromising speed, as in portable devices and many embedded systems. This study proposes a scalable and systolic AB ² and a scalable and systolic A × B, which are the core circuit modules of double-exponentiation. A scalable and systolic double-exponentiation can thus be obtained based on the proposed scalable AB ² and A × B architecture. Embedded system engineers may specify a target double-exponentiation with appropriate scaling systolic circuits. The proposed circuit has lower circuit space/cost and low time/propagation than other circuits.     

Fast algorithms for determining the linear complexities of sequences over GF(p~m) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p-1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(pm)(any positive integer m) with the period 3n (n and pm - 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-lmamura algorithm, we can determine the linear complexity of any sequence over GF(pm) with the period 3n (n and pm - 1 are coprime) more efficiently.     

Construction of pseudorandom binary sequences using additive characters over GF(2 k )

In a series of papers Mauduit and Sárközy (partly with coauthors) studied finite pseudorandom binary sequences and they constructed sequences with strong pseudorandom properties. In these constructions fields with prime order were used. In this paper a new construction is presented, which is based on finite fields of order 2 ^k .     

算术级数中的奇数Goldbach问题(Ⅱ)

本文考察了几乎所有模的算术级数中的奇数Goldbach问题．证明了对几乎所有的模r≤N1/6-ε,充分大的正奇数N可表为三个素数之和,其中每个素数取在模r 的满足必要同余条件的任意剩余系中．     

On the Complexity of Parallel Algorithms for Computing Inverses in GF(2^m) with m Prime

Inversion over a finite field is usually an expensive operation which is a crucial issue in many applications, such as cryptography and error-control codes. In this paper, three different strategies for computing the inverse over binary finite fields , called Eulerian, Gaussian, and Euclidean, respectively, are discussed and compared in terms of time and space complexity. In particular, some new upper and lower bounds to the respective complexities are evaluated.     

GF(2)上本原多项式的三项倍式的次数研究

研究了二元域上本原多项式的三项倍式的计数问题,通过对三项倍式进行分类,导出了本原多项式三项倍式最低次数的一个上界.利用这一结果,使构造本原多项式的次数最低的三项倍式的计算复杂性降到原来的九分之一.     

Efficient parallel exponentiation in using normal basis representations

Von zur Gathen proposed an efficient parallel exponentiation algorithm in finite fields using normal basis representations. In this paper we present a processor-efficient parallel exponentiation algorithm in GF(qⁿ) which improves upon von zur Gathen's algorithm. We also show that exponentiation in GF(qⁿ) can be done in O((log₂n)²/log_qn) time using n/(log₂n)² processors. Hence we get a processor-time bound of O(n/log_qn), which matches the best known sequential algorithm. Finally, we present an efficient on-line processor assignment scheme which was missing in von zur Gathen's algorithm.     

Fast algorithms for determining the linear complexities of sequences over GF(pm) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p − 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m − 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m − 1 are coprime) more efficiently.     

Sn+1中M(o)ebius形式平行的超曲面

如果x:M→Sn+1是不含脐点的超曲面,且M的Moebius形式 =0和Blaschke张量A=λg,就称M为Moebius迷向超曲面,如果x:M→Sn+1 是不合脐点的超曲面,且M的Moebius形式 平行( =0)和Blaschke张量A=λg,就称M为Moebius拟迷向超曲面,这里g是M上的Moebius度量,λ:M→R是M上的光滑函数,本文证明了如下结果: (1)设x:M→Sn+1(n 3)是不含脐点的超曲面,则M是拟迷向超曲面当且仅当M是迷向超曲面,(2)设x:M→Sn+1(n 3)是不合脐点的超曲面,且M的Moebius形式 平行和Blaschke张量A也平行( A=0),则 =0.     

psl(2|2) 非线性α -模型超对称性质研究

由$\widehat{psl(2|2)^{(2)}}_{k}$非线性$\sigma$ -模型加上WZ -项得到的WZW模型是共形场论,它具有李超代数$psl(2|2)$对称性.该文用向量相干态方法给出了李超代数$psl(2|2)$的微分算子表示.并在此基础上给出了扭曲Kac-Moody李超代数 $\widehat{psl(2|2)^{(2)}}_{k}$自由场实现,相应共形场论的中心荷为$-2$.