2022/03/03 by Jordi Guàrdia, Guàrdia, Jordi, Enric Nart +1
Computer Science · #11R04 #11Y40 #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2203.01691
openalex publication_date 2022/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a prime p, the OM algorithm finds the p-adic factorization of an irreducible polynomial f∈ℤ[x] in polynomial time. This may be applied to construct p-integral bases in the number field K defined by f. In this paper, we adapt the OM techniques to work with a positive integer N instead of p. As an application, we obtain an algorithm to compute global integral bases in K, which does not require a previous factorization of the discriminant of f.