mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-02-02, 00:33   #1
yih117
 
Jan 2018

22 Posts
Default 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?
yih117 is offline   Reply With Quote
Old 2018-02-02, 00:46   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by yih117 View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-02-02, 00:55   #3
yih117
 
Jan 2018

22 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
yih117 is offline   Reply With Quote
Old 2018-02-02, 00:59   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by yih117 View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-02-02, 01:11   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts
Default

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
Dubslow is offline   Reply With Quote
Old 2018-02-02, 02:49   #6
axn
 
axn's Avatar
 
Jun 2003

2·5·479 Posts
Default

Quote:
Originally Posted by yih117 View Post
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).
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne trial division implementation mathPuzzles Math 8 2017-04-21 07:21
trial division over a factor base Peter Hackman Factoring 7 2009-10-26 18:27
P95 trial division strategy SPWorley Math 8 2009-08-24 23:26
Trial division software for Mersenne SPWorley Factoring 7 2009-08-16 00:23
Need GMP trial-division timings 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.