mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2019-11-05, 20:05   #23
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

22·3·7·139 Posts
Default

Quote:
Originally Posted by Dan Ee View Post
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.
ewmayer is offline   Reply With Quote
Old 2019-11-06, 13:27   #24
Dan Ee
 
Mar 2013

78 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
Dan Ee is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Requestion for fast chebyshev theta function danaj Computer Science & Computational Number Theory 9 2018-03-31 14:59
Do normal adults give themselves an allowance? (...to fast or not to fast - there is no question!) jasong jasong 35 2016-12-11 00:57
Fast modular reduction for primes < 512 bits? BenR Computer Science & Computational Number Theory 2 2016-03-27 00:37
Fast Approximate Ceiling Function R.D. Silverman Programming 27 2010-11-19 17:50
Base-6 speed for prime testing vs. base-2 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.