Unpublished Paper
An Algorithm to Generate Random Factored Smooth Integers
(2020)
Abstract
Let x≥y>0 be integers. We present an algorithm that will generate an integer n≤x at random, with known prime factorization, such that every prime divisor of n is ≤y. Further, asymptotically, n is chosen uniformly from among all integers ≤x that have no prime divisors >y. In particular, if we assume the Extended Riemann Hypothesis, then with probability 1−o(1), the average running time of our algorithm is
O((logx)^3/loglogx)
arithmetic operations. We also present other running times based on differing sets of assumptions and heuristics.
Keywords
- Smooth numbers,
- Friable numbers
Disciplines
Publication Date
June, 2020
DOI
https://doi.org/10.48550/arXiv.2006.07445
Comments
This paper was presented as a poster at ANTS XIV where it won the best poster award.
Citation Information
Eric Bach and Jonathan P Sorenson. "An Algorithm to Generate Random Factored Smooth Integers" (2020) Available at: http://works.bepress.com/jonathan_sorenson/41/