View Single Post
Old 2005-04-06, 15:06   #2
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

1D2416 Posts
Thumbs up

Originally Posted by akruppa

I've been wondering about how the technique of estimating root properties for NFS or Knuth-Schroeppel factors for MPQS actually works. According to various sources (i.e. TAOCP 4.5.4) they compare the average log contribution of small primes to the factorization of the numbers that are tested for smoothness with the average log contribution in uniformly, randomly chosen integers.

Let f(p,S) be the average exponent of the prime p in values chosen uniformly at random from the set S. For S the natural numbers, we have f(p,\N) = 1/(p-1).

If S is the set of values we test for smoothness, and s \in S chosen at random, then the log of the residual after dividing out primes p<k can be expected to be

log(s)-\sum_{p \in \Primes, p<k} f(p,S)*log(p)

Comparing the size of the residual to that for S=\N, we find that the residual should be smaller by
\alpha = \sum_{p \in \Primes, p<k} (f(p,S) - 1/(p-1))*log(p)

Now, apparantly, they argue that because of this the probability that an s \in S is smooth is about the same as that a random integer of size s/exp(\alpha) is smooth (to the same bound k).

Is this about right? Has anything been proven about this estimate? Especially the last step seems like a leap of faith to me... numerical evidence supports the idea, as shown in several papers (I remember something in Lenstra/Bernstein's NFS paper), but I was wondering if there's more theoretical fundation to it. Any comments or pointers to sources would be greatly appreciated.

"Is this about right? Has anything been proven about this estimate? "

Yes, it is about right. Yes, it is an assumption; but "leap of faith" is
too strong. There is substantial supporting numerical evidence. I characterise something as "leap of faith" when there is no supporting
evidence. There are also some probability arguments to suggest that the
assumption is correct (or at most off by a constant factor). These
arguments [for at least quadratic extension fields] are discussed in the
"Cohen-Lenstra" heuristics.
R.D. Silverman is offline   Reply With Quote