Systolic implementation of multiplication over GF(2m) is usually very efficient in area-time complexity,but its latency is usually very large.Thus,two low latency systolic multipliers over GF(2m) based on general irre...Systolic implementation of multiplication over GF(2m) is usually very efficient in area-time complexity,but its latency is usually very large.Thus,two low latency systolic multipliers over GF(2m) based on general irreducible polynomials and irreducible pentanomials are presented.First,a signal flow graph(SFG) is used to represent the algorithm for multiplication over GF(2m).Then,the two low latency systolic structures for multiplications over GF(2m) based on general irreducible polynomials and pentanomials are presented from the SFG by suitable cut-set retiming,respectively.Analysis indicates that the proposed two low latency designs involve at least one-third less area-delay product when compared with the existing designs,To the authors' knowledge,the time-complexity of the structures is the lowest found in literature for systolic GF(2m) multipliers based on general irreducible polynomials and pentanomials.The proposed low latency designs are regular and modular,and therefore they are suitable for many time critical applications.展开更多
The standard method to construct a finite field requires a primitive irreducible polynomial of a given degree. Therefore, it is difficult to apply for the construction of huge finite fields. To avoid this problem, we ...The standard method to construct a finite field requires a primitive irreducible polynomial of a given degree. Therefore, it is difficult to apply for the construction of huge finite fields. To avoid this problem, we propose a new method to construct huge finite fields with the characteristic p = 5 by using an Artin-Schreier tower. Utilizing the recursive basis of the Artin-Schreier tower, we define a nmltiplication algorithm The algorithm can explicitly calculate the multiplication of two elements on the top finite field of this tower, without any primitive element. We also define a linear recurrence equation as an application, which produces a sequence of numbers, and call the new pseudorandom number generator Abstract Syntax Tree （AST） for p = 5. The experircental results show that our new pseudorandom number generator can produce a sequence of numbers with a long period.展开更多
In this paper, we give the conception of implicit congruence and nonimplicit congruence in a unique factorization domain R and establish some structures of irreducible polynomials over R . A classical result, E...In this paper, we give the conception of implicit congruence and nonimplicit congruence in a unique factorization domain R and establish some structures of irreducible polynomials over R . A classical result, Eisenstein′s criterion, is generalized.展开更多
This paper presents a criterion for testing the irreducibility of a polynomial over an algebraicextension field.Using this criterion and the characteristic set method,the authors give a criterion fortesting whether ce...This paper presents a criterion for testing the irreducibility of a polynomial over an algebraicextension field.Using this criterion and the characteristic set method,the authors give a criterion fortesting whether certain difference ascending chains are strong irreducible,and as a consequence,whetherthe saturation ideals of these ascending chains are prime ideals.展开更多
The period of a monic polynomial over an arbitrary Galois ring GR(pe,d) is theoretically determined by using its classical factorization and Galois extensions of rings. For a polynomial f(x) the modulo p remainder of ...The period of a monic polynomial over an arbitrary Galois ring GR(pe,d) is theoretically determined by using its classical factorization and Galois extensions of rings. For a polynomial f(x) the modulo p remainder of which is a power of an irreducible polynomial over the residue field of the Galois ring, the period of f(x) is characterized by the periods of the irreducible polynomial and an associated polynomial of the form (x-1)m+pg(x). Further results on the periods of such associated polynomials are obtained, in particular, their periods are proved to achieve an upper bound value in most cases. As a consequence, the period of a monic polynomial over GR(pe,d) is equal to pe-1 times the period of its modulo p remainder polynomial with a probability close to 1, and an expression of this probability is given.展开更多
基金Project(61174132) supported by the National Natural Science Foundation of ChinaProject(09JJ6098) supported by the Natural Science Foundation of Hunan Province,China
文摘Systolic implementation of multiplication over GF(2m) is usually very efficient in area-time complexity,but its latency is usually very large.Thus,two low latency systolic multipliers over GF(2m) based on general irreducible polynomials and irreducible pentanomials are presented.First,a signal flow graph(SFG) is used to represent the algorithm for multiplication over GF(2m).Then,the two low latency systolic structures for multiplications over GF(2m) based on general irreducible polynomials and pentanomials are presented from the SFG by suitable cut-set retiming,respectively.Analysis indicates that the proposed two low latency designs involve at least one-third less area-delay product when compared with the existing designs,To the authors' knowledge,the time-complexity of the structures is the lowest found in literature for systolic GF(2m) multipliers based on general irreducible polynomials and pentanomials.The proposed low latency designs are regular and modular,and therefore they are suitable for many time critical applications.
基金supported by Overseas Scholars Research Fund of Heilongjiang Provinicial Education Department
文摘The standard method to construct a finite field requires a primitive irreducible polynomial of a given degree. Therefore, it is difficult to apply for the construction of huge finite fields. To avoid this problem, we propose a new method to construct huge finite fields with the characteristic p = 5 by using an Artin-Schreier tower. Utilizing the recursive basis of the Artin-Schreier tower, we define a nmltiplication algorithm The algorithm can explicitly calculate the multiplication of two elements on the top finite field of this tower, without any primitive element. We also define a linear recurrence equation as an application, which produces a sequence of numbers, and call the new pseudorandom number generator Abstract Syntax Tree （AST） for p = 5. The experircental results show that our new pseudorandom number generator can produce a sequence of numbers with a long period.
文摘In this paper, we give the conception of implicit congruence and nonimplicit congruence in a unique factorization domain R and establish some structures of irreducible polynomials over R . A classical result, Eisenstein′s criterion, is generalized.
基金supported by a National Key Basic Research Project of ChinaNSFC
文摘This paper presents a criterion for testing the irreducibility of a polynomial over an algebraicextension field.Using this criterion and the characteristic set method,the authors give a criterion fortesting whether certain difference ascending chains are strong irreducible,and as a consequence,whetherthe saturation ideals of these ascending chains are prime ideals.
基金National Natural Science Foundation of China (Grant Nos. 61070172 and 10990011)the Strategic Priority Research Program of Chinese Academy of Sciences (Grant No. XDA06010702)the State Key Laboratory of Information Security, Chinese Academy of Sciences
文摘The period of a monic polynomial over an arbitrary Galois ring GR(pe,d) is theoretically determined by using its classical factorization and Galois extensions of rings. For a polynomial f(x) the modulo p remainder of which is a power of an irreducible polynomial over the residue field of the Galois ring, the period of f(x) is characterized by the periods of the irreducible polynomial and an associated polynomial of the form (x-1)m+pg(x). Further results on the periods of such associated polynomials are obtained, in particular, their periods are proved to achieve an upper bound value in most cases. As a consequence, the period of a monic polynomial over GR(pe,d) is equal to pe-1 times the period of its modulo p remainder polynomial with a probability close to 1, and an expression of this probability is given.
