Lattice basis reduction, Jacobi sums and hyperelliptic cryptosystems
Joe Buhler, Neal Koblitz · Bulletin of the Australian Mathematical Society · 1998
Using the LLL-algorithm for finding short vectors in lattices, we show how to compute a Jacobi sum for the prime field Fp in Q(e2πi/n) in time O(log3p), where n is small and fixed, p is large, and p = 1 (mod n). This result is useful in the construction of hyperelliptic cryptosystems.