Sublinear complexity of trial division?
 

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?

[QUOTE=yih117;479040]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?[/QUOTE]

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

[QUOTE=science_man_88;479041]False, mersenne factors for prime exponents have special form that varies in relation to exponent.[/QUOTE]

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?

[QUOTE=yih117;479043]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?[/QUOTE]

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

That thread is an excellent reference for the detailed optimizations level, but the simpler more overarching concept is [URL="https://www.mersenne.org/various/math.php"]this[/URL]:

[quote]One very nice property of Mersenne numbers is that [B]any factor q of 2^p-1 must be of the form 2kp+1[/B]. 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.[/quote]

The bold part is the important part: the factor [I]candidates[/I] themselves are size O(p). Therefore, within a given bit range, for an exponent x ~ 2p, there are half as many factor [I]candidates[/I] for x as there are for p. So, in effect yes, your observation is correct, [I]for a given bit range[/I] 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.

[QUOTE=yih117;479043]So does that mean that there is some overhead to prepare a special table of potential prime factors for each exponent?[/QUOTE]

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