mersenneforum.org Proth test performed by LLR
 Register FAQ Search Today's Posts Mark Forums Read

 2022-06-27, 11:04 #1 bur     Aug 2020 79*6581e-4;3*2539e-3 5·109 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 $a^{(p-1)/2} \equiv -1 \pmod p$. 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.
2022-06-27, 11:12   #2
charybdis

Apr 2020

7·107 Posts

Quote:
 Originally Posted by bur 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 $a^{(p-1)/2} \equiv -1 \pmod p$. 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.
By Euler's criterion, if p is prime, then a(p-1)/2 is 1 mod p if a is a square mod p, and -1 mod p if a is not a square mod p. So it suffices to find a value of a that is not a square modulo the number we want to test; we are then guaranteed to get -1 if it is prime.

Finding such a value of a is easy, owing to quadratic reciprocity for Jacobi symbols.

 2022-06-27, 11:44 #3 bur     Aug 2020 79*6581e-4;3*2539e-3 10418 Posts Thanks, so the iteration LLR performs is calculating a(p-1)/2 (mod p)?
2022-06-27, 11:48   #4
charybdis

Apr 2020

7·107 Posts

Quote:
 Originally Posted by bur Thanks, so the iteration LLR performs is calculating a(p-1)/2 (mod p)?
Yes (I assume you meant a(p-1)/2). For k*2^n+1 this requires ~n squarings, hence the n iterations that LLR performs.

 2022-06-27, 12:26 #5 bur     Aug 2020 79*6581e-4;3*2539e-3 5×109 Posts Ok, makes sense. I forgot that it's possible to determine whether a is a quadratic non-residue without calculating a(p-1)/2 (mod p) at first. Last fiddled with by bur on 2022-06-27 at 12:27
2022-07-02, 16:09   #6
Happy5214

"Alexander"
Nov 2008
The Alamo City

11001011112 Posts

Quote:
 Originally Posted by bur Ok, makes sense. I forgot that it's possible to determine whether a is a quadratic non-residue without calculating a^(p-1)/2 (mod p) at first.
Um, that's (a^(p-1))/2, which is probably not what you meant ( a^((p-1)/2) ).

 Similar Threads Thread Thread Starter Forum Replies Last Post kijinSeija Miscellaneous Math 10 2021-12-08 13:26 masser Conjectures 'R Us 5 2020-09-08 20:31 patnashev Number Theory Discussion Group 11 2020-06-03 14:02 jasong jasong 5 2019-01-06 15:16 amcfarlane Math 1 2006-07-23 18:29

All times are UTC. The time now is 21:17.

Sun Jul 3 21:17:05 UTC 2022 up 80 days, 19:18, 0 users, load averages: 1.06, 1.20, 1.24