Lucas-Lehmer Primes

[henryzz]

I have been thinking for a while that a nice form to test for primes might be the numbers encountered during a lucas-lehmer test.
Let LL(x,n) = LL(x,n-1)^2-2 with LL(x,0)=x.

It will be possible to primality test some of these numbers. For example:
LL(x,4) + 1= (x-1) (x+1) (x^2-3) (x^4-4 x^2+1) (x^8-8 x^6+20 x^4-16 x^2+1) which should provide enough prime factors for some to be proven prime. This doesn't work perfectly for example LL(425,10) only has ~8.7% factored. It would be possible to extend that another 152 digits with snfs(and another 320 if someone is feeling adventurous)

The thing that makes these numbers nice is that there are strict restrictions on the form that their factors can take. The factors of LL(x,10) seem to take the form k*2^12+-1 for example(proof would be useful). This would imply that it should be possible to sieve them deeper and once sieved they should more likely to be prime than general numbers. Also P-1 and P+1 should be strong factoring tools for these numbers.

I would appreciate it if anyone has any further information on these numbers. There are things like LL(3,n)=Lucas(2^(n+1)). It would be nice to prove the form of the factors and estimate the likelihood of one of these candidates being prime.

[science_man_88]

Originally Posted by henryzz

I have been thinking for a while that a nice form to test for primes might be the numbers encountered during a lucas-lehmer test.
Let LL(x,n) = LL(x,n-1)^2-2 with LL(x,0)=x.

It will be possible to primality test some of these numbers. For example:
LL(x,4) + 1= (x-1) (x+1) (x^2-3) (x^4-4 x^2+1) (x^8-8 x^6+20 x^4-16 x^2+1) which should provide enough prime factors for some to be proven prime. This doesn't work perfectly for example LL(425,10) only has ~8.7% factored. It would be possible to extend that another 152 digits with snfs(and another 320 if someone is feeling adventurous)

The thing that makes these numbers nice is that there are strict restrictions on the form that their factors can take. The factors of LL(x,10) seem to take the form k*2^12+-1 for example(proof would be useful). This would imply that it should be possible to sieve them deeper and once sieved they should more likely to be prime than general numbers. Also P-1 and P+1 should be strong factoring tools for these numbers.

I would appreciate it if anyone has any further information on these numbers. There are things like LL(3,n)=Lucas(2^(n+1)). It would be nice to prove the form of the factors and estimate the likelihood of one of these candidates being prime.

well lets see if x is even so are all the terms so that the lowest factor they have is 2.
if x is divisible by 3 we get 0,1,2,2,2,2,2,2,2,2 ... mod 3 and none can divide by 3.
and in general if an odd prime p divides one of them it can no longer divide any of the others as it will enter the loop 0,P-2,2,2,2,2,..... in this form of the test or 0,P-1,1,1,1,1,1,... in the versions where the common factor of 2 is taken out. edit: we can also show that any polynomials we need to factor that have an even number odd coefficients must always divide by 2 if the constant term is even and can only not divide by 2 if the constant term is odd in which case it is odd for all even values of a variable in all terms.( because then the parity arguments can come into play).

[henryzz]

Originally Posted by science_man_88

well lets see if x is even so are all the terms so that the lowest factor they have is 2.
if x is divisible by 3 we get 0,1,2,2,2,2,2,2,2,2 ... mod 3 and none can divide by 3.
and in general if an odd prime p divides one of them it can no longer divide any of the others as it will enter the loop 0,P-2,2,2,2,2,..... in this form of the test or 0,P-1,1,1,1,1,1,... in the versions where the common factor of 2 is taken out. edit: we can also show that any polynomials we need to factor that have an even number odd coefficients must always divide by 2 if the constant term is even and can only not divide by 2 if the constant term is odd in which case it is odd for all even values of a variable in all terms.( because then the parity arguments can come into play).

I was thinking sieving would be done with constant n rather than constant x. I could see why this sort of argument could potentially be used to prove the form of the factors.

[science_man_88]

Originally Posted by henryzz

I was thinking sieving would be done with constant n rather than constant x. I could see why this sort of argument could potentially be used to prove the form of the factors.

it still won't contain any prime that divides earlier term in it's own sequence also since they have constant form of polynomial compared with x the parity arguments still happen:

