mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2017-06-18, 14:20   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7D616 Posts
Default 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
a1call is offline   Reply With Quote
Old 2017-06-19, 00:04   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

598510 Posts
Default

Quote:
Originally Posted by a1call View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2017-06-19, 00:25   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×17×59 Posts
Default

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
a1call is offline   Reply With Quote
Old 2017-06-19, 00:55   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2017-06-19, 00:58   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-06-19, 01:16   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·17·59 Posts
Default

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
a1call is offline   Reply With Quote
Old 2017-06-19, 02:15   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

200610 Posts
Default

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

})
##
Code:
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.
a1call is offline   Reply With Quote
Old 2017-06-19, 03:29   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by a1call View Post
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.");
CRGreathouse is offline   Reply With Quote
Old 2017-06-19, 03:38   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

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)
CRGreathouse is offline   Reply With Quote
Old 2017-06-19, 04:24   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×17×59 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2017-06-19, 05:25   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·17·59 Posts
Default

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.
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factorization of RSA-180 Robert Holmes Factoring 19 2010-11-08 18:46
Factorization on 2^p +1 kurtulmehtap Math 25 2010-09-12 14:13
Wheel factorization: Efficient? 3.14159 Miscellaneous Math 520 2010-08-30 07:21
A Wheel storm5510 Puzzles 7 2010-06-25 10:29
Factorization of 7,254+ 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

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.