Sublinear complexity of trial division?

[yih117]

I noticed that for trial division in a given range (2^68 - 2^69 for example), larger exponents seem to take less time (and are awarded with less GHz * Days). I assume that the divisors remain the same since they come from the same range. What optimization does Prime95 use to make division a sublinear time operation?

[science_man_88]

Originally Posted by yih117

I noticed that for trial division in a given range (2^68 - 2^69 for example), larger exponents seem to take less time (and are awarded with less GHz * Days). I assume that the divisors remain the same since they come from the same range. What optimization does Prime95 use to make division a sublinear time operation?

False, mersenne factors for prime exponents have special form that varies in relation to exponent.

[yih117]

Originally Posted by science_man_88

False, mersenne factors for prime exponents have special form that varies in relation to exponent.

Ah thanks, this explains everything. So does that mean that there is some overhead to prepare a special table of potential prime factors for each exponent?

[science_man_88]

Originally Posted by yih117

Ah thanks, this explains everything. So does that mean that there is some overhead to prepare a special table of potential prime factors for each exponent?

I'm not the maker of the software. But you can look at:http://www.mersenneforum.org/showthread.php?t=17126 for some basic idea of how some software may do this.

[Dubslow]

That thread is an excellent reference for the detailed optimizations level, but the simpler more overarching concept is this:

One very nice property of Mersenne numbers is that any factor q of 2^p-1 must be of the form 2kp+1. Furthermore, q must be 1 or 7 mod 8. A proof is available. Finally, an efficient program can take advantage of the fact that any potential factor q must be prime.

The bold part is the important part: the factor candidates themselves are size O(p). Therefore, within a given bit range, for an exponent x ~ 2p, there are half as many factor candidates for x as there are for p. So, in effect yes, your observation is correct, for a given bit range against a varying exponent p, difficulty goes as the number of candidates goes as O(1/p).

But the actual division itself of the candidates is linear in the number of candidates, same as for non-Mersenne numbers.

[axn]

Originally Posted by yih117

So does that mean that there is some overhead to prepare a special table of potential prime factors for each exponent?

Yes. However, this overhead is less than preparing a general table of prime factors in the given range (say, 2^68-2^69).