LL(x,1) = x
LL(x,2) = x^2-2 in this form where LL(x,n+1)=LL(x,n)^2-2 there will only be one odd coefficient therefore it's only odd if x is odd. all x values that are the same mod a prime p can be done all at once as they will give the same modular remainder mod p so like in factoring mersennes you only have to test the first p-1 x values to test for division by p before p can't divide any of them. edit2: and of course any x values that are 2 less than a square are already in a lower sequence so the can be skipped.

[henryzz]

I am currently using pfgw's modular factoring to find the first prime for each n.
n=10-12:

(((((((((425^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
((((((((((1685^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
(((((((((((1417^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2

The trial division is reaching large numbers. It's sieve has been expanded to 300 billion.
There would be a large speedup with a proper sieve.

[science_man_88]

Originally Posted by henryzz

I am currently using pfgw's modular factoring to find the first prime for each n.
n=10-12:

(((((((((425^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
((((((((((1685^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2
(((((((((((1417^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2

The trial division is reaching large numbers. It's sieve has been expanded to 300 billion.
There would be a large speedup with a proper sieve.

okay so find out which x values allow a number to divide by r in x=0- r-1 then eliminate all x values that are that original x mod r.

[henryzz]

Originally Posted by science_man_88

okay so find out which x values allow a number to divide by r in x=0- r-1 then eliminate all x values that are that original x mod r.

Looking at 31 dividing LL(x,3) http://factordb.com/index.php?query=...e=200&format=1
4, 9, 10, 11, 20, 21, 22, 27
It appears that there is a mirror image as I expected. Not sure how I would go about finding those without trial division. The problem with sieving these numbers like that is that the numbers will often be larger than the range we are sieving. This means that we are basically trial dividing. Another approach is needed.

After an overnight search ((((((((((((9003^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2 was found for n=13.

I am afraid your maths escapes me science_man_88.

[science_man_88]

Originally Posted by henryzz

Looking at 31 dividing LL(x,3) http://factordb.com/index.php?query=...e=200&format=1
4, 9, 10, 11, 20, 21, 22, 27
It appears that there is a mirror image as I expected. Not sure how I would go about finding those without trial division. The problem with sieving these numbers like that is that the numbers will often be larger than the range we are sieving. This means that we are basically trial dividing. Another approach is needed.

After an overnight search ((((((((((((9003^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2 was found for n=13.

I am afraid your maths escapes me science_man_88.

after r, n or x values either all r values mod r are used up or it has already cycled. so you only need to test the first r, n values with the first r x values to know if r divides any of the values in the whole of LLP(x,n) for technically since certain things always happen you can cut the testing even more. if r divides LLP(x,n) it will never be a divisor for LLP(x,k) for k>n.

examples from the LL test:

4,14,194, for odd prime r =3 we get the modular remainders 1,2,2 since we've tested the first 3 values and have not got 0 we know that none of the LL test numbers will divide by 3. furthermore we have learned that LLP({x:x%3==1},n) for n={1,2,3} all give the pattern 1,2,2 when mod 3.

we know that for p=13 2^p-1 divides into LLP(4,11) that means it can not divide into any LLP(4,k) where k>11. this is just using basic math of course.


or to show it with true data:

%10 =
[1 -1  -1     -1          -1]

[2  2   2      2           2]

[3  7  47   2207     4870847]

[4 14 194  37634  1416317954]

[5 23 527 277727 77132286527]

okay so lets test for division by 3 in this data 1= 1 mod 3 so what I'm saying is based on modular arithmetic we can prove that 4= 1 mod 3 as well, going forward we have -1 = 2 mod 3 so from that same thing we can prove 14 = 2 mod 3, and the same thing happens with -1 and 194 2 is always 2 mod 3 and so we can use modular arithmetic to show 5=2 mod 3, 23 = 2 mod 3, 527 =2 mod 3, and in fact that whole last row will be 2 mod 2.

then we test the row starting with 3 well 3 divides by 3 so that's a 0 mod 3 answer and 0^2-2 is -2 ( aka 1) mod 3 so 7 is 1 mod 3 and 1^2-2 = -1 ( aka 2) mod 3 and 2^2-2 = 2 mod 3 as well so that residue will happen again and again through the whole row. if we were to look at the large scale data we would get these three row repeating going down:

1,2,2,2,2,...
2,2,2,2,2,...
0,1,2,2,2,... so only values with x that divides by 3 will be 0 mod 3 (and only for n=1) the rest are safe from elimination as we know 3 doesn't divide them. and we can do this with any prime p all we have to do is check the first p rows and first p columns, if one in that area of the table doesn't divide by p then none of the values will for the whole extent of the table.

[science_man_88]

Originally Posted by henryzz

Looking at 31 dividing LL(x,3) http://factordb.com/index.php?query=...e=200&format=1
4, 9, 10, 11, 20, 21, 22, 27
It appears that there is a mirror image as I expected. Not sure how I would go about finding those without trial division. The problem with sieving these numbers like that is that the numbers will often be larger than the range we are sieving. This means that we are basically trial dividing. Another approach is needed.

After an overnight search ((((((((((((9003^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2 was found for n=13.

I am afraid your maths escapes me science_man_88.

well if you had done n=1 and n=2 and found values that divide by 31 you could eliminate those from testing so from n=1 you could show that in LLP(x,3), x can't be in {8,23} and with n=2 you can prove that LLP(x,3) can't work out to divide by it with x in {5,14,17,26} so I just knocked 1/5 off the list to check to know it all. all it takes to do this is knowledge that in polynomials r|(f(x+r)-f(x)) where | means divides so they are the same mod r that and the fact that under x^2-2 once you hit 0 modularly you will never hit 0 again to help knock out these numbers. and using your own values for n=3 I can tell you that for n=4 the values you would need to check are x=1,2,3,6,7,12,13,15,16,18,19,24,25,28,29,30 mod 31. edit2: and the symmetry is to be expected in that when allowing negative equivalents you get two for one (aka both)

 my(r=11,a=[1..r-1],b=vector(#a,i,[]),c=[%36,%37,%38,%39,%40,%41,%42,%43,%44,%45,%46,%47]);for(y=1,#a,if(a[y]==0,,for(z=1,#c,if(subst(c[z],x,y)%r,,b[z]=concat(b[z],y);a[y]=0))));b

wrap it in a forprime loop to change r instead of declare one value and you'll be sieving them. where %36 etc are replaced by LLP(x,n)'s polynomial:

LLP(x,n) = if(n==1,x,my(s=self());s(x,n-1)^2-2)

[henryzz]

Just thought I would point out that we don't need to test the small primes normally as we know the form of the factors is k*2^(n+2)+-1 or 2. This means that the factors start at over 1e4 and will finish at over 1e8 and if we get it faster maybe 1e10.
As we are only looking at a range of around 10-100k values of x this means that we can't really sieve. Quickly identifying which candidates can divide LL(x,n) is the best we can hope for. Note n will remain fixed.
All methods need to be extendable to very large factors and efficient for a small range(I suppose range will increase as n increases but so will the size of the factors).
Nothing for n=14 yet. I suspect a major speed improvement over the pfgw trial division may be code that uses the form of the factor when doing the trial division. I suspect that pfgw uses the k*2^(n+2)+-1 form to generate the factors but divides using generic methods.
It may be worth looking at how people factor fermat numbers as that is a similar form of factor.

[science_man_88]

Originally Posted by henryzz

Just thought I would point out that we don't need to test the small primes normally as we know the form of the factors is k*2^(n+2)+-1 or 2. This means that the factors start at over 1e4 and will finish at over 1e8 and if we get it faster maybe 1e10.
As we are only looking at a range of around 10-100k values of x this means that we can't really sieve. Quickly identifying which candidates can divide LL(x,n) is the best we can hope for. Note n will remain fixed.
All methods need to be extendable to very large factors and efficient for a small range(I suppose range will increase as n increases but so will the size of the factors).
Nothing for n=14 yet. I suspect a major speed improvement over the pfgw trial division may be code that uses the form of the factor when doing the trial division. I suspect that pfgw uses the k*2^(n+2)+-1 form to generate the factors but divides using generic methods.
It may be worth looking at how people factor fermat numbers as that is a similar form of factor.

I'm not sure if I believe the factor form without the proof, I do see based on an assumption that in theory the lowest factor has to exceed 2^(n+1) because if not then there can't be 2^n values of every n below that and still have values leftover to delete ( as they would sum up to 2^(n+1)-1). okay I guess I see the logic of 2^(n+2) because then it allows there to be the proper 2^(n+1) values the chosen n. still not convinced on the exact form though. my guess is this comes from it needing to be odd ? and not the 1 or 7 mod 8 form. also have you sieved the k the same way I would have sieved the values at any n because every third one allows the difference to divide by 3 etc. so the k in the same congruence classes can all fall to the same factor possibly.