About: Itoh–Tsujii inversion algorithm

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

The Itoh–Tsujii inversion algorithm is used to invert elements in a finite field. It was introduced in 1988, first over GF(2m) using the normal basis representation of elements, however, the algorithm is generic and can be used for other bases, such as the polynomial basis. It can also be used in any finite field GF(pm). The algorithm is as follows: Input: A ∈ GF(pm)Output: A−1 1. * r ← (pm − 1)/(p − 1) 2. * compute Ar − 1 in GF(pm) 3. * compute Ar = Ar − 1 · A 4. * compute (Ar)−1 in GF(p) 5. * compute A−1 = (Ar)−1 · Ar −1 6. * return A−1

Property Value
dbo:abstract
  • The Itoh–Tsujii inversion algorithm is used to invert elements in a finite field. It was introduced in 1988, first over GF(2m) using the normal basis representation of elements, however, the algorithm is generic and can be used for other bases, such as the polynomial basis. It can also be used in any finite field GF(pm). The algorithm is as follows: Input: A ∈ GF(pm)Output: A−1 1. * r ← (pm − 1)/(p − 1) 2. * compute Ar − 1 in GF(pm) 3. * compute Ar = Ar − 1 · A 4. * compute (Ar)−1 in GF(p) 5. * compute A−1 = (Ar)−1 · Ar −1 6. * return A−1 This algorithm is fast because steps 3 and 5 both involve operations in the subfield GF(p). Similarly, if a small value of p is used, a lookup table can be used for inversion in step 4. The majority of time spent in this algorithm is in step 2, the first exponentiation. This is one reason why this algorithm is well suited for the normal basis, since squaring and exponentiation are relatively easy in that basis. (en)
dbo:wikiPageID
  • 1180190 (xsd:integer)
dbo:wikiPageLength
  • 1877 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1063675646 (xsd:integer)
dbo:wikiPageWikiLink
dcterms:subject
rdfs:comment
  • The Itoh–Tsujii inversion algorithm is used to invert elements in a finite field. It was introduced in 1988, first over GF(2m) using the normal basis representation of elements, however, the algorithm is generic and can be used for other bases, such as the polynomial basis. It can also be used in any finite field GF(pm). The algorithm is as follows: Input: A ∈ GF(pm)Output: A−1 1. * r ← (pm − 1)/(p − 1) 2. * compute Ar − 1 in GF(pm) 3. * compute Ar = Ar − 1 · A 4. * compute (Ar)−1 in GF(p) 5. * compute A−1 = (Ar)−1 · Ar −1 6. * return A−1 (en)
rdfs:label
  • Itoh–Tsujii inversion algorithm (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License