20170618, 14:20  #1 
"Rashid Naimi"
Oct 2015
Remote to Here/There
7D6_{16} Posts 
Wheel Factorization
Hi all,
How does WheelFactorization compare to other methods in efficiency? In particular what are the more efficient deterministic factorization methods for general format numbers other than WeekFactoring? Thank you in advance. https://en.m.wikipedia.org/wiki/Wheel_factorization 
20170619, 00:04  #2 
Aug 2006
5985_{10} Posts 

20170619, 00:25  #3 
"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 cuberoot# +/ consecutive nextprimes to the cuberoot. 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 20170619 at 00:46 
20170619, 00:55  #4 
Aug 2006
3^{2}·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 mod6 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 216 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. 
20170619, 00:58  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20170619, 01:16  #6 
"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,61) \\ imagine this does not yield to justify continuation gcd(55,6+7) gcd(55,67)\\ usually the primorial will be much larger and not give negatives gcd(55,6+11) gcd(55,611)\\ 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 20170619 at 01:37 
20170619, 02:15  #7 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2006_{10} Posts 
This is what I was hoping to avoid.
Code:
print("BRT200ARNWheel.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 <n,{ print("Found a factor: ", theGcd ); }) \\Check +/1 m=thePrimorial +1; theGcd = gcd(n,m ); if (theGcd >1 && theGcd <n,{ print("Found a factor: ", theGcd ); }) m=thePrimorial 1; theGcd = gcd(n,m ); if (theGcd >1 && theGcd <n,{ print("Found a factor: ", theGcd ); }) \\ m=theCubeRoot; while(1==1,{ m=nextprime(m+1); theGcd = gcd(n,thePrimorial+m ); if (theGcd >1 && theGcd <n, print("Found a factor: ", theGcd ); next(19); ); theGcd = gcd(n,thePrimorialm ); if (theGcd >1 && theGcd <n, print("Found a factor: ", theGcd ); next(19); ); }) ## Code:
BRT200ARNWheel.gp By a1call timer = 1 (on) 2590875105391 [1507763 1] [1718357 1] *** last result computed in 0 ms. Found a factor: 1718357 time = 1,444 ms. *** last result computed in 1,444 ms. 
20170619, 03:29  #8 
Aug 2006
3^{2}×5×7×19 Posts 
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 moreorless 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."); 
20170619, 03:38  #9 
Aug 2006
3^{2}·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) 
20170619, 04:24  #10 
"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. 
20170619, 05:25  #11 
"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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factorization of RSA180  Robert Holmes  Factoring  19  20101108 18:46 
Factorization on 2^p +1  kurtulmehtap  Math  25  20100912 14:13 
Wheel factorization: Efficient?  3.14159  Miscellaneous Math  520  20100830 07:21 
A Wheel  storm5510  Puzzles  7  20100625 10:29 
Factorization of 7,254+  dleclair  NFSNET Discussion  1  20060321 05:11 