论文标题
一种生成随机计算的光滑整数的算法
An Algorithm to Generate Random Factored Smooth Integers
论文作者
论文摘要
令$ x \ ge y> 0 $为整数。我们提出了一种算法，该算法将随机生成一个整数$ n \ le x $，并具有已知的质量分解，使得$ n $的每个素数为$ \ le y $。此外，从所有没有Prime Divisors $> y $的整数中均匀地选择了$ n $。特别是，如果我们假设扩展的Riemann假设，则使用概率$ 1-O（1）$，我们的算法的平均运行时间为$$ o \ left（\ frac {（\ log x）^3} {\ log log \ log x} \ x} \ right）$$ ARITHMETIC操作。我们还根据不同的假设和启发式方法提出其他运行时间。
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$. In particular, if we assume the Extended Riemann Hypothesis, then with probability $1-o(1)$, the average running time of our algorithm is $$ O\left( \frac{ (\log x)^3 }{\log\log x} \right) $$ arithmetic operations. We also present other running times based on differing sets of assumptions and heuristics.
