Primality testing of numbers k*b^n+c

[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:

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)

[sweety439]

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:

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)

[paulunderwood]

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:

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

[Gelly]

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:

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