View Single Post
Old 2005-04-06, 14:43   #1
akruppa's Avatar
Aug 2002

2,467 Posts
Default Knuth-Schroeppel analysis


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.

akruppa is offline   Reply With Quote