a^(p^(n-1)) mod p^n
 

Is PFGW (or any other prime program) able to verify that 2^(5^(n-1)) mod 5^n is prime or PRP for n = 1, 2, 6, 18, 19, 248, 829 up to 1000?

If so, please show me the program or script file which can check for n which (general form) a^(p^(n-1)) mod p^n is prime or PRP WITHOUT giving any computational errors? Here a is any integer between 0 and p, and p is a prime. Can anyone continue further? The script should run twice as long for these PRPs, because of the computation of f = a^(p^(n-1)) mod p^n, and the computation of a^(f-1) mod f. I am willing to allow time for this.

[QUOTE=carpetpool;479922]Is PFGW (or any other prime program) able to verify that 2^(5^(n-1)) mod 5^n is prime or PRP for n = 1, 2, 6, 18, 19, 248, 829 up to 1000?

If so, please show me the program or script file which can check for n which (general form) a^(p^(n-1)) mod p^n is prime or PRP WITHOUT giving any computational errors? Here a is any integer between 0 and p, and p is a prime. Can anyone continue further? The script should run twice as long for these PRPs, because of the computation of f = a^(p^(n-1)) mod p^n, and the computation of a^(f-1) mod f. I am willing to allow time for this.[/QUOTE]

A simple PARI/GP script confirms your numbers as PRPs. Proving will be difficult, as they don't have any special form, and so APR-CL or ECPP might be the only way.

I don't know what is best way to do this - probably write a small program using GMP, calculate a^(p^(n-1)) mod p^n, then feed the full decimal expansion to PFGW for the PRP check. Or maybe do it using GMP itself which shouldn't be too bad for small-medium sizes?

EDIT: FWIW
[code]a=2; p=5; for(n=1,1000, r=Mod( a, p^n) ^ p^(n-1); if (ispseudoprime( lift(r)), print(a ":" p ":" n)))[/code]

EDIT2:- I wonder if gwnum can do mod exp with b^n+c where c=0? In that case, sticking with a custom gwnum program will be the fastest (but with some additional TF logic thrown in)

a^(p^(n-1))= 1/a^(p-1) mod p^n by modification of Euler's extention of Fermats little theorem.

[QUOTE=science_man_88;479926]a^(p^(n-1))= 1/a^(p-1) mod p^n by modification of Euler's extention of Fermats little theorem.[/QUOTE]

Hmmm...

It appears, (a^p^(n-1))^(p-1) = 1 (mod p^n), so it should be a^(p^(n-1))= 1^(1/(p-1)) (mod p^n) [i.e. p-1th roots of unity]

[QUOTE=axn;479924]A simple PARI/GP script confirms your numbers as PRPs. Proving will be difficult, as they don't have any special form, and so APR-CL or ECPP might be the only way.[/QUOTE]

A primality proof for n is possible if F*R = Phi(g,x) where Phi(g,n) is the gth cyclotomic polynomial evaluated at n and F > R (the factorization of F is known), and one demonstrates that for each prime p dividing n, p^n = 1 (mod F). However, the smaller g is, the more likely an elementary proof exists.

The cases for g = 3, 4, 6 are simple.

If g = 3, and n is the integer we would like to primality test, we need first find F*R = n^2+n+1 with F completely factored, and F > R. If F is successfully factored, all we need to do to prove that n is prime is prove that each prime p dividing n has the form F*k+1, F*k+m, or F*k+m^2 where the multiplicative order of m mod F is 3. If n > sqrt(F^3) then n is for sure to be prime, otherwise a slight factorization or trial division would show n is prime.

There are similar methods for m = 4 and 6.


[QUOTE=Prime Pages;]

How much further can we go? It is possible to consider higher powers such as the factors of

n^6 -1 = (n - 1)(n^2 + n + 1)(n + 1)(n^2 - n + 1).

(See [Williams78] for the theory and examples of these techniques). But the cost in terms of mathematical complication is very high. So in practice adding a few terms such as n^2+n+1 or n^2-n+1 is rarely worth the effort. Rather it makes sense to just move on to the general primality proving methods of the next chapter.

---

How do we improve on the tests of the previous chapter? The way Williams and others began in the 70's was to use the factors of other polynomials of n such as n^2+1, n^2+n+1 and n^2-n+1 [Williams78]. But why stop there? Why not try n^m-1 for a higher exponent m such as 5040, then every prime q such that q-1 divides 5040 (which does not divide n) must divide n5040-1 (by Fermats Little Theorem).

[/QUOTE]

Indeed PRPs of the these forms are much more "easier" and "simpler" to prove because n^2+1, n^2+n+1, n^2-n+1 has factors nearly the size of n and there is no need to proceed on a "higher exponent" m.

Just for fun, I tested the bases 5, 7, and 13 for primes:


T(b,p^k) = b^(p^(k-1)) mod p^k where p is prime.

Primes of this form --->

