Generating random factored ideals in number fields

DOI10.1090/MCOM/3283MaRDI QIDQ4637588zbMATH OpenOpenAlexFDO

Authors Zachary B. Charles

Publication date 24 April 2018

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.06260

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40) Analysis of algorithms and problem complexity (68Q25)

Abstract: We present a randomized polynomial-time algorithm to generate a random integer according to the distribution of norms of ideals at most N in any given number field, along with the factorization of the integer. Using this algorithm, we can produce a random ideal in the ring of algebraic integers uniformly at random among ideals with norm up to N, in polynomial time. We also present a variant of this algorithm for generating ideals in function fields.

Recommendations

• Generating random factored Gaussian integers, easily
• How to Generate Factored Random Numbers
• Generating random factored numbers, easily
• scientific article; zbMATH DE number 2119690
• Factoring polynomials using fewer random bits

Cites work

• Approximate formulas for some functions of prime numbers
• Generating random factored Gaussian integers, easily
• Generating random factored numbers, easily
• How to Generate Factored Random Numbers
• scientific article; zbMATH DE number 3912454 (Why is no real title available?)
• scientific article; zbMATH DE number 66619 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 1954367 (Why is no real title available?)
• Introduction to algorithms
• PRIMES is in P

Cited in

(2)

• Generating random factored numbers, easily
• Generating random factored Gaussian integers, easily

This page was built for publication: Generating random factored ideals in number fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637588)