20220627, 11:04  #1 
Aug 2020
79*6581e4;3*2539e3
601 Posts 
Proth test performed by LLR
According to the rieselprime.de Wiki, LLR uses the Proth's theorem to test for primality of Proth numbers, i.e. finding a number a such that . To my understanding that would require testing all numbers a < p.
I can't link this to the LLR output, though. LLR seems to perform an algorithm with n steps, where n is the exponent. Similar to what you'd expect from an LL(R) test. Also, LLR has a fixed runtime, whereas a Proth test would have a random runtime within certain bounds. 
20220627, 11:12  #2  
Apr 2020
5^{3}×7 Posts 
Quote:
Finding such a value of a is easy, owing to quadratic reciprocity for Jacobi symbols. 

20220627, 11:44  #3 
Aug 2020
79*6581e4;3*2539e3
601 Posts 
Thanks, so the iteration LLR performs is calculating a(p1)/2 (mod p)?

20220627, 11:48  #4 
Apr 2020
5^{3}·7 Posts 

20220627, 12:26  #5 
Aug 2020
79*6581e4;3*2539e3
601 Posts 
Ok, makes sense. I forgot that it's possible to determine whether a is a quadratic nonresidue without calculating a^{(p1)/2} (mod p) at first.
Last fiddled with by bur on 20220627 at 12:27 
20220702, 16:09  #6 
"Alexander"
Nov 2008
The Alamo City
863 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primality test for Riesel and Proth prime ?  kijinSeija  Miscellaneous Math  10  20211208 13:26 
proth 2.0 use  masser  Conjectures 'R Us  5  20200908 20:31 
Efficient Proth/PRP Test Proof Scheme  patnashev  Number Theory Discussion Group  11  20200603 14:02 
The Jews built an altar dedicated to their third temple, and performed a sacrifice  jasong  jasong  5  20190106 15:16 
Proth Test Limits  amcfarlane  Math  1  20060723 18:29 