Wheel Factorization

[a1call]

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

[CRGreathouse]

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?

[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.

[CRGreathouse]

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.

[science_man_88]

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.

[a1call]

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.

[a1call]

This is what I was hoping to avoid.

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 <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,thePrimorial-m );
  if (theGcd >1 && theGcd <n,
    print("Found a factor: ", theGcd );
    next(19);
  );

})
##

BRT-200-A-RN-Wheel.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.

[CRGreathouse]

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:

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.");

[CRGreathouse]

A naive implementation of my suggestions, below, gives around a 20x speedup on your sample number (56ms on my machine).

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)

[a1call]

That is cool, neat and novel. I get:

(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.

[a1call]

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.