• Create Account

### #ActualBacterius

Posted 27 October 2012 - 08:53 PM

Also, trial division isn't the only way to factorize numbers. Basically, factoring is a difficult problem, and it is in fact infeasible to do it when the prime factors are larger than a few hundred digits. Fortunately, you're not dealing with such large numbers.

I would expect Project Euler to specifically choose a large number to prevent you from using trial division, forcing you to implement a better algorithm. Look into Pollard's rho algorithm, or Pollard's p + 1. There's also a continued fraction algorithm (SQUFOF) which is somewhat arcane, but works. Quadratic sieve is the next step up but is considerably harder to implement. Number Field Sieve (NFS) is state-of-the-art but good luck implementing that, seriously. You can also look into elliptic curve factorization (elliptic curve method or ECM for short) which is pretty good for average-size factors but is a bit tricky to get right and difficult to understand - you need to understand elliptic curves.

For reference, quadratic sieve can factorize a 100-digit semiprime into two 50-digit primes in four hours or so. Trial division would have done the same in, say, a few trillion years.

All of this is probably overkill for 64-bit integers though.

### #4Bacterius

Posted 27 October 2012 - 08:50 PM

Also, trial division isn't the only way to factorize numbers. Basically, factoring is a difficult problem, and it is in fact infeasible to do it when the prime factors are larger than a few hundred digits. Fortunately, you're not dealing with such large numbers.

I would expect Project Euler to specifically choose a large number to prevent you from using trial division, forcing you to implement a better algorithm. Look into Pollard's rho algorithm, or Pollard's p + 1. There's also a continued fraction algorithm (SQUFOF) which is somewhat arcane, but works. Quadratic sieve is the next step up but is considerably harder to implement. Number Field Sieve (NFS) is state-of-the-art but good luck implementing that, seriously. You can also look into elliptic curve factorization (elliptic curve method or ECM for short) which is pretty good for average-size factors but is a bit tricky to get right and difficult to understand - you need to understand elliptic curves.

For reference, quadratic sieve can factorize a 100-digit semiprime into two 50-digit primes in four hours or so. Trial division would have done the same in, say, a few trillion years.

### #3Bacterius

Posted 27 October 2012 - 08:50 PM

Also, trial division isn't the only way to factorize numbers. Basically, factoring is a difficult problem, and it is in fact infeasible to do it when the prime factors are larger than a few hundred digits. Fortunately, you're not dealing with such large numbers.

I would expect Project Euler to specifically choose a large number to prevent you from using trial division, forcing you to implement a better algorithm. Look into Pollard's rho algorithm, or Pollard's p + 1. There's also a continued fraction algorithm (SQUFOF) which is somewhat arcane, but works. Quadratic sieve is the next step up but is considerably harder to implement. Number Field Sieve (NFS) is state-of-the-art but good luck implementing that, seriously. You can also look into elliptic curve factorization (elliptic curve method or ECM for short) which is pretty good for average-size factors but is a bit tricky to get right and difficult to understand - you need to understand elliptic curves.

For reference, quadratic sieve can factorize a 100-digit semiprime into two 50-digit primes in four hours or so. Trial division would have done the same in, say, a few trillion years.

### #2Bacterius

Posted 27 October 2012 - 08:50 PM

Also, trial division isn't the only way to factorize numbers. Basically, factoring is a difficult problem, and it is in fact infeasible to do it when the prime factors are larger than a few hundred digits. Fortunately, you're not dealing with such large numbers.

I would expect Project Euler to specifically choose a large number to prevent you from using trial division, forcing you to implement a better algorithm. Look into Pollard's rho algorithm, or Pollard's p + 1. There's also a continued fraction algorithm (SQUFOF) which is somewhat arcane, but works. Quadratic sieve is the next step up but is considerably harder to implement. Number Field Sieve (NFS) is state-of-the-art but good luck implementing that, seriously. You can also look into elliptic curve factorization (elliptic curve method or ECM for short) which is pretty good for average-size factors but is a bit tricky to get right and difficult to understand - you need to understand elliptic curves.

For reference, quadratic sieve can factorize a 100-digit number in four hours or so. Trial division would have done the same in, say, a few trillion years.

### #1Bacterius

Posted 27 October 2012 - 08:49 PM

Also, trial division isn't the only way to factorize numbers. Basically, factoring is a difficult problem, and it is in fact infeasible to do it when the prime factors are larger than a few hundred digits. Fortunately, you're not dealing with such large numbers.

I would expect Project Euler to specifically choose a large number to prevent you from using trial division, forcing you to implement a better algorithm. Look into Pollard's rho algorithm, or Pollard's p + 1. There's also a continued fraction algorithm (SQUFOF) which is somewhat arcane, but works. Quadratic sieve is the next step up but is considerably harder to implement. Number Field Sieve (NFS) is state-of-the-art but good luck implementing that, seriously. You can also look into elliptic curve factorization (elliptic curve method or ECM for short) which is pretty good for average-size factors but is a bit tricky to get right and difficult to understand - you need to understand elliptic curves.

PARTNERS