mersenneforum.org  

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

Reply
 
Thread Tools
Old 2016-11-24, 08:26   #1
xsx
 
Nov 2016

1 Posts
Exclamation Are it possible?

How check it formula (8191 + 1) / 4(or any other depending on 8191) , is an remainder of the division division "Lucas - lehtera primality test"?
(4^2-2)mod 8191=14
(14^2-2)mod 8191=194
(194^2-2)mod 8191=4870
(4870^2-2)mod 8191=3953
(3953^2-2)mod 8191=5970
(5970^2-2)mod 8191=1857
(1857^2-2)mod 8191=36
(36^2-2)mod 8191=1294
(1294^2-2)mod 8191=3470
(3470^2-2)mod 8191=128
(128^2-2)mod 8191=0
xsx is offline   Reply With Quote
Old 2016-11-24, 11:52   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×5×107 Posts
Default

Quote:
Originally Posted by xsx View Post
How check it formula (8191 + 1) / 4(or any other depending on 8191) , is an remainder of the division division "Lucas - lehtera primality test"?
(4^2-2)mod 8191=14
(14^2-2)mod 8191=194
(194^2-2)mod 8191=4870
(4870^2-2)mod 8191=3953
(3953^2-2)mod 8191=5970
(5970^2-2)mod 8191=1857
(1857^2-2)mod 8191=36
(36^2-2)mod 8191=1294
(1294^2-2)mod 8191=3470
(3470^2-2)mod 8191=128
(128^2-2)mod 8191=0
It's called the "Lucas Lehmer" test.

It checks only numbers of the form 2^p-1. (We know p must be a prime too.)

What you described is the LL test for 2^13-1 which is 8191, and is prime

Last fiddled with by paulunderwood on 2016-11-24 at 11:59
paulunderwood is online now   Reply With Quote
Old 2016-11-25, 03:31   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100111011011102 Posts
Default

I think his/her question is "how to check if some number (example: (8191+1)/4=8192/4=2048 given by OP) appears as a residue in the set of some LL test residues" (example LL test for M13 given by OP).

Answer: you can not, unless you do all the LL test "da capo al fine" (from the beginning to the end).

If that would be possible, then you would have a "shortcut" to do the LL test in only two iterations, by checking if either (Mp+1)/2 or its negative appears in the residue list. This can only happen if Mp is prime.

Last fiddled with by LaurV on 2016-11-25 at 03:33
LaurV is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 07:49.


Tue Sep 27 07:49:11 UTC 2022 up 40 days, 5:17, 0 users, load averages: 1.02, 1.11, 1.14

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.

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