mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2022-06-27, 11:04   #1
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

25916 Posts
Default 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.
bur is offline   Reply With Quote
Old 2022-06-27, 11:12   #2
charybdis
 
charybdis's Avatar
 
Apr 2020

23×107 Posts
Default

Quote:
Originally Posted by bur View Post
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.
charybdis is offline   Reply With Quote
Old 2022-06-27, 11:44   #3
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

601 Posts
Default

Thanks, so the iteration LLR performs is calculating a(p-1)/2 (mod p)?
bur is offline   Reply With Quote
Old 2022-06-27, 11:48   #4
charybdis
 
charybdis's Avatar
 
Apr 2020

23×107 Posts
Default

Quote:
Originally Posted by bur View Post
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.
charybdis is offline   Reply With Quote
Old 2022-06-27, 12:26   #5
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

601 Posts
Default

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
bur is offline   Reply With Quote
Old 2022-07-02, 16:09   #6
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

34616 Posts
Default

Quote:
Originally Posted by bur View Post
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) ).
Happy5214 is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 14:56.


Fri Sep 30 14:56:11 UTC 2022 up 43 days, 12:24, 0 users, load averages: 1.30, 1.32, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