TY - UNPB
T1 - An Algorithm to Generate Random Factored Smooth Integers
AU - Bach, Eric
AU - Sorenson, Jonathan P
N1 - Let $x\ge y>0$ be integers. We present an algorithm that will generate an integer $n\le x$ at random, with known prime factorization, such that every prime divisor of $n$ is $\le y$. Further, asymptotically, $n$ is chosen uniformly from among all integers $\le x$ that have no prime divisors $>y$.
PY - 2020/6
Y1 - 2020/6
N2 - 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.
AB - 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.
KW - Friable numbers
KW - Smooth numbers
UR - https://arxiv.org/abs/2006.07445
U2 - 10.48550/arXiv.2006.07445
DO - 10.48550/arXiv.2006.07445
M3 - Preprint
BT - An Algorithm to Generate Random Factored Smooth Integers
ER -