mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-08-12, 18:50   #1
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

14208 Posts
Default Primality testing of numbers k*b^n+c

I know that Riesel and Proth tests are used for numbers k*2^n-1 and k*2^n+1 respectively. I have found the names of tests for k*b^n-c and k*b^n+c (Pocklington and Morrison algorithm respectively). All four work for k < b^n. Here it says, that number with |c| > 1 or k > b^n can only be PRP tested.

My questions are:
  1. How do the Pocklington and Morrison tests work?
  2. Why is there a restriction on the size of k?
  3. Why is it so bad with the rest? (|c| > 1, k > b^n)
Viliam Furik is offline   Reply With Quote
Old 2020-08-12, 18:57   #2
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

3,643 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
I know that Riesel and Proth tests are used for numbers k*2^n-1 and k*2^n+1 respectively. I have found the names of tests for k*b^n-c and k*b^n+c (Pocklington and Morrison algorithm respectively). All four work for k < b^n. Here it says, that number with |c| > 1 or k > b^n can only be PRP tested.

My questions are:
  1. How do the Pocklington and Morrison tests work?
  2. Why is there a restriction on the size of k?
  3. Why is it so bad with the rest? (|c| > 1, k > b^n)
You can generalize the form to (k*b^n+c)/gcd(k+c,b-1) (this is the Proth form, you can use -c as c for the Riesel form), since k*b^n+c is always divisible by gcd(k+c,b-1)

We assume that k>=1, b>=2, c != 0, gcd(k, c) = 1, gcd(b, c) = 1), for a fixed (k,b,c) triple satisfy this condition, we can find the smallest n>=1 such that (k*b^n+c)/gcd(k+c,b-1) is prime or prove that (k*b^n+c)/gcd(k+c,b-1) cannot be prime (has covering set of prime factors, or make a full covering set with all or partial algebraic factors)
sweety439 is offline   Reply With Quote
Old 2020-08-12, 18:58   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10000111111002 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
I know that Riesel and Proth tests are used for numbers k*2^n-1 and k*2^n+1 respectively. I have found the names of tests for k*b^n-c and k*b^n+c (Pocklington and Morrison algorithm respectively). All four work for k < b^n. Here it says, that number with |c| > 1 or k > b^n can only be PRP tested.

My questions are:
  1. How do the Pocklington and Morrison tests work?
  2. Why is there a restriction on the size of k?
  3. Why is it so bad with the rest? (|c| > 1, k > b^n)
If N is the number to be proved then you need to factor N-1 or N+1 or a combination of N-1 and N+1 to 33.33%. This is dead easy for numbers of the form k*b^n+-1, much harder if not infeasible for |c|>1.

See: https://primes.utm.edu/prove/index.html

Last fiddled with by paulunderwood on 2020-08-12 at 19:16
paulunderwood is online now   Reply With Quote
Old 2020-08-18, 01:51   #4
Gelly
 
Gelly's Avatar
 
May 2020

47 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
I know that Riesel and Proth tests are used for numbers k*2^n-1 and k*2^n+1 respectively. I have found the names of tests for k*b^n-c and k*b^n+c (Pocklington and Morrison algorithm respectively). All four work for k < b^n. Here it says, that number with |c| > 1 or k > b^n can only be PRP tested.

My questions are:
  1. How do the Pocklington and Morrison tests work?
  2. Why is there a restriction on the size of k?
  3. Why is it so bad with the rest? (|c| > 1, k > b^n)
1. Pocklington and Morrison utilize a factored part of 33.333...% (minus some small amount of digits, with a wiggle factor m) of N+1 or N-1. The details are in the paper here, which is also listed on the Wikipedia article on the Pocklington primality test. If you're willing to accept the Lucas sequence stuff as fact, it's actually a pretty digestible paper. Theorems 7 and 17 are what you're looking for

2. If k is too big, then you don't meet the requirement for factorizing a third of N if you don't know the factorization of k.

3. With |c| > 1, then you don't know a lot about the factorization of N+/-1 - even simple forms, like 3^n - 2, are only really provable with ECPP, even with a fair bit of knowledge of factorization of numbers that look like 3^n - 1. For rather large numbers, you have a real struggle meeting 33.33% unless you construct it or are astronomically lucky.

For k > b^n, you could be fine with k <= 2*b^n, since you'd still meet the requirements, but likely for the fact that it would no longer be a Proth or Proth-like number, they opted to not consider it outside of PRP tests
Gelly is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality testing non-Mersennes lukerichards Software 8 2018-01-24 22:30
Testing an expression for primality 1260 Software 17 2015-08-28 01:35
a new Deterministic primality testing wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25
a new primality testing method jasong Math 1 2007-11-06 21:46
newbie question - testing primality of very large numbers NeoGen Software 8 2006-03-20 01:22

All times are UTC. The time now is 16:39.


Sat Nov 26 16:39:49 UTC 2022 up 100 days, 14:08, 1 user, load averages: 0.95, 1.16, 1.10

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.

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