Calculating the power residue symbol and ibeta: Applications of computing the group structure of the principal units of a p-adic number field completion
| Autor: | Koen de Boer, Carlo Pagano |
|---|---|
| Přispěvatelé: | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Algebraic number theory 010102 general mathematics 010103 numerical & computational mathematics Algebraic number field Legendre symbol 01 natural sciences Power residue symbol Randomized algorithm Combinatorics symbols.namesake Norm (mathematics) ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION symbols 0101 mathematics Computational number theory p-adic number Mathematics |
| Zdroj: | ISSAC |
| DOI: | 10.1145/3087604.3087637 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|