2020/06/12 by Bach, Eric, Sorenson, Jonathan
#11y05 #11y16 #68q25 #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.2006.07445
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( ( (log x)3 )/(loglog x) ) arithmetic operations. We also present other running times based on differing sets of assumptions and heuristics.