T(2,5) = 2
T(2,5^2) = 7
T(2,5^6) = 14557
T(2,5^18) = 3459595983307
T(2,5^19) = 3459595983307
T(2,5^248) = 114660923277...(174 digits)...158326452057
T(2,5^829) = 184203354927...(580 digits)...092896764557
T(3,5) = 3
T(3,5^4) = 443
T(3,5^74) = 3260042344475...(53 digits)...265013391693
T(3,5^255) = 128927315588...(180 digits)...938353235443
T(2,7) = 2
T(2,7^19) = 10744682090246617
T(2,7^119) = 129270567058...(101 digits)...417448696587
T(3,7) = 3
T(3,7^2) = 31
T(3,7^49) = 121854617702...(42 digits)...116734992637
T(3,7^80) = 355518391384...(68 digits)...271989992259
T(3,7^84) = 370045804637...(71 digits)...790446569171
T(3,7^509) = 424498268158...(430 digits)...085049118047
T(3,7^830) = 784953661875...(701 digits)...375649130343
T(4,7^8) = 3376853
T(4,7^25) = 936579478224094047977
T(4,7^61) = 677822686658...(51 digits)...634249273881
T(4,7^150) = 402056376682...(127 digits)...615640612833
T(4,7^855) = 802222138774...(722 digits)...088240459911
T(5,7) = 5
T(5,7^2) = 19
T(5,7^3) = 19
T(5,7^10) = 135967277
T(5,7^20) = 57648689021992241
T(5,7^41) = 406633727665...(35 digits)...294355914421
T(5,7^42) = 406633727665...(35 digits)...294355914421
T(5,7^43) = 406633727665...(35 digits)...294355914421
T(5,7^101) = 178998697417...(86 digits)...953481618481
T(3,13) = 3
T(3,13^20) = 14600137274456049185171
T(3,13^44) = 677960582853...(49 digits)...457736192243
T(3,13^80) = 388371299568...(89 digits)...042549799899
T(3,13^480) = 449809901202...(535 digits)...480084160343
T(5,13) = 5
T(5,13^3) = 239
T(5,13^4) = 239
T(5,13^9) = 822557039
T(5,13^976) = 822557039702...(1096 digits)...821953762217
T(8,13^260) = 417580382995...(290 digits)...642580464859
T(9,13^31) = 223840666066...(35 digits)...242320402727
T(9,13^325) = 982320057720...(362 digits)...838087627813

Edit: Thanks @axn for the script:

I am currently running:

[CODE]forprime(p=5,19, for(a=2,p-2, for(n=1,1000, r=Mod( a, p^n) ^ p^(n-1); if (ispseudoprime( lift(r)), print(a ":" p ":" n)))[/CODE]

[QUOTE=axn;479927]Hmmm...

It appears, (a^p^(n-1))^(p-1) = 1 (mod p^n), so it should be a^(p^(n-1))= 1^(1/(p-1)) (mod p^n) [i.e. p-1th roots of unity][/QUOTE]

Yeah I screwed it up in my head.

[QUOTE=science_man_88;479939]Yeah I screwed it up in my head.[/QUOTE]

This is also equivalent of taking the pth roots of unity mod n. For example, +-i mod 5 is either 2, or -2 (3) because i^2 = -1 mod 5, i.e. is 4.

Is there any way of eliminating some of these numbers through sieving or without actually calculating the numbers? The modular exponentiation is the bit that takes the time with not the prp test.

I seem to have found a (practical) primality test for p = k*3^n+-1 where k < 3^n:

Let a(n) = (a(n-1)+1)^3 - (3*a(n-1)+1)

where a(1) = x

If there exists an integer x (as above with a(1)) such that p divides a(n), then a(n) is prime.

If p divides a(n), then by analyzing the splitting behaviors of subfields of cyclotomic fields, each prime p dividing a(n) must have the form k*3^n+-1, so if there were a prime q = s*3^n+-1 which divides p, then p would be composite and q must be less than the square root of p, as s and 3^n would also be less than the square root of p. But as stated before k < 3^n, so this is impossible, so q must be greater than the square root of p, and by contradiction q = p so p is prime.

Anyways the relevance in this is that there exists other types of sequences (involving higher powers other than cubes which can show that a^(p^(n-1)) mod p^n is prime for some prime p.

[QUOTE=henryzz;480301]The modular exponentiation is the bit that takes the time with not the prp test.[/QUOTE]

They're both similar operations (althought a good chunk of numbers will not proceed to PRP test, as they will have small-ish factors).

[QUOTE=axn;480357]They're both similar operations (althought a good chunk of numbers will not proceed to PRP test, as they will have small-ish factors).[/QUOTE]

There is a very high proportion of small factors(as you would expect). There is also quite a number of repeat numbers. It isn't that uncommon that T(3,5^k)==T(3,5^(k+1)). A fast way of detecting duplicates or even numbers would help a lot.