US6038581A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Scheme for arithmetic operations in finite field and group operations over elliptic curves realizing improved computational speed
Assignee: NTT Inc
•
Filing: 1998-01-28
•
Granted: 2000-03-14
•
Expires: 2018-01-28
Abstract
Abstract A scheme for arithmetic operations in finite field and group operations over elliptic curves capable of realizing a very fast implementation. According to this scheme, by using a normal basis [ alpha alpha +1], the multiplicative inverse calculation and the multiplication in the finite field GF(22n) can be realized as combinations of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2n). Also, by using a standard basis [1 alpha ], the multiplication, the square calculation, and the multiplicative inverse calculation in the finite field GF(22n) can be realized as combinations of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2n). These arithmetic operations can be utilized for calculating rational expressions expressing group operations over elliptic curves that are used in information security techniques such as elliptic curve cryptosystems.
Inventors
- 👤 Kazumaro Aoki
- 👤 Kazuo Ohta
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 21:35
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/725; G06F7/726
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
133 words
A method for calculating a multiplicative inverse in finite field GF(2 2n ), comprising the steps of: expressing an element m.di-elect cons.GF(2 2n ) as m=xα+y(α+1)(x,y.di-elect cons.GF(2.sup.n)) where α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(a(x+y).sup.2 +xy).sup.-1 yα+(a(x+y).sup.2 +xy).sup.-1 x(α+1) by combining a normal basis [α α+1] with extended Euclidean algorithm; and calculating the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 2
Independent Claim
133 words
A method for calculating a multiplicative inverse in finite field GF(2 2n ), comprising the steps of: expressing an element m.di-elect cons.GF(2 2n ) as m=xα+y(α+1)(x,y.di-elect cons.GF(2.sup.n)) where α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(a(x+y).sup.2 +xy).sup.-1 yα+(a(x+y).sup.2 +xy).sup.-1 x(α+1) by combining a normal basis [α α+1] with extended Euclidean algorithm; and calculating the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 3
Dependent Claim
71 words
The method of claim 1, wherein the calculating step calculates a multiplicative inverse x -1 of an element X.di-elect cons.GF(2 n ) by: obtaining e=log g x by looking up a logarithmic conversion table provided in advance, where g is a primitive element in the subfield GF(2 n ); calculating f=-e mod (2 n -1); and obtaining x -1 =g f by looking up an exponential conversion table provided in advance.
Claim 4
Dependent Claim
59 words
The method of claim 1, wherein the calculating step converts a multiplication in the subfield GF(2 n ) into an addition in additive cyclic group Z/(2 n -1)Z that can be calculated by logarithmic conversion, and re-converts calculation result of the addition in the additive cyclic group Z/(2 n -1l)Z into the subfield GF(2 n ) by exponential conversion.
Claim 5
Dependent Claim
54 words
The method of claim 1, further comprising the step of: storing calculation results of multiplications in subfield GF(2 n ) into a fast read accessible memory as a multiplication table in advance, so that the calculating step obtains calculation results of multiplications in the subfield GF(2 n ) by looking up the multiplication table.
Claim 6
Dependent Claim
65 words
The method of claim 1, further comprising the step of: storing calculation results of multiplications in subfield GF(2 n ) for cases where one number to be multiplied is a constant into a memory as a multiplication table in advance, so that the calculating step obtains calculation results of multiplications in the subfield GF(2 n ) for said cases by looking up the multiplication table.
Claim 7
Dependent Claim
30 words
The method of claim 1, wherein the calculating step reduces multiplications in the subfield GF(2 n ) into multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n/2 ).
Claim 8
Dependent Claim
70 words
The method of claim 1, wherein the calculating step calculates a multiplication using one element in the subfield GF(2 n ) by looking up a logarithmic conversion table provided in advance, stores a logarithm corresponding to said one element obtained from the logarithmic conversion table, and calculates a subsequent multiplication using said one element by using stored logarithm corresponding to said one element without looking up the logarithmic conversion table.
Claim 9
Independent Claim
135 words
A method for calculating a multiplication in finite field GF(2 2n ), comprising the steps of: reducing a multiplication of two elements m 1 and m 2 in GF(2 2n ) into multiplications and additions in subfield GF(2 n ) by expressing m 1 , m 2 .di-elect cons.GF(2 2n ) as m.sub.1 =x.sub.1 α+y.sub.1 (α+1), m.sub.2 =x.sub.2 α+y.sub.2 (α+1) where x i , y i .di-elect cons.GF(2 n ), i=1, 2, α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 0 of m 1 , m 2 .di-elect cons.GF(2 2n ) is given by m.sub.0 =m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))α+(y.sub.1 y.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))(α+1); and calculating the multiplication m 0 by executing said multiplications and additions in the subfield GF(2 n ).
Claim 10
Independent Claim
135 words
A method for calculating a multiplication in finite field GF(2 2n ), comprising the steps of: reducing a multiplication of two elements m 1 and m 2 in GF(2 2n ) into multiplications and additions in subfield GF(2 n ) by expressing m 1 , m 2 .di-elect cons.GF(2 2n ) as m.sub.1 =x.sub.1 α+y.sub.1 (α+1), m.sub.2 =x.sub.2 α+y.sub.2 (α+1) where x i , y i .di-elect cons.GF(2 n ), i=1, 2, α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 0 of m 1 , m 2 .di-elect cons.GF(2 2n ) is given by m.sub.0 =m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))α+(y.sub.1 y.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))(α+1); and calculating the multiplication m 0 by executing said multiplications and additions in the subfield GF(2 n ).
Claim 11
Independent Claim
138 words
A device for calculating a multiplicative inverse in finite field GF(2 2n ), comprising: an input unit for expressing an element m.di-elect cons.GF(2 2n ) as m=xα+y(α+1)(x,y.di-elect cons.GF(2.sup.n)) where α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(a(x+y).sup.2 +xy).sup.-1 yα+(a(x+y).sup.2 +xy).sup.-1 x(α+1) by combining a normal basis [α α+1] with extended Euclidean algorithm; and a calculation unit for calculating the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 12
Independent Claim
138 words
A device for calculating a multiplicative inverse in finite field GF(2 2n ), comprising: an input unit for expressing an element m.di-elect cons.GF(2 2n ) as m=xα+y(α+1)(x,y.di-elect cons.GF(2.sup.n)) where α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(a(x+y).sup.2 +xy).sup.-1 yα+(a(x+y).sup.2 +xy).sup.-1 x(α+1) by combining a normal basis [α α+1] with extended Euclidean algorithm; and a calculation unit for calculating the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 13
Independent Claim
140 words
A device for calculating a multiplication in finite field GF(2 2n ), comprising: an input unit for reducing a multiplication of two elements m 1 and m 2 in GF(2 2n ) into multiplications and additions in subfield GF(2 n ) by expressing m 1 , m 2 .di-elect cons.GF(2 2n ) as m.sub.1 =x.sub.1 α+y.sub.1 (α+1), m.sub.2 =x.sub.2 α+y.sub.2 (α+1) where x i , y i .di-elect cons.GF(2 n ), i=1, 2, α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 0 of m 1 , m 2 .di-elect cons.GF(2 2n ) is given by m.sub.0 =m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))α+(y.sub.1 y.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))(α+1); and a calculation unit for calculating the multiplication m 0 by executing said multiplications and additions in the subfield GF(2 n ).
Claim 14
Independent Claim
140 words
A device for calculating a multiplication in finite field GF(2 2n ), comprising: an input unit for reducing a multiplication of two elements m 1 and m 2 in GF(2 2n ) into multiplications and additions in subfield GF(2 n ) by expressing m 1 , m 2 .di-elect cons.GF(2 2n ) as m.sub.1 =x.sub.1 α+y.sub.1 (α+1), m.sub.2 =x.sub.2 α+y.sub.2 (α+1) where x i , y i .di-elect cons.GF(2 n ), i=1, 2, α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 0 of m 1 , m 2 .di-elect cons.GF(2 2n ) is given by m.sub.0 =m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))α+(y.sub.1 y.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))(α+1); and a calculation unit for calculating the multiplication m 0 by executing said multiplications and additions in the subfield GF(2 n ).
Claim 15
Dependent Claim
182 words
An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplicative inverse in finite field GF(2 2n ), the computer readable program code means includes: first computer readable program code means for causing said computer to express an element m.di-elect cons.GF(2 2n ) as m=xα+y(α+1)(x,y.di-elect cons.GF(2.sup.n)) where α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(a(x+y).sup.2 +xy).sup.-1 yα+(a(x+y).sup.2 +xy).sup.-1 x(α+1) by combining a normal basis [α α+1] with extended Euclidean algorithm; and second computer readable program code means for causing said computer to calculate the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 16
Dependent Claim
182 words
An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplicative inverse in finite field GF(2 2n ), the computer readable program code means includes: first computer readable program code means for causing said computer to express an element m.di-elect cons.GF(2 2n ) as m=xα+y(α+1)(x,y.di-elect cons.GF(2.sup.n)) where α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(a(x+y).sup.2 +xy).sup.-1 yα+(a(x+y).sup.2 +xy).sup.-1 x(α+1) by combining a normal basis [α α+1] with extended Euclidean algorithm; and second computer readable program code means for causing said computer to calculate the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 17
Dependent Claim
184 words
An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplication in finite field GF(2 2n ), the computer readable program code means includes: first computer readable program code means for causing said computer to reduce a multiplication of two elements m 1 and m 2 in GF(2 2n ) into multiplications and additions in subfield GF(2 n ) by expressing m 1 , m 2 .di-elect cons.GF(2 2n ) as m.sub.1 =x.sub.1 α+y.sub.1 (α+1), m.sub.2 =x.sub.2 α+y.sub.2 (α+1) where x 1 , y 1 .di-elect cons.GF(2 n ), i=1, 2, α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 0 of m 1 , m 2 .di-elect cons.GF(2 2n ) is given by m.sub.0 =m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))α+(y.sub.1 y.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))(α+1); and second computer readable program code means for causing said computer to calculate the multiplication m 0 by executing said multiplications and additions in the subfield GF(2 n ).
Claim 18
Dependent Claim
184 words
An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplication in finite field GF(2 2n ), the computer readable program code means includes: first computer readable program code means for causing said computer to reduce a multiplication of two elements m 1 and m 2 in GF(2 2n ) into multiplications and additions in subfield GF(2 n ) by expressing m 1 , m 2 .di-elect cons.GF(2 2n ) as m.sub.1 =x.sub.1 α+y.sub.1 (α+1), m.sub.2 =x.sub.2 α+y.sub.2 (α+1) where x 1 , y 1 .di-elect cons.GF(2 n ), i=1, 2, α.di-elect cons.GF(2 2n )\GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 0 of m 1 , m 2 .di-elect cons.GF(2 2n ) is given by m.sub.0 =m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))α+(y.sub.1 y.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))(α+1); and second computer readable program code means for causing said computer to calculate the multiplication m 0 by executing said multiplications and additions in the subfield GF(2 n ).
Claim 19
Independent Claim
149 words
A method for calculating a multiplication in finite field GF(2 2n ), comprising the steps of: expressing elements m 1 , m 2 .di-elect cons.GF(2 2n )≃GF(2 n )[x]/(x 2 +x+a) as m.sub.1 =x.sub.1 +y.sub.1 α m.sub.2 =x.sub.2 +y.sub.2 α(x.sub.1, x.sub.2, y.sub.1, y.sub.2 .di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) is expressed as a combination of multiplications and additions in subfield GF(2 n ) given by m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +ay.sub.1 y.sub.2)+((x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2)+x.sub.1 x.sub.2)α by using a standard basis [1α]; and calculating the multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) by executing said combination of multiplications and additions in the subfield GF(2 n ).
Claim 20
Independent Claim
149 words
A method for calculating a multiplication in finite field GF(2 2n ), comprising the steps of: expressing elements m 1 , m 2 .di-elect cons.GF(2 2n )≃GF(2 n )[x]/(x 2 +x+a) as m.sub.1 =x.sub.1 +y.sub.1 α m.sub.2 =x.sub.2 +y.sub.2 α(x.sub.1, x.sub.2, y.sub.1, y.sub.2 .di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) is expressed as a combination of multiplications and additions in subfield GF(2 n ) given by m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +ay.sub.1 y.sub.2)+((x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2)+x.sub.1 x.sub.2)α by using a standard basis [1α]; and calculating the multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) by executing said combination of multiplications and additions in the subfield GF(2 n ).
Claim 21
Independent Claim
129 words
A method for calculating a multiplicative inverse in finite field GF(2 2n ), comprising the steps of: expressing an element m.di-elect cons.GF(2 2n )≃GF(2 n ) [x]/(x 2 +x+a) as m=x+yα(x,y.di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a .di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(x(x+y)+ay.sup.2).sup.-1 ((x+y)+yα) by using a standard basis [1α]; and calculating the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 22
Independent Claim
129 words
A method for calculating a multiplicative inverse in finite field GF(2 2n ), comprising the steps of: expressing an element m.di-elect cons.GF(2 2n )≃GF(2 n ) [x]/(x 2 +x+a) as m=x+yα(x,y.di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a .di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(x(x+y)+ay.sup.2).sup.-1 ((x+y)+yα) by using a standard basis [1α]; and calculating the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 23
Independent Claim
156 words
A device for calculating a multiplication in finite field GF(2 2n ), comprising: an input unit for expressing elements m 1 , m 2 .di-elect cons.GF(2 2n ) ≃GF(2 n )[x]/(x 2 +x+a) as m.sub.1 =x.sub.1 +y.sub.1 α m.sub.2 =x.sub.2 +y.sub.2 α(x.sub.1, x.sub.2, y.sub.1, y.sub.2 .di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) is expressed as a combination of multiplications and additions in subfield GF(2 n ) given by m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 ay.sub.1 y.sub.2)+((x.sub.1 +y.sub.1) (x.sub.2 +y.sub.2)+x.sub.1 x.sub.2)α by using a standard basis [1α]; and a calculation unit for calculating the multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) by executing said combination of multiplications and additions in the subfield GF(2 n ).
Claim 24
Independent Claim
156 words
A device for calculating a multiplication in finite field GF(2 2n ), comprising: an input unit for expressing elements m 1 , m 2 .di-elect cons.GF(2 2n ) ≃GF(2 n )[x]/(x 2 +x+a) as m.sub.1 =x.sub.1 +y.sub.1 α m.sub.2 =x.sub.2 +y.sub.2 α(x.sub.1, x.sub.2, y.sub.1, y.sub.2 .di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) is expressed as a combination of multiplications and additions in subfield GF(2 n ) given by m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 ay.sub.1 y.sub.2)+((x.sub.1 +y.sub.1) (x.sub.2 +y.sub.2)+x.sub.1 x.sub.2)α by using a standard basis [1α]; and a calculation unit for calculating the multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) by executing said combination of multiplications and additions in the subfield GF(2 n ).
Claim 25
Independent Claim
132 words
A device for calculating a multiplicative inverse in finite field GF(2 2n ), comprising: an input unit for expressing an element m.di-elect cons.GF(2 2n )≃GF(2 n )[x]/(x 2 +x+a) as m=x+yα(x,y.di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(x(x+y)+ay.sup.2).sup.-1 ((x+y)+yα) by using a standard basis [1α]; and a calculation unit for calculating the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 26
Independent Claim
132 words
A device for calculating a multiplicative inverse in finite field GF(2 2n ), comprising: an input unit for expressing an element m.di-elect cons.GF(2 2n )≃GF(2 n )[x]/(x 2 +x+a) as m=x+yα(x,y.di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(x(x+y)+ay.sup.2).sup.-1 ((x+y)+yα) by using a standard basis [1α]; and a calculation unit for calculating the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 27
Dependent Claim
198 words
An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplication in finite field GF(2 2n ), the computer readable program code means includes: first computer readable program code means for causing said computer to express elements m 1 , m 2 .di-elect cons.GF(2 2n )≃GF(2 n )[x]/(x 2 +x+a) as m.sub.1 =x.sub.1 +y.sub.1 α m.sub.2 =x.sub.2 +y.sub.2 α(x.sub.1, x.sub.2, y.sub.1, y.sub.2 .di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) is expressed as a combination of multiplications and additions in subfield GF(2 n ) given by m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +ay.sub.1 y.sub.2)+((x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2)+x.sub.1 x.sub.2)α by using a standard basis [1α]; and second computer readable program code means for causing said computer to calculate the multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) by executing said combination of multiplications and additions in the subfield GF(2 n ).
Claim 28
Dependent Claim
198 words
An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplication in finite field GF(2 2n ), the computer readable program code means includes: first computer readable program code means for causing said computer to express elements m 1 , m 2 .di-elect cons.GF(2 2n )≃GF(2 n )[x]/(x 2 +x+a) as m.sub.1 =x.sub.1 +y.sub.1 α m.sub.2 =x.sub.2 +y.sub.2 α(x.sub.1, x.sub.2, y.sub.1, y.sub.2 .di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) is expressed as a combination of multiplications and additions in subfield GF(2 n ) given by m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +ay.sub.1 y.sub.2)+((x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2)+x.sub.1 x.sub.2)α by using a standard basis [1α]; and second computer readable program code means for causing said computer to calculate the multiplication m 1 m 2 of the elements m 1 and m 2 in the finite field GF(2 2n ) by executing said combination of multiplications and additions in the subfield GF(2 n ).
Claim 29
Dependent Claim
175 words
An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplicative inverse in finite field GF(2 2n ), the computer readable program code means includes: first computer readable program code means for causing said computer to express an element m.di-elect cons.GF(2 2n )≃GF(2 n )[x]/(x 2 +x+a) as m=x+yα(x,y.di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(x(x+y)+ay.sup.2).sup.-1 ((x+y)+yα) using a standard basis [1α]; and second computer readable program code means for causing said computer to calculate the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
Claim 30
Dependent Claim
175 words
An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplicative inverse in finite field GF(2 2n ), the computer readable program code means includes: first computer readable program code means for causing said computer to express an element m.di-elect cons.GF(2 2n )≃GF(2 n )[x]/(x 2 +x+a) as m=x+yα(x,y.di-elect cons.GF(2.sup.n)) where α.epsilon slash.GF(2 n ), α 2 +α+a=0, and a.di-elect cons.GF(2 n ) so that a multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2 n ) given by m.sup.-1 =(x(x+y)+ay.sup.2).sup.-1 ((x+y)+yα) using a standard basis [1α]; and second computer readable program code means for causing said computer to calculate the multiplicative inverse m -1 of the element m in the finite field GF(2 2n ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2 n ).
References Cited (Backward Citations)
US4251875A
Cited
US4587627A
Cited
JPH01181232A
Cited
US5213209A
Cited
US5414719A
Cited
US5689452A
Cited
EP0741355A1
Cited
US5812438A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-14 | 2003-09-13 | 2004-03-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-14 | 2007-09-13 | 2008-03-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-14 | 2011-09-13 | 2012-03-14 | $7700.00 | Window Closed / Lapsed |