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. [URL="https://www.rieselprime.de/ziki/LLR"]Here[/URL] it says, that number with |c| > 1 or k > b^n can only be PRP tested.

My questions are:[LIST=1][*]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)[/LIST]

[QUOTE=Viliam Furik;553463]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. [URL="https://www.rieselprime.de/ziki/LLR"]Here[/URL] it says, that number with |c| > 1 or k > b^n can only be PRP tested.

My questions are:[LIST=1][*]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)[/LIST][/QUOTE]

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)

[QUOTE=Viliam Furik;553463]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. [URL="https://www.rieselprime.de/ziki/LLR"]Here[/URL] it says, that number with |c| > 1 or k > b^n can only be PRP tested.

My questions are:[LIST=1][*]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)[/LIST][/QUOTE]

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: [url]https://primes.utm.edu/prove/index.html[/url]

[QUOTE=Viliam Furik;553463]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. [URL="https://www.rieselprime.de/ziki/LLR"]Here[/URL] it says, that number with |c| > 1 or k > b^n can only be PRP tested.

My questions are:[LIST=1][*]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)[/LIST][/QUOTE]

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 [URL="https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf"]here[/URL], 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