Calculating the power residue symbol and ibeta: Applications of computing the group structure of the principal units of a p-adic number field completion

In the recent PhD thesis of Bouw, an algorithm is examined that computes the group structure of the principal units of a p-adic number field completion. In the same thesis, this algorithm is used to compute Hilbert norm residue symbols. In the present paper, we will demonstrate two other applications. The first application is the computation of an important invariant of number field completions, called ibeta. The algorithm that computes ibeta is deterministic and runs in polynomial time. The second application uses Hilbert norm residue symbols and yields a probabilistic algorithm that computes the m-th power residue symbol (a/b)m in arbitrary number fields K. This probabilistic algorithm relies on LLL-reduction and sampling of nearprimes. Using heuristics, we analyse its complexity to be polynomial expected time in n = [K: ℚ], log |ΔK| and the input bit size - a tentative conclusion corroborated by timing experiments. An implementation of the algorithm in Magma will be available at https://github.com/kodebro/powerresiduesymbol.

• View at Publisher

Full Text ( Final Version , 833kb )