mersenneforum.org Wheel Factorization
 Register FAQ Search Today's Posts Mark Forums Read

 2017-06-18, 14:20 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 7D616 Posts Wheel Factorization Hi all, How does Wheel-Factorization compare to other methods in efficiency? In particular what are the more efficient deterministic factorization methods for general format numbers other than Week-Factoring? Thank you in advance. https://en.m.wikipedia.org/wiki/Wheel_factorization
2017-06-19, 00:04   #2
CRGreathouse

Aug 2006

598510 Posts

Quote:
 Originally Posted by a1call How does Wheel-Factorization compare to other methods in efficiency?]
I'm not clear on what you're asking it to do. Are you trying to factor a single number or a range of numbers? If the latter, how large is the range?

 2017-06-19, 00:25 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×17×59 Posts Thank you for the replies on both threads. And apologies for not being clear on the reference on other thread. I kind of got at least one example from Batalov on the other thread to my question on this thread. My reason for asking this question was that, I kind of reinvented the wheel (concept), and was about to write a program to find a primorial up to say cube root of n and then GCD test n and the cube-root# +/- consecutive next-primes to the cube-root. Then I remembered that this happens to be precisely what wheel factorization is. I was looking for further excuses/confirmation as to why I shouldn't spent hours reinventing the wheel. Please feel free to delete this thread if it does not compile any useful lists of faster algorithms of genteel factorization which was its original purpose. Last fiddled with by a1call on 2017-06-19 at 00:46
 2017-06-19, 00:55 #4 CRGreathouse     Aug 2006 32·5·7·19 Posts So let me see if I understand. You're suggesting picking a number around the cube root of the number to be factored and taking the product of primes up to that number, then taking the GCD of the primorial with your original number. If that doesn't work, you'll take another chunk of primes and take their product, check GCD, and so on until you find a factor. So this isn't really wheel factorization, it's trial division which is one step more advanced, in a sense: you're not using all the numbers on a wheel, just the primes. (If you used a mod-6 wheel, for example, you'd divide by 49 even though it's composite and covered by 7.) Now if you have a good, i.e. subquadratic, GCD algorithm you can get some improvements by shifting from testing one prime at a time to a batch of primes with one GCD. But the cube root of the number is probably too big unless you're using factor trees (in which case I'm not sure what a good size would be). Normally I would expect 2-16 would be a better number of primes, very much smaller than the number you'd find up to the cube root unless your numbers were tiny.
2017-06-19, 00:58   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by a1call Thank you for the replies on both threads. And apologies for not being clear on the reference on other thread. I kind of got at least one example from Batalov on the other thread to my question on this thread. My reason for asking this question was that, I kind of reinvented the wheel (concept), and was about to write a program to find a primorial up to say cube root of n and then GCD test n and the cube-root# +/- consecutive next-primes to the cube-root. Then I remembered that this happens to be precisely what wheel factorization is. I was looking for further excuses/confirmation as to why I shouldn't spent hours reinventing the wheel. Please feel free to delete this thread if it does not compile any useful lists of faster algorithms of genteel factorization which was its original purpose.
I think the problem being asked by CRG is one about statements you made you talk about wheel factorization but that's for a range of numbers to be factored or disproved prime at very least where as say a normal factorization of a single number is different for ranges you can use sieves like the sieve of Eratosthenes, the sieve of Sundaram, the sieve of Atkin, Euler's sieve, etc. for a single number it's mostly primality tests or things like Pollard's P-1, P+1, others that are mostly useful for specific form numbers I think.

 2017-06-19, 01:16 #6 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·17·59 Posts To factor 55, sqrtnint(55,3)=3 3#=6 \\check primorial for common factor gcd(55,6) \\Check the wheel up to nextprime < sqrtint(n) gcd(55,6+1) gcd(55,6-1) \\ imagine this does not yield to justify continuation gcd(55,6+7) gcd(55,6-7)\\ usually the primorial will be much larger and not give negatives gcd(55,6+11) gcd(55,6-11)\\ usually the primorial will be much larger and not give negatives ..... I still think with the exception of setting the cube root it is precisely equivalent to wheel factorization. Like wheel factorization it will generate all the numbers which are coprime (and no numbers with common factors to it) to the primorial, If it continues to the sum of (primorial+/nextprime) >= sqrtint(n) it is deterministic. Last fiddled with by a1call on 2017-06-19 at 01:37
 2017-06-19, 02:15 #7 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 200610 Posts This is what I was hoping to avoid. Code: print("BRT-200-A-RN-Wheel.gp\nBy a1call") # theExp = 5;\\larger integers will enlarge random n \\\ primorial(n)= { my(thePrimorial=1); forprime(p=2,n,thePrimorial=thePrimorial*p); return (thePrimorial); } \\\ n=nextprime(random(19^theExp ))*nextprime(random(19^theExp )) factor(n) ## \\The wheel theCubeRoot = sqrtnint(n,3); thePrimorial = primorial(theCubeRoot ); theGcd = gcd(n,thePrimorial ); if (theGcd >1 && theGcd 1 && theGcd 1 && theGcd 1 && theGcd 1 && theGcd
