20050611, 19:55  #1 
Mar 2005
Poland
5×7 Posts 
Smoothness test
I have a number, say 50 digits long. It is not any special form, and I know its factorization.
I want to find all numbers in my number neibourhood (say from n10000 to n+10000) which are smooth over small factorbase, say 2^32. How can I do this in a most efficent and fast way? I'm not interested in full factorization of each number, only FINDING these, which can be factorized to primes less than 2^32. Trial factorisation by every prime in fb doestn't seem to be the fastest way, but most obvious one. What are your ideas? Washuu 
20050611, 20:02  #2  
∂^{2}ω=0
Sep 2002
República de California
2×5×1,163 Posts 
Quote:


20050612, 01:32  #3 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001011111_{2} Posts 
Page 115, Crandall & Pomerance, entitled "Sieving to recognize smooth numbers" gives a description of what I think you want to do.

20050614, 11:06  #4 
Mar 2005
Poland
5×7 Posts 
Done!
Hi.
I haven't got Crandall&Pomerance book (maybe someone could point me the place in priv message), but I have managed to do my task. This was very simple idea, and rather slow and ugly algorithm, but it worked  maybe someone will find it useful or correct me. I am not able to explain it very clearly (my english...), but I'll try. I wanted to find all smooth numbers in some range (n,n+20000). So I made an array  two bytes per number (40000), and in another array I had all primes in my factorbase. Odd primes upto 2^32 (without 2)  one bit per number. This one was big  256 MB. In a loop: I get a prime, and added a point to places in array, where numbers were divisible by this prime (first calculated remainder for n and another loop for adding this prime). I repeated inner loop and added another point when number was divisible by p^2, another for p^3... until p^n > 2^32. And I get another prime (external loop), and so on. This way prime numbers (and those not divisible by any of primes in fb) had 0 "points" in array, numbers divisible by 2*3 had 2 "points", divisible by 2*2*2 had 3 "points" and 2*2*3*3 had 4 points (and so on). The minimum number of "points" when number can be completely factored, is when n=largerst_prime_in_fb^x. So by a simple array search I printed the numbers which have "points" greater than log(base: greatest prime in fb) of n  all were smooth in the factorbase  and there weren't many numbers. If someone could correct/optimise my algorithm in simple words, I would appreciate this. Regards, Washuu Last fiddled with by Washuu on 20050614 at 11:07 
20050614, 11:07  #5 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
You rediscovered sieving
Alex 
20050614, 15:58  #6  
Mar 2005
Poland
5×7 Posts 
Quote:
Okay, so push me a little further and tell me about using polynomials in sieves, if you have a few minutes :) I have read that sieve of Eratosthenes is better when using some 4x^2n poly, but I couldn't catch it (yet). 

20050614, 16:06  #7 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
That would take more than a few minutes to do right. In very brief, for any polynomial f(x), if pf(r) then pf(r+p). So you can look for the roots r_1, r_2... of f (mod p) and sieve positions r_1+k*p, r_2+k*p, for integer k.
If you're interested in this kind of stuff, get Crandall and Pomerance's book! It's great. Alex 
20050614, 16:07  #8 
"Phil"
Sep 2002
Tracktown, U.S.A.
3·373 Posts 
Great  you have the sieve set up so that you can recognize any Bsmooth numbers where B can be any bound up to 2^32! (With a lower B, you don't need such a large array of primes.) Crandall and Pomerance suggest a couple of improvements. Rather than counting the factors, you could multiply each location in the array by p when you find that p or some power of p divides that number. Then smooth numbers are the numbers where the product after sieving is equal to the original number represented by the location. They also suggest, to avoid all the multiplications, add the approximate logarithm of p, say log base 2 rounded to the nearest integer. So for the example of 12000, we add 1 each time we find a power of 2 divides it, we add 2 each time a power of 3 or 5 divides it, we add 3 for each power of 7, etc. The result is 13, close enough to log base 2 of 12000 to recognize it is smooth.

20050626, 18:29  #9 
Jun 2005
Near Beetlegeuse
2^{2}·97 Posts 
ksmooth
I'm just finding my way with this so I found this thread quite enlightening, but I have two quite possibly stupid questions.
Went to Mathworld to find out what smooth means where I learned that an integer n is ksmooth if it has no prime factor >k. So stupid question no. 1 is how do you know how smooth n is if you're sieving for factors up to some bound, in this case 2^32. Surely n can still have prime factors > max prime in fb, can't it? (I'm obviously assuming that n is sufficiently large that fb does not encompass sqrt(n).) Second stupid question: Is there any point in defining n (I am actually thinking of a subset of N) as ksmooth where k is some fraction of n, n/6 for example, where this can be proved to be a property of the set? 
20050627, 00:24  #10 
Jun 2003
The Texas Hill Country
3^{2}·11^{2} Posts 
Yes. When sieving, we are looking at the norms of the polynomials. MOST of them are less smooth than we desire. If you are working strictly from a factor base (with primes up to k) then sieving will find numbers that are ksmooth. However, it is more efficient to consider norms that are smooth to some larger limit, l, but not necessarily ksmooth. The technique that we use does not find ALL of the norms that are lsmooth. Instead it takes those that are ksmooth plus at most two factors between k and l. Again, it is more important to be fast rather than strictly accurate. So some are missed when we use approximations to speed up the search. Once extremely likely candidates are found, they are checked accurately to assure that they are lsmooth.

20050627, 11:35  #11  
Nov 2003
2^{2}·5·373 Posts 
Quote:
generally do not have norms. Instead, we are looking at norms of elements of the field(s) that is generated by appending a root of the polynomial(s) to the rationals. Let f be an irreducible polynomial of degree d. Let alpha be a root. Then the norm of the element a+b alpha is the product of all of its algebraic conjugates. Put the polynomial in product form: f(x) = product i=1 to d of (x  alpha_i) where alpha_i, i = 1,d are the roots. The norm of (a + b alpha) is product(a + b alpha_i). Factor out b from each term of this product (there are d terms). We then get norm(a + b alpha) = (b)^d f(a/b). [substitute (a/b) for x in the product form of the polynomial] 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
Inverse of Smoothness Probability  paul0  Math  6  20170725 16:41 
Quick smoothness test  Sam Kennedy  Programming  18  20130121 14:23 
Double check LL test faster than first run test  lidocorc  Software  3  20081203 15:12 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 