Thread: Knuth-Schroeppel analysis View Single Post
 2005-04-06, 14:43 #1 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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