2
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ How many steps should it take to determine which of 110592 and 110596 is 5-smooth? Does division come for free in your model? $\endgroup$
    – The Masked Avenger
    Commented Jul 16, 2013 at 16:41
  • $\begingroup$ 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$). $\endgroup$
    – user37200
    Commented Jul 16, 2013 at 16:54
  • 2
    $\begingroup$ 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. $\endgroup$
    – Felipe Voloch
    Commented Jul 16, 2013 at 17:08
  • $\begingroup$ @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. :/ $\endgroup$
    – user37200
    Commented Jul 16, 2013 at 18:05
  • $\begingroup$ Perhaps instead of divide by p, perhaps a step is gcd with a large power of p. $\endgroup$
    – The Masked Avenger
    Commented Jul 16, 2013 at 19:01

0

Reset to default

You must log in to answer this question.