 mersenneforum.org > Math Smoothness test
 Register FAQ Search Today's Posts Mark Forums Read  2005-06-11, 19:55 #1 Washuu   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 n-10000 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   2005-06-11, 20:02   #2
ewmayer
2ω=0

Sep 2002
República de California

2×5×1,163 Posts Quote:
 Originally Posted by Washuu I'm not interested in full factorization of each number, only FINDING these, which can be factorized to primes less than 2^32.
Alas, determining the smoothness of a number (in the sense you desire, as opposed to just seeing if it has *any* factors within a target range) amounts to complete factorization. However, for a bound of 2^32 you should be able to construct a quite efficient sieve that accomplishes your desired task.   2005-06-12, 01:32 #3 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 100010111112 Posts Page 115, Crandall & Pomerance, entitled "Sieving to recognize smooth numbers" gives a description of what I think you want to do.   2005-06-14, 11:06 #4 Washuu   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 2005-06-14 at 11:07   2005-06-14, 11:07 #5 akruppa   "Nancy" Aug 2002 Alexandria 2,467 Posts You rediscovered sieving Alex   2005-06-14, 15:58   #6
Washuu

Mar 2005
Poland

5×7 Posts Quote:
 Originally Posted by akruppa You rediscovered sieving Alex
Yup, but only the main idea.

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^2-n poly, but I couldn't catch it (yet).   2005-06-14, 16:06 #7 akruppa   "Nancy" Aug 2002 Alexandria 1001101000112 Posts That would take more than a few minutes to do right. In very brief, for any polynomial f(x), if p|f(r) then p|f(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   2005-06-14, 16:07 #8 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 3·373 Posts Great - you have the sieve set up so that you can recognize any B-smooth 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.   2005-06-26, 18:29 #9 Numbers   Jun 2005 Near Beetlegeuse 22·97 Posts k-smooth 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 k-smooth 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 k-smooth where k is some fraction of n, n/6 for example, where this can be proved to be a property of the set?   2005-06-27, 00:24 #10 Wacky   Jun 2003 The Texas Hill Country 32·112 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 k-smooth. However, it is more efficient to consider norms that are smooth to some larger limit, l, but not necessarily k-smooth. The technique that we use does not find ALL of the norms that are l-smooth. Instead it takes those that are k-smooth 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 l-smooth.   2005-06-27, 11:35   #11
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by Wacky 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 k-smooth. However, it is more efficient to consider norms that are smooth to some larger limit, l, but not necessarily k-smooth. The technique that we use does not find ALL of the norms that are l-smooth. Instead it takes those that are k-smooth 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 l-smooth.
Slight correction: We are not looking at norms of polynomials. Polynomials
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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 paul0 Math 6 2017-07-25 16:41 Sam Kennedy Programming 18 2013-01-21 14:23 lidocorc Software 3 2008-12-03 15:12 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 00:10.

Wed May 12 00:10:21 UTC 2021 up 33 days, 18:51, 0 users, load averages: 4.33, 4.17, 3.84 