20200317, 13:23  #12 
Mar 2007
Estonia
2×67 Posts 
Prime95, LLR64, and even my own implementation use the gwnum library for the core multiplication/subtraction/modulus, not the builtin %, which works only on native ints. Before I wrote my final implementation I created a demo in Python, with GMP doing the heavy lifting. This solution was several times slower than the final compiled+gwnum solution. This is due to relatively slow loops in Python (an issue Java shouldn't have due to probably effective jiting of loops), but GMP itself was too slow for this exact problem. gwnum handles the 2 almost for free, and it's geared towards being very good with multiplication/products mod N. Also it transfers some info from one multiplication to the next (with some special calls) which also speeds it up. Naive solutions are going to be dead slow. gwnum also parallelizes the calculation, uses intrinsics and uses handwritten assembly for the FFT.
Last fiddled with by kuratkull on 20200317 at 13:37 
20200317, 13:24  #13 
Jun 2003
11×421 Posts 
Have you tried implementing S mod Mp as (S & Mp) + (S >> p) ? This ought to be much faster than generic Java biginteger mod. Then you can add additional safety checks to your heart's content.

20200317, 13:24  #14  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{3}·691 Posts 
Quote:


20200317, 13:33  #15  
Nov 2017
Karlsruhe, Germany
31 Posts 
Quote:
Quote:
Quote:
Though keep in mind that there will always be legitemate reasons to calculate LL in pure Java. 

20200317, 13:45  #16 
Nov 2017
Karlsruhe, Germany
31 Posts 
That calculation does not seem to work.
Last fiddled with by BrainStone on 20200317 at 13:53 
20200317, 15:20  #17 
Jun 2003
11·421 Posts 
Can you post your code snippet?
EDIT: For some values, you might have to do a second reduction. Last fiddled with by axn on 20200317 at 15:29 
20200317, 15:43  #18  
Nov 2003
2×3×17×73 Posts 
Quote:
Why post in the math subforum?? Your question is not mathrelated. There is a programming subforum. Use it instead. 

20200317, 15:44  #19  
Nov 2017
Karlsruhe, Germany
31 Posts 
Quote:
Code:
public static final BigInteger fastMod(BigInteger number, BigInteger candidate, int prime) { return number.and(candidate).add(number.shiftRight(prime)); } Last fiddled with by BrainStone on 20200317 at 15:46 

20200317, 15:47  #20 
Nov 2017
Karlsruhe, Germany
31 Posts 
Because my question is if there's ever a case where \(S(n) \equiv 1 \mod M_p\). Why I am asking this is merely giving context.
Last fiddled with by BrainStone on 20200317 at 15:48 
20200317, 15:51  #21  
Nov 2003
2×3×17×73 Posts 
Quote:


20200317, 15:58  #22  
Sep 2002
Database er0rr
13·251 Posts 
Quote:
Last fiddled with by paulunderwood on 20200317 at 15:58 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
A second proof for the LucasLehmer Test  carpetpool  Miscellaneous Math  2  20170730 09:21 
LucasLehmer test  Mathsgirl  Information & Answers  23  20141210 16:25 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
Lucas Lehmer test question?  BMgf  Programming  23  20031209 08:52 