mersenneforum.org > Math Primality testing of numbers k*b^n+c
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-12, 18:50 #1 Viliam Furik     "Viliam Furík" Jul 2018 Martin, Slovakia 14208 Posts 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:How do the Pocklington and Morrison tests work? Why is there a restriction on the size of k? Why is it so bad with the rest? (|c| > 1, k > b^n)
2020-08-12, 18:57   #2
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

3,643 Posts

Quote:
 Originally Posted by Viliam Furik 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:How do the Pocklington and Morrison tests work? Why is there a restriction on the size of k? 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)

2020-08-12, 18:58   #3
paulunderwood

Sep 2002
Database er0rr

10000111111002 Posts

Quote:
 Originally Posted by Viliam Furik 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:How do the Pocklington and Morrison tests work? Why is there a restriction on the size of k? 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

2020-08-18, 01:51   #4
Gelly

May 2020

47 Posts

Quote:
 Originally Posted by Viliam Furik 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:How do the Pocklington and Morrison tests work? Why is there a restriction on the size of k? 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

 Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards Software 8 2018-01-24 22:30 1260 Software 17 2015-08-28 01:35 wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25 jasong Math 1 2007-11-06 21:46 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