2017-06-19, 03:29   #8
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by a1call This is what I was hoping to avoid.
There's a good method -- well, a decent method -- hiding here underneath what you have presently.

Yes, I agree that this version is not very good. It starts out by knocking out a swath of small primes (up to the cube root). This step needs tuning -- for large inputs, you're doing too much all in one go, and your code to compute the primorial is slow because of the way the multiplies accumulate -- but it's essentially good. But after that you go into the weeds, stepping through the primorial +/- p for small primes p. But primorials +/- p don't have useful divisibility properties, so the program just spends a long time here until it happens across a prime more-or-less at random.

What I had suggested above is that rather than do something completely different, just continue what you were doing. You searched for primes from 1 to x (where x is the cube root of the number to be factored), so now search for primes from x+1 to 2x, then from 2x+1 to 3x, and so on. So just multiply the appropriate primes and take the gcd.

You should use binary splitting to compute the products of primes. In GP, something like this:
Code:
primeProduct(from, to)=producttree(primes([from,to]));
addhelp(primeProduct, "primeProduct(from, to): Gives the product of primes in the range [from, to] inclusive.");

producttree(v)=
{
if (#v < 4, return(factorback(v)));
my(middle=#v\2);
producttree(v[1..middle])*producttree(v[middle+1..#v]);
}
addhelp(producttree, "producttree(v): Returns the product of the elements of the vector v, using binary splitting.");

 2017-06-19, 03:38 #9 CRGreathouse     Aug 2006 32·5·7·19 Posts A naive implementation of my suggestions, below, gives around a 20x speedup on your sample number (56ms on my machine). Code: trialBlock(n)=my(block=sqrtnint(n,3),last=2,t); forstep(k=block,sqrtint(n),block, t=gcd(primeProduct(last,k),n); if(t>1, if(t==n, warning("All factors in range "last" to "k)); return(t)); last=k)
 2017-06-19, 04:24 #10 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×17×59 Posts That is cool, neat and novel. I get: Code: (00:17) gp > trialBlock(2590875105391) %6 = 1507763 (00:19) gp > # timer = 1 (on) (00:19) gp > trialBlock(2590875105391) time = 281 ms.` But I don't think it is Wheel-Factorization. Then again I was looking for algos which were faster and this qualifies.
 2017-06-19, 05:25 #11 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·17·59 Posts Ok I just realized what you where saying. My wheel is missing rotation. By nullifying the x you only need to use the primes less than x. I stand corrected. That would be the proper wheel.

 Similar Threads Thread Thread Starter Forum Replies Last Post Robert Holmes Factoring 19 2010-11-08 18:46 kurtulmehtap Math 25 2010-09-12 14:13 3.14159 Miscellaneous Math 520 2010-08-30 07:21 storm5510 Puzzles 7 2010-06-25 10:29 dleclair NFSNET Discussion 1 2006-03-21 05:11

All times are UTC. The time now is 14:51.

Wed Apr 14 14:51:24 UTC 2021 up 6 days, 9:32, 0 users, load averages: 2.24, 1.75, 1.67