Efficient Computation of Roots in Finite Fields

    loading  Checking for direct PDF access through Ovid

Abstract

We present an algorithm to compute rth roots in 𝔽 with complexity Õ[(log m + r log q) m log q] if (m, q) = 1 and either (q(q−1), r) = 1 or r|(q−1) and ((q−1)/r, r) = 1. This compares well to previously known algorithms, which need O(rm3 log3q) steps.

Related Topics

    loading  Loading Related Articles