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

2,467 Posts
Default Knuth-Schroeppel analysis

Hi,

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.

Thanks,
Alex
akruppa is offline   Reply With Quote