mersenneforum.org > Math Sublinear complexity of trial division?
 Register FAQ Search Today's Posts Mark Forums Read

 2018-02-02, 00:33 #1 yih117   Jan 2018 22 Posts 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?
2018-02-02, 00:46   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2018-02-02 at 00:51

2018-02-02, 00:55   #3
yih117

Jan 2018

22 Posts

Quote:
 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?

2018-02-02, 00:59   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2018-02-02 at 01:00

2018-02-02, 01:11   #5
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts

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

Quote:
 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.

Last fiddled with by Dubslow on 2018-02-02 at 01:11

2018-02-02, 02:49   #6
axn

Jun 2003

2·5·479 Posts

Quote:
 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).

 Similar Threads Thread Thread Starter Forum Replies Last Post mathPuzzles Math 8 2017-04-21 07:21 Peter Hackman Factoring 7 2009-10-26 18:27 SPWorley Math 8 2009-08-24 23:26 SPWorley Factoring 7 2009-08-16 00:23 ewmayer Factoring 7 2008-12-11 22:12

All times are UTC. The time now is 15:11.

Wed Dec 2 15:11:59 UTC 2020 up 83 days, 12:22, 2 users, load averages: 1.99, 1.94, 1.84