computing field inverses without EGCD()
saw this nice "trick" in blackeye's solution to "howl"
file history:

oct15_2009 added Giuliano Bertoletti's email
oct08_2009 created
+
Pinvers PROC poly_a:DWORD
 ; calculate a^(1) mod X^31+X^3+1
 ; uses the square and multiply algo
 ; it's based on the fact in any GF(2^n) a^(1)= a^(n2) mod poly
 ; in our case n2=2^312=0x7FFFFFFE
 ; very little optimized

 pushad
 mov ecx,7FFFFFFEh
 xor ebx,ebx
 inc ebx
 mov edx,poly_a
 .while ecx!=0
 shr ecx,1
 .if CARRY?
 invoke Pmul,ebx,edx
 mov ebx,eax
 .endif
 jecxz @F
 invoke Pmul,edx,edx
 mov edx,eax
 @@:
 .endw
 mov dword ptr [esp+01Ch],ebx
 popad
 ret
+
think there is small typo, or "n" is used two different ways, should read:
+
 ; it's based on the fact in any GF(2^n) a^(1)= a^((2^n)2) mod poly
+
didn't get many hits searching for this trick, except one mention of fermat's little theorem
does it really work? why?
does it work in other extension fields, not just GF(2^n) ?
came up with two arguments why it works:
first way:
GF(2^n) has mult cyclic group with 2^n1 elems (zero not a member)
let g be a generator, the elems can be represented {1,g,g^2,...,g^(2^n2)}
two elems g^x and g^y are inverses iff g^x*g^y=g^0 in this group
> two elems g^x and g^y are inverses iff x + y = 0 (mod 2^n1) !!MAIN CONDITION!!
watch what happens when g^x is exponentiated by 2^n2:
(g^x)^(2^n2)
= g^(x*(2^n2))
= g^(x*(2^n11))
= g^(x*(2^n1)x)
now we can test if this exponet satisfies the main condition:
x*(2^n1)x = y (mod 2^n1)
x = y (mod 2^n1)
y+x = 0 (mod 2^n1) yes!
second way:
fermat's theorem is:
a^(p1) = 1 (mod p)
a*a^(p2) = 1 (mod p)
i think fermat's condition that p be prime was just to enforce that the numbers
from [1,p] formed a group... here 2^n1 (the size of the mult group) is not
prime, but since we know the elems are a group, maybe this theorem still works...
if it does then the elements a and a^(p2) are inverses
...so this should really work for any field, not just binary extension fields, right?
let us try extension field GF(3^3) and irreducible p(x) = x^3 + 2*x + 1
here are the elements:
0
1
2
x
x + 1
x + 2
2*x
2*x + 1
2*x + 2
x^2
x^2 + 1
x^2 + 2
x^2 + x
x^2 + x + 1
x^2 + x + 2
x^2 + 2*x
x^2 + 2*x + 1
x^2 + 2*x + 2
2*x^2
2*x^2 + 1
2*x^2 + 2
2*x^2 + x
2*x^2 + x + 1
2*x^2 + x + 2
2*x^2 + 2*x
2*x^2 + 2*x + 1
2*x^2 + 2*x + 2
the mult group has all these except 0, and let us choose generator g = x, then {x^0, x^1, ..., x^(3^32)} =
g^00 = 1
g^01 = x
g^02 = x^2
g^03 = x + 2
g^04 = x^2 + 2*x
g^05 = 2*x^2 + x + 2
g^06 = x^2 + x + 1
g^07 = x^2 + 2*x + 2
g^08 = 2*x^2 + 2
g^09 = x + 1
g^11 = x^2 + x
g^12 = x^2 + x + 2
g^13 = x^2 + 2
g^14 = 2
g^15 = 2*x
g^16 = 2*x^2
g^17 = 2*x + 1
g^18 = 2*x^2 + x
g^19 = x^2 + 2*x + 1
g^20 = 2*x^2 + 2*x + 2
g^21 = 2*x^2 + x + 1
g^22 = x^2 + 1
g^23 = 2*x + 2
g^24 = 2*x^2 + 2*x
g^25 = 2*x^2 + 2*x + 1
g^26 = 2*x^2 + 1
with 3^3 elements total in the field, the mult group here has 3^31 (this is the "p" in fermat theorem)
thus any element exponentiatiated to the 3^32 = 25 should be its inverse
we test...
example:
g^05 = 2*x^2 + x + 2
(2*x^2 + x + 2)^25 = x^2 + 1 = g^22
we can verify by seeing that g^05 * g^22 = g^00 = 1
or just enter it into pari:
(2*x^2 + x + 2)*(x^2 + 1) = 1
it works!
example:
g^01 = x
(x)^25 = 2x^2 + 1 = g^26
we can verify by seeing that g^01 * g^26 = g^00 = 1
or just enter it into pari:
x*(2x^2 + 1) = 1
it works!
the last example makes it seem almost obvious...
x * x^25 = x^26 and x^26 = 1 (mod 27)
and the method is very efficient  because even for large field like GF(2^128), you don't have to
multiply 2^1282 times when using methods like exponentiation by squaring... you only need about
2*log(n) mults
PARI NOTES:
p = Mod(1, 2)*x^3 + Mod(1, 2)*x + Mod(1, 2)
forvec(v=[[0,2],[0,2],[0,2]],print(lift((v[1]*x^2 + v[2]*x + v[3])*Mod(1,3)) % p))
for(i=0,26,print( lift( (((x)^i)*Mod(1,3) % p) )))
Update! Giuliano Bertoletti has another angle at explaining it, in this email from Oct12_2009:
+
 This hinges on the fact that for any finite field F=GF(q), the order of any
 element x of the multiplicative  group F* = F \ { 0 }, divides q  1.
 More specifially this follows from Lagrange's theorem that states that for any

 subgroup H of a group G, the order of H divides the order or G.
 So, if t is the order of x in F*, by definition x^t = 1 and so does x^(s*t) =
 1^s = 1, where s = (q  1) / t is a positive integer.

 Notice that unless q1 is a prime, not all elements of F* are generators,
 still the inverse is unique and x^1 = x^(q2) because
 x^(q2) * x = x^(q1) = 1.

 If q1 is not a prime however, for some x there exist a t < q1, t divides q1,
 for which x^(t1) = x^1, which basically means that for some x you could stop
 computing powers earlier (but this is clearly unusable since we do not know
 the order of an element in advance).

 Cheers,
 Giulio.
+
~~~~~~~~~~~~~~
andrewl
oct09_2009
crackmes.de