SPRUJ17H March 2022 – October 2024 AM2631 , AM2631-Q1 , AM2632 , AM2632-Q1 , AM2634 , AM2634-Q1
This Shift-Xor-Loop (SXL) operation represents a building block for the implementation of the so-called binary version of the extended GCD algorithm. This is one of the algorithms for calculating inverses in finite fields. When adapted to the field GF(2m), the algorithm can be expressed as follows:
inverse(U, V):
# return 1 / U (modulo V), where U is a value in the GF(2m) field
# defined by prime polynomial V
u, v = U, V
g1, g2 = 1L, 0L
# invariants: U*g1 == u (mod V)
# U*g2 == v (mod V)
# gcd(U, V) == gcd(u, v)
while u != 1 and v != 1:
(1) while (u & 1) == 0:
u = u / 2
g1 = g1 / 2 (modulo V)
(2) while (v & 1) == 0:
v = v / 2
g2 = g2 / 2 (modulo V)
if deg(u) > deg(v):
u ^= v
g1 ^= g2
else:
(3) v ^= u
g2 ^= g1
if u == 1:
return g1
return g2
The SXL operation performs a number of "divide-by-2 (modulo p)" operations on the selected registers. The operation implements each of the while loops (1) and (2), by dividing-by-2 the src0 operand until it is odd and simultaneously dividing-by-2 the src1 operand the same number of times. To divide-by-2 an even value in GF(2m), a shift-right over one bit does the job. To divide-by-2 an odd value in GF(2m), it first needs to be made even by XORing it with the prime polynomial. Hence, each divide-by-2 on src1 may take an extra clock cycle.
Besides updated src0 and src1 values, another important output of the SXL operation is a count of the number of divide-by-2 operations done on src0. This count helps to keep track of the degree (the position of the MSB) of the src0 operand. This count is stored in the [25-16] SHIFT_VALUE bits inside the GF2M_STAT register after the SXL operation finishes.
The SXL operation requires: