## 25402A sharper a-SPRP test ?

Expand Messages
• Oct 26 5:25 AM
A peaceful day for all members of the group and especially for David

I refer to the page
http://primes.utm.edu/prove/prove2_3.html

Is think the following proposed test is better, results below:

Let be p element N, odd and greater 5
a element N, gcd (a,p)=1 and jacobi (a,p)=-1
p-1=(2^d)*r with r>2 and d maximal
(This test is not suitable for Mersenne numbers ;-)

1. A pretest which is new with
a^(2^(d-1)) <> p-1 mod p
if this precondition fails, the test should be repeated by another a

2. a^(2^[(d-1)*r)])=p-1 mod p (the normal Sprp test)

1. and 2. reveal that a is a non quadratic residuum and that a primitiv root of t | r
exist so that at least 2 factors n,m of p exist with t|n-1 and t|m-1
A factorization of r is not needed and the test can be improved by using the Pocklington theorem so that an estimation of t can be made.

The test is a little bit sharper than the SPRP-test.

I know that it is only a little improvement and may be a logical consequence.
If there are some results available, it may be friendly to give me some links or sources.
Otherwise i will make some work to document this idea.
If someone can give an accurate mathematical proof which should not be difficult
i will be thankful for it.

Friendly greetings from the primes
Bernhard

Especially for David in order to decrease the amount of some gremlins

The following gremlins fool this test:
a=2, p< 100000:

• anz_prob_prime:=0;
for p from 7 to 1000000 step 2 do
a:=2;
if numlib::jacobi (a, p)=-1 then
k:=(p-1)/2;
d:=1;
while k mod 2 = 0 do
k:=k/2;
d:=d+1;
end_while;
res:=powermod (a, 2^(d-1), p);
if res<>p-1 then
res:=powermod (res, k, p);
if res=p-1 then
if isprime (p)=FALSE then
fac:=ifactor (p);
anz_prob_prime:=anz_prob_prime+1;
print (anz_prob_prime,"FALSE", p, "p-1=", ifactor (p-1), "p=",fac);
for i from 1 to (nops (fac)-1)/2 do
print (fac[2*i],"-1=", ifactor (fac[2*i]-1));
end_for;
end_if;
end_if;
else
print ("Pretest Fails", p, d);
end_if;
end_if;
end_for;
```

2  2
1, "FALSE", 3277, "p-1=", 2  3  7 13, "p=", 29 113

2
29, "-1=", 2  7

4
113, "-1=", 2  7

2  2
2, "FALSE", 29341, "p-1=", 2  3  5 163, "p=", 13 37 61

2
13, "-1=", 2  3

2  2
37, "-1=", 2  3

2
61, "-1=", 2  3 5

2  3
3, "FALSE", 49141, "p-1=", 2  3  5 7 13, "p=", 157 313

2
157, "-1=", 2  3 13

3
313, "-1=", 2  3 13

2
4, "FALSE", 80581, "p-1=", 2  3 5 17 79, "p=", 61 1321

2
61, "-1=", 2  3 5

3
1321, "-1=", 2  3 5 11

2
5, "FALSE", 88357, "p-1=", 2  3 37 199, "p=", 149 593

2
149, "-1=", 2  37

4
593, "-1=", 2  37

2  4
6, "FALSE", 104653, "p-1=", 2  3  17 19, "p=", 229 457

2
229, "-1=", 2  3 19

3
457, "-1=", 2  3 19

2  2
7, "FALSE", 196093, "p-1=", 2  3  13 419, "p=", 157 1249

2
157, "-1=", 2  3 13

5
1249, "-1=", 2  3 13

2  3
8, "FALSE", 314821, "p-1=", 2  3  5 11 53, "p=", 13 61 397

2
13, "-1=", 2  3

2
61, "-1=", 2  3 5

2  2
397, "-1=", 2  3  11

2
9, "FALSE", 458989, "p-1=", 2  3 23 1663, "p=", 277 1657

2
277, "-1=", 2  3 23

3  2
1657, "-1=", 2  3  23

10, "FALSE", 476971, "p-1=", 2 3 5 13 1223, "p=", 11 131 331

11, "-1=", 2 5

131, "-1=", 2 5 13

331, "-1=", 2 3 5 11

2  3
11, "FALSE", 489997, "p-1=", 2  3  13 349, "p=", 157 3121

2
157, "-1=", 2  3 13

4
3121, "-1=", 2  3 5 13

2  4
12, "FALSE", 800605, "p-1=", 2  3  7 353, "p=", 5 13 109 113

2
5, "-1=", 2

2
13, "-1=", 2  3

2  3
109, "-1=", 2  3

4
113, "-1=", 2  7

2
13, "FALSE", 838861, "p-1=", 2  3 5 11 31 41, "p=", 397 2113

2  2
397, "-1=", 2  3  11

6
2113, "-1=", 2  3 11

2  4    2
14, "FALSE", 873181, "p-1=", 2  3  5 7  11, "p=", 661 1321

2
661, "-1=", 2  3 5 11

3
1321, "-1=", 2  3 5 11

15, "FALSE", 877099, "p-1=", 2 3 17 8599, "p=", 307 2857

2
307, "-1=", 2 3  17

3
2857, "-1=", 2  3 7 17```