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 [I]a[/I] such that [TEX]a^{(p-1)/2} \equiv -1 \pmod p[/TEX]. To my understanding that would require testing all numbers [I]a < p[/I].

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.

[QUOTE=bur;608529]According to the rieselprime.de Wiki, LLR uses the Proth's theorem to test for primality of Proth numbers, i.e. finding a number [I]a[/I] such that [TEX]a^{(p-1)/2} \equiv -1 \pmod p[/TEX]. To my understanding that would require testing all numbers [I]a < p[/I].

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.[/QUOTE]

By [URL="https://en.wikipedia.org/wiki/Euler%27s_criterion"]Euler's criterion[/URL], if p is prime, then a[SUP](p-1)/2[/SUP] 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 [URL="https://en.wikipedia.org/wiki/Quadratic_reciprocity#Jacobi_symbol"]quadratic reciprocity for Jacobi symbols[/URL].

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

[QUOTE=bur;608534]Thanks, so the iteration LLR performs is calculating a(p-1)/2 (mod p)?[/QUOTE]

Yes (I assume you meant a[SUP](p-1)/2[/SUP]). For k*2^n+1 this requires ~n squarings, hence the n iterations that LLR performs.

Ok, makes sense. I forgot that it's possible to determine whether [I]a[/I] is a quadratic non-residue without calculating a[SUP](p-1)/2[/SUP] (mod p) at first.

[QUOTE=bur;608537]Ok, makes sense. I forgot that it's possible to determine whether [I]a[/I] is a quadratic non-residue without calculating [B]a^(p-1)/2[/B] (mod p) at first.[/QUOTE]

Um, that's ([I]a[/I]^([I]p[/I]-1))/2, which is probably not what you meant ( [I]a[/I]^(([I]p[/I]-1)/2) ).