mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-06-11, 19:55   #1
Washuu
 
Mar 2005
Poland

3510 Posts
Question 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
Washuu is offline   Reply With Quote
Old 2005-06-11, 20:02   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3×53×31 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2005-06-12, 01:32   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default

Page 115, Crandall & Pomerance, entitled "Sieving to recognize smooth numbers" gives a description of what I think you want to do.
philmoore is offline   Reply With Quote
Old 2005-06-14, 11:06   #4
Washuu
 
Mar 2005
Poland

5·7 Posts
Thumbs up 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
Washuu is offline   Reply With Quote
Old 2005-06-14, 11:07   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

You rediscovered sieving

Alex
akruppa is offline   Reply With Quote
Old 2005-06-14, 15:58   #6
Washuu
 
Mar 2005
Poland

5·7 Posts
Default

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).
Washuu is offline   Reply With Quote
Old 2005-06-14, 16:06   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-06-14, 16:07   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111910 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2005-06-26, 18:29   #9
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22×97 Posts
Default 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?
Numbers is offline   Reply With Quote
Old 2005-06-27, 00:24   #10
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

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.
Wacky is offline   Reply With Quote
Old 2005-06-27, 11:35   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Thumbs up

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]
R.D. Silverman is offline   Reply With Quote
Reply

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 2018-03-11 23:20
Inverse of Smoothness Probability paul0 Math 6 2017-07-25 16:41
Quick smoothness test Sam Kennedy Programming 18 2013-01-21 14:23
Double check LL test faster than first run test lidocorc Software 3 2008-12-03 15:12
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 03:44.

Sun Apr 11 03:44:09 UTC 2021 up 2 days, 22:25, 1 user, load averages: 1.19, 1.27, 1.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.