Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic
Sergey Borisovich Gashkov, Гашков Игорь Борисович · Moscow University Mathematics Bulletin · 2018
It was proved that the complexity of square root computation in the Galois field GF (3 s ), s = 2 k r , is equal to O ( M (2 k ) M ( r ) k + M ( r ) log 2 r ) + 2 k kr 1+ o (1) , where M ( n ) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF (3 s ) is equal to O ( M (2 k ) M ( r )) and O ( M (2 k ) M ( r )) + r 1+ o (1) , respectively. If the basis in the field GF (3 r ) is determined by an irreducible binomial over GF (3) or is an optimal normal basis, then the summands 2 k kr 1+ o (1) and r 1+ o (1) can be omitted. For M ( n ) one may take n log 2 n ψ ( n ) where ψ ( n ) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O r ( M ( s ) log 2 s ) = s (log 2 s ) 2 ψ ( s ).