Proth test performed by LLR

bur · 2022-06-27, 11:04

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.

charybdis · 2022-06-27, 11:12

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.

bur · 2022-06-27, 11:44

Thanks, so the iteration LLR performs is calculating a(p-1)/2 (mod p)?

charybdis · 2022-06-27, 11:48

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.

bur · 2022-06-27, 12:26

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.

Happy5214 · 2022-07-02, 16:09

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) ).

2022-06-27, 11:04	#1
bur Aug 2020 796581e-4;32539e-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, 12:26	#5
bur Aug 2020 796581e-4;32539e-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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Primality test for Riesel and Proth prime ?	kijinSeija	Miscellaneous Math	10	2021-12-08 13:26
proth 2.0 use	masser	Conjectures 'R Us	5	2020-09-08 20:31
Efficient Proth/PRP Test Proof Scheme	patnashev	Number Theory Discussion Group	11	2020-06-03 14:02
The Jews built an altar dedicated to their third temple, and performed a sacrifice	jasong	jasong	5	2019-01-06 15:16
Proth Test Limits	amcfarlane	Math	1	2006-07-23 18:29

2022-06-27, 11:44	#3
bur Aug 2020 796581e-4;32539e-3 1041₈ Posts	Thanks, so the iteration LLR performs is calculating a(p-1)/2 (mod p)?