How does trial-factoring work?

[ThomRuley]

I had a quick question about how the trial-factoring in Prime95 works. Does the program trial-divide by prime numbers in order or does it try them randomly until one works? :?

[Axel Fox]

Trial factoring tries all possible dividers up to a certain limit, which depends on the exponent you are testing (or which you set yourself with the FactorOverride option).

However, not all prime numbers are tried, because there is a theorem that if a number divides a Mersenne number, it MUST be of the form

2*k*p+1 where p is the exponent of the number you are testing. So it only tries to devide the Mersenne by these kind of numbers.

How the program tries to divide it exactly, I don't know myself. I don't know the exact algorithm for it, but I know that it is waaaay faster than just trying to numerically divide it.

Axel Fox.

[cheesehead]

Prime95 trial-factoring is orderly. It's designed to ensure that once it reports that there's no factor up to 2^m, it really does mean that no potential factor below 2^m divides the Mnumber it tested, so any factor of that Mnumber must be greater than 2^m.

[smh]

Prime95 trial-factoring is orderly.

I'm not sure about this. I remember from the old days that the client used 16 passes while trail factoring. I believe those 16 passes are still in there.

The program does however try all numbers below a bit length before moving to the next though.

Below is a message from George to the mersenne mailing list on 08 may 1996

Hi all,

David M. Einstein writes:
> I see that your new version is facoring in two passes. I assume that
these
> are numbers +-1 mod 8.

Your guess is correct. For those of you wondering why this is a
good idea - consider a one pass algorithm that first clears every
3 mod 8 and 5 mod 8 sieve bit. Then you clear every 3rd bit, every
5th bit, etc. Well, half the time you clear a bit because it it a multiple
of 3, 5, 7, etc. it was already cleared because the factor was 3 mod 8
or 5 mod 8. The two pass approach avoids this waste by using
two sieves, one for the 1 mod 8 factors and another for the 7 mod 8
factors.

> Would it be worthwhile to do it in 16 passes with numbers
> +-1 mod 8, +-1 mod 3, +-1,2 mod 5, or even in two stages say first seiving the
> interval from 0 to 8*3*5*7*11*13, and then seiving the residue classes found
in the
> first pass mod the other primes before 'trial dividing', or would the cost of
> reinitializing the seive be too great?

Good idea! It's already on my to-do list. If I remember correctly, 20% of the
time
spent factoring is attributed to the cost of sieving. Thus going to a four pass
approach would save 1/3 of 20% or about 7%. A 16-pass approach would save
a total of 9.3%. The cost of reinitializing the sieve is not that great. As
was pointed
out earlier, doubling the factoring speed results in a 2% overall improvement,
so
this item is not high on my priority list.

Regards,
George

[NickGlover]

Originally Posted by Axel Fox

How the program tries to divide it exactly, I don't know myself. I don't know the exact algorithm for it, but I know that it is waaaay faster than just trying to numerically divide it.

The algorithm is described at the top of The GIMPS Math page.

[cheesehead]

I'm not sure about this. I remember from the old days that the client used 16 passes while trail factoring. I believe those 16 passes are still in there.

That's why I wrote "orderly" rather than "sequentially" or "strictly linearly". :)

And if no factor is found, then the progress as measured at the standard powers-of-2 breakpoints is sequential.