20200812, 18:50  #1 
"Viliam Furík"
Jul 2018
Martin, Slovakia
1420_{8} Posts 
Primality testing of numbers k*b^n+c
I know that Riesel and Proth tests are used for numbers k*2^n1 and k*2^n+1 respectively. I have found the names of tests for k*b^nc 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:

20200812, 18:57  #2  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
3,643 Posts 
Quote:
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,b1) is prime or prove that (k*b^n+c)/gcd(k+c,b1) cannot be prime (has covering set of prime factors, or make a full covering set with all or partial algebraic factors) 

20200812, 18:58  #3  
Sep 2002
Database er0rr
1000011111100_{2} Posts 
Quote:
See: https://primes.utm.edu/prove/index.html Last fiddled with by paulunderwood on 20200812 at 19:16 

20200818, 01:51  #4  
May 2020
47 Posts 
Quote:
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 Prothlike number, they opted to not consider it outside of PRP tests 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primality testing nonMersennes  lukerichards  Software  8  20180124 22:30 
Testing an expression for primality  1260  Software  17  20150828 01:35 
a new Deterministic primality testing  wsc812  Computer Science & Computational Number Theory  36  20130304 06:25 
a new primality testing method  jasong  Math  1  20071106 21:46 
newbie question  testing primality of very large numbers  NeoGen  Software  8  20060320 01:22 