mersenneforum.org A fast C/C++ function for base-2 modular exponentation
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2019-11-05, 20:05   #23
ewmayer
2ω=0

Sep 2002
República de California

22·3·7·139 Posts

Quote:
 Originally Posted by Dan Ee I think I may have a slightly different method for doing Mersenne number trial division that you can test in your project. This method can be summarized as "Negative power base-2 modular exponentiation using Montgomery reduction." Instead of computing Mod(2,m)^q and test whether the result is 1, we can compute Mod(2,m)^-q and test whether the result is 1.
That sounds like my Algorithm E here. It's the algo I use in my own Mersenne and Fermat TF code, and also used to find the fourth-known factor of the double mersenne MM31.

2019-11-06, 13:27   #24
Dan Ee

Mar 2013

78 Posts

Quote:
 Originally Posted by ewmayer That sounds like my Algorithm E here. It's the algo I use in my own Mersenne and Fermat TF code, and also used to find the fourth-known factor of the double mersenne MM31.
You are right. One possible minor improvement is to use MMUL_ONE at the beginning to get to negative power. For example 2^-977, start from 2^-1, MMUL_ONE to get 2^-65, then 3 MONT_SQR iterations: 2^-194, 2^-452, 2^-968.
Also, consider using mod-halvings, or even mixing mod-halvings and mod-doublings. When implemented well, I believe the worst case scenario will not have an extra loop iteration compared to positive-powering ladder.

 Similar Threads Thread Thread Starter Forum Replies Last Post danaj Computer Science & Computational Number Theory 9 2018-03-31 14:59 jasong jasong 35 2016-12-11 00:57 BenR Computer Science & Computational Number Theory 2 2016-03-27 00:37 R.D. Silverman Programming 27 2010-11-19 17:50 jasong Conjectures 'R Us 36 2010-08-03 06:25

All times are UTC. The time now is 02:43.

Mon Dec 6 02:43:01 UTC 2021 up 135 days, 21:12, 0 users, load averages: 0.95, 1.11, 1.28