Number of Rabin-Miller Non-Witnesses

ATH · 2011-07-30, 16:42

Charles Greathouse showed me this formula for the number of "Non-Witnesses" / "False Witnesses" for composite numbers in the Rabin-Miller strong PRP test:
https://oeis.org/A141768

Code:

(PARI) star(n)={n--; n>>valuation(n, 2)};
bases(n)={my(f=factor(n)[, 1], nu=valuation(f[1]-1, 2), nn = star(n)); for(i=2, #f, nu = min(nu, valuation(f[i] - 1, 2)); ); (1 + (2^(#f * nu) - 1) / (2^#f - 1)) * prod(i=1, #f, gcd(nn, star(f[i]))) - 1};
r=0; forstep(n=9, 1e8, 2, if(isprime(n), next); t=bases(n); if(t>r, r=t; print1(n", ")))

I don't know who found this formula or who proved it, but I programmed it in C and tested it a bit myself, and I found something new, which is most likely already known but I'll write it here just in case.

I'll start by explaining the formula:

We have an odd composite number n with a prime factorization: $\mathrm{n=p_1^{\alpha_1} * p_2^{\alpha_2} * \dots * p_k^{\alpha_k} }$ with k distinct prime factors.
Each prime factor can be written as: $\mathrm{p_i = 2^{r_i}*s_i + 1}$ with s_i odd, and the smallest of the r_i I call r_min: $\mathrm{r_{min} = min(r_1,r_2,...,r_k).}$ So r_min >= 1.
The composite n can also be written in this way: $\mathrm{n = 2^{r_n}*s_n + 1}$ with s_n odd.

Now the number of non-witnesses, which I call NW and which includes 1 and n-1 as non-witnesses, is given by:

$\mathrm{NW(n) = \left(1 + \frac{2^{k * r_{min}}-1}{2^k - 1}\right) * \prod_{i=1}^{k} GCD(s_n,s_i)}$

I was investigating the different "types" of non-witnesses of $\mathrm{n = 2^{r_n} * s_n + 1}$ . I call the different types for A, B, C, D ...
Type A: $\mathrm{a^{s_n} \equiv 1 \pmod n}$ , type B: $\mathrm{a^{s_n} \equiv -1 \pmod n}$ , type C: $\mathrm{\left(a^{s_n}\right)^{2^1} \equiv -1 \pmod n}$ , type D: $\mathrm{\left(a^{s_n}\right)^{2^2} \equiv -1 \pmod n}$ , and so on.

If an integer a is type A, then n-a is type B and vice versa, so there is an equal number of A and B. If a is type C,D,E,... then n-a is the same type, so the number of each type is always even.

I found out that the formula actually gives the number of each "type" of non-witnesses. This is only from my numerical testing and is not proved in any way.

If I divide the polynomials in the formula it can be written as:

$\mathrm{ NW(n) = \left(1 + 1 + 2^k + 2^{2*k} + 2^{3*k} + \dots + 2^{(r_{min}-1)*k}\right) * prod = \left( prod + prod + prod*2^k + prod*2^{2*k} + prod*2^{3*k} + \dots + prod*2^{(r_{min}-1)*k}\right)}$
where $\mathrm{ prod = \prod_{i=1}^{k} GCD(s_n,s_i) }$

The first 2 prod is the number of type A and B, and prod*2^k is the number of type C, prod*2^2*k type D and so on. Note that there is only any type C if r_min>=2, type D if r_min>=3 and so on.

I tested this for all odd composites up to 400,000 so far and it checks out, and of those 166,140 odd composites < 400,000: 17315 had r_min=2, 1545 had r_min=3, 541 had r_min=4, 53 had r_min=5, 19 had r_min=6, 3 had r_min=7, 2 had r_min=8.

2011-07-30, 16:42	#1
ATH Einyen Dec 2003 Denmark 110001010110₂ Posts	Number of Rabin-Miller Non-Witnesses Charles Greathouse showed me this formula for the number of "Non-Witnesses" / "False Witnesses" for composite numbers in the Rabin-Miller strong PRP test: https://oeis.org/A141768 Code: (PARI) star(n)={n--; n>>valuation(n, 2)}; bases(n)={my(f=factor(n)[, 1], nu=valuation(f[1]-1, 2), nn = star(n)); for(i=2, #f, nu = min(nu, valuation(f[i] - 1, 2)); ); (1 + (2^(#f * nu) - 1) / (2^#f - 1)) * prod(i=1, #f, gcd(nn, star(f[i]))) - 1}; r=0; forstep(n=9, 1e8, 2, if(isprime(n), next); t=bases(n); if(t>r, r=t; print1(n", "))) I don't know who found this formula or who proved it, but I programmed it in C and tested it a bit myself, and I found something new, which is most likely already known but I'll write it here just in case. I'll start by explaining the formula: We have an odd composite number n with a prime factorization: $\mathrm{n=p_1^{\alpha_1} * p_2^{\alpha_2} * \dots * p_k^{\alpha_k} }$ with k distinct prime factors. Each prime factor can be written as: $\mathrm{p_i = 2^{r_i}s_i + 1}$ with s_i odd, and the smallest of the r_i I call r_min: $\mathrm{r_{min} = min(r_1,r_2,...,r_k).}$ So r_min >= 1. The composite n can also be written in this way: $\mathrm{n = 2^{r_n}s_n + 1}$ with s_n odd. Now the number of non-witnesses, which I call NW and which includes 1 and n-1 as non-witnesses, is given by: $\mathrm{NW(n) = \left(1 + \frac{2^{k * r_{min}}-1}{2^k - 1}\right) * \prod_{i=1}^{k} GCD(s_n,s_i)}$ I was investigating the different "types" of non-witnesses of $\mathrm{n = 2^{r_n} * s_n + 1}$ . I call the different types for A, B, C, D ... Type A: $\mathrm{a^{s_n} \equiv 1 \pmod n}$ , type B: $\mathrm{a^{s_n} \equiv -1 \pmod n}$ , type C: $\mathrm{\left(a^{s_n}\right)^{2^1} \equiv -1 \pmod n}$ , type D: $\mathrm{\left(a^{s_n}\right)^{2^2} \equiv -1 \pmod n}$ , and so on. If an integer a is type A, then n-a is type B and vice versa, so there is an equal number of A and B. If a is type C,D,E,... then n-a is the same type, so the number of each type is always even. I found out that the formula actually gives the number of each "type" of non-witnesses. This is only from my numerical testing and is not proved in any way. If I divide the polynomials in the formula it can be written as: $\mathrm{ NW(n) = \left(1 + 1 + 2^k + 2^{2k} + 2^{3k} + \dots + 2^{(r_{min}-1)k}\right) prod = \left( prod + prod + prod2^k + prod2^{2k} + prod2^{3k} + \dots + prod2^{(r_{min}-1)k}\right)}$ where $\mathrm{ prod = \prod_{i=1}^{k} GCD(s_n,s_i) }$ The first 2 prod is the number of type A and B, and prod2^k is the number of type C, prod2^2k type D and so on. Note that there is only any type C if r_min>=2, type D if r_min>=3 and so on. I tested this for all odd composites up to 400,000 so far and it checks out, and of those 166,140 odd composites < 400,000: 17315 had r_min=2, 1545 had r_min=3, 541 had r_min=4, 53 had r_min=5, 19 had r_min=6, 3 had r_min=7, 2 had r_min=8. Last fiddled with by ATH on 2011-07-30 at 16:44

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Probabilistic primality tests faster than Miller Rabin?	mathPuzzles	Math	14	2017-03-27 04:00
Miller-Rabin test questions	firejuggler	Miscellaneous Math	6	2011-12-22 05:57
Miller-Rabin Strong Probable Prime Test (SPRP)	fenderbender	Miscellaneous Math	22	2010-11-11 01:04
Monier-Rabin Theorem	flouran	Math	2	2009-05-01 21:44
Why no Rabin-Miller Tests ?	Axel Fox	Math	13	2004-06-28 16:07