Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am currently reading section 5 of Pomerance's paper The Number Field Sieve and I have a few questions about smooth numbers.

A number $x\in\mathbb Z_{\ge1}$ is called $z$-smooth if every prime divisor $p$ of $x$ satisfies $p\le z$. So if we want to check if a given natural number is $z$-smooth, we could simply trial divide by all prime numbers $p\le z$, which should take about $\pi(z)$ steps ($\pi$ = prime-counting function).

However, Pomerance states that it would take about $z$ steps, which I think should be $\pi(z)$ (as pointed out above). And he also states that using his early abort strategy one would need about $z^{1/2}$ steps, which I think should read $\pi(z)^{1/2}$.

I guess that I am missing his point, since he is a very accomplished number theorist, but I am not sure.

share|cite|improve this question
How many steps should it take to determine which of 110592 and 110596 is 5-smooth? Does division come for free in your model? – The Masked Avenger Jul 16 '13 at 16:41
Okay, I see what you mean. But what does Pomerance mean, when he says "... trial division, taking about $z$ steps to recognize whether $s$ is $z$-smooth"? E.g. for your first number $110592=2^{12}\cdot 3^3$ we would need about $15=12+3$ divisons, and for $110596=2^2\cdot 43\cdot 643$ we would need about $4$ ($2$ for $2$, $1$ check for $3$, $1$ check for $5$). – Tom Jul 16 '13 at 16:54
To check by trial division if a number is $z$-smooth in $\pi(z)$ steps would require knowing all primes up to $z$. If you just trial divide by all numbers up to $z$ you avoid the extra cost of identifying the primes. Which is best will depend on this extra cost. – Felipe Voloch Jul 16 '13 at 17:08
@FelipeVoloch Since the algorithms described in Pomerance's paper require many number to be checked for smoothness I am assuming that we know all the primes up to z (e.g. they could be safed in an array). So I am still wondering what his statement means. :/ – Tom Jul 16 '13 at 18:05
Perhaps instead of divide by p, perhaps a step is gcd with a large power of p. – The Masked Avenger Jul 16 '13 at 19:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.