An Algorithm to Generate Random Factored Smooth Integers

MaRDI QIDQ6342803zbMATH OpenFDO

Authors Eric Bach, Jonathan P. Sorenson

Publication date 12 June 2020

Mathematics Subject Classification ID

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

Abstract: Let $xgey>0$ be integers. We present an algorithm that will generate an integer $nlex$ at random, with known prime factorization, such that every prime divisor of $n$ is $ley$. Further, asymptotically, $n$ is chosen uniformly from among all integers $lex$ 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 ${\displaystyle }$ Oleft( frac{ (log x)^3 }{loglog x} ight) ${\displaystyle }$ arithmetic operations. We also present other running times based on differing sets of assumptions and heuristics.

This page was built for publication: An Algorithm to Generate Random Factored Smooth Integers

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