mersenneforum.org  

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

Reply
 
Thread Tools
Old 2005-05-12, 15:50   #1
Holmes
 

52×241 Posts
Question PRP => LL-tests?

hi,

a short, maybe silly question:

i know how the LucasLehmer test works for Mersennes (S(n+1)=S(n)^2-2 mod 2^n-1, S(1)=4 etc. ).

But how it works for a general numbers like a*b^n-1?

Or the algorithm used in PRP3.exe isn't related to LL-tests? If it isn't, may i kindly ask for a short explanation or a link to such?

J. HOlmes
  Reply With Quote
Old 2005-05-13, 17:18   #2
Washuu
 
Mar 2005
Poland

5×7 Posts
Lightbulb

Quote:
Originally Posted by Holmes
...
But how it works for a general numbers like a*b^n-1?

Or the algorithm used in PRP3.exe isn't related to LL-tests? If it isn't, may i kindly ask for a short explanation or a link to such?
Sure. First of all - take look at this page (but whole site is worth of reading): http://primes.utm.edu/prove/index.html.

The theorem used in testing number as Probable Prime is Fermat Little Theorem.

Fermat's Little Theorem: If p is a prime and if a is any integer, then a^p = a (mod p). In particular, if p does not divide a, then a^(p-1) = 1 (mod p).

In most cases we choose a=2, as multiplying by 2 is very simple in binary system, used by computers. This test gives only certainty of number being composite in 99% cases (when 2^(p-1) != 2 mod p), and pretty good PROBABILITY of number being prime, if 2^(p-1) = 1 mod p.

One of algorithm for PROVING primarility of n follows:

Let n > 1. If for every prime factor q of n-1 there is an integer a such that

* a(n-1) = 1 (mod n), and
* a(n-1)/q is not 1 (mod n);

then n is prime.

That should be enough for now, come back here when you read mentioned webpage :)

Regards,

Washuu
Washuu is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Run P-1 before PRP tests alpertron Software 35 2018-02-27 16:01
p4 - 1.8 ghz - LL tests? joblack Hardware 12 2009-08-26 20:40
More P-1 tests dave_0273 Marin's Mersenne-aries 1 2006-03-23 00:03
Yet another set of 20 P-1 tests GP2 Completed Missions 5 2003-09-30 22:10
Bad LL Tests outlnder Lounge 8 2002-10-21 00:12

All times are UTC. The time now is 03:54.


Wed Jun 29 03:54:01 UTC 2022 up 76 days, 1:55, 1 user, load averages: 1.30, 1.21, 1.22

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.

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