Math subforum (I am not a crank)

[Andrew Usher]

Just recently I made a post titled 'LL pseudoprimes' about a new class of pseudoprimes I investigated, which I had been thinking of for some time, then wrote a program to compute. My posts were moved to the crackpot forum, although, as few new posts are allowed to remain in Math, I am not sure if that is an implication of crankery. I admit my initial post was poorly written due to my state of mind and uncharacteristic haste, and I would rather replace it with a better version I have now composed, incorporating my program's results.

I do not see where the belief that I am a mathematical crank could come from; though my post (even in its revised version) may not being understood by many here, it has none of the crackpot characteristics, nor does my posting history.

As it wasn't meant to contain a proof of anything, no real rigor was attempted.

Here is the revised version, that I would like to see in the Math forum:

I define a Lucas-Lehmer pseudoprime (for lack of any better term I know of) as any composite 7 mod 24 that divides the (n+1)/8'th term of A011943 or its double which is V(14,1) (the numbers in the LL test, after 4, are the terms with power-of-2 indices in that sequence). Every prime 7 mod 24 does, from known properties of Lucas sequences (one was discovered and proved by me but I doubt it's original).

The LL test is then an assertion that no such pseudoprimes can be 2^n-1, and the LLR extension (k not divisible by 3) that they can't be k*2^n-1 for k<2^n ; in fact, somewhat better can be proved. But the question of the existence of any such pseudoprimes must be investigated; the conditions of them are fairly stringent, but it seems likely that as usual infinitely many exist. I wrote a program to find all those under 2^32, which verified itself by getting zero residues for every prime 7 mod 24 in that range; 60 composites 7 mod 24 also do and are the sought pseudoprimes. The smallest is over a million; only two have more than 2 prime factors and those, 31*223*607 and 31*607*1567, both divide the 28th term of the sequence.

Even taking the modular restriction into account, this is substantially fewer than there are strong pseudoprimes to any base, or any type related to the standard Fibonacci and Lucas numbers, supporting my intuitive belief when seeing the conditions required.

I credit reading about the LLR test for giving me the idea to investigate this, and would like to know if anyone else has had (or has heard of) a similar notion. Finally, I will give the complete list on request.

[Uncwilly]

The forum that it got moved to: "Other Mathematical Topics" is not the crackpot forum.
Miscellaneous Math serves that function.

Maybe you should reread your posts and then post them. Or compose them off-line, read them, then post them.

[Andrew Usher]

I'm pretty sure I saw it in Miscellaneous Math at the time I wrote that, but OK, what _is_ allowed to stay in the Math forum? I'd rather get it right the first time.

And I do usually compose offline, as I did for this improved version.

[Batalov]

mersenneforum.org > Great Internet Mersenne Prime Search > Math

That "Math" is a subforum of "Great Internet Mersenne Prime Search-related Math" - discussion of how GIMPS functions.
_______

Generally speaking, one can take any specialized primality test and deliberately use it outside of its use domain, for example Berrizbeitia-Iskra test, and then express a genuine surprise that "it doesn't work! It produces pseudoprimes!" Well, of course it does. Not really surprising. Lucas test is no different than Fermat test - except when used in correct context. Talk to Paul Underwood and other folks about combining several tests together to produce gold out of two or three pieces of led.

[paulunderwood]

Here BPSW is king. I have come up with several test over the years for example:

1. f=x^2-2 is "prime" if x^f==x mod f.
   
2. x^(n+1)==1 (mod n,x^2-(a-2)*x+1) and x^(n+1)==1 (mod n,x^2-(a+2)*x+1) and (a-2)^(n-1)==1 mod n and (a+2)^(n-1)==1 mod n (any a).
   
3. (x+2)^(n+1)==5+2*a (mod x^2-a*x+1) ( a minimal).
   
4. x^(n+1)==-3 (mod n, x^2-3^r*x-3) (any r: gcd(r-1,n-1)=1).

( The last 3 require a strong discriminant with jacobi symbol = -1.)

All these test, like BPSW, are believed to produce pseudoprimes eventually.

[Andrew Usher]

That makes sense re: the Math forum.

Yes, I thought there would be pseudoprimes but I needed to search to be sure, and I correctly realised a computer program would be required, and as a benefit I discovered how to efficiently compute Lucas sequences - which I know was known, but not to me.

It's a good bet that any test will have pseudoprimes unless proved not to, and infinitely many of them. This includes, yes, all those Paul Underwood mentions.

[Dr Sardonicus]

1) The usage "LL pseudoprime" is gratuitously confusing. "LL" meaning "Lucas-Lehmer" is universally understood to mean the conclusive primality test for Mersenne numbers. The terms "Lucas test" and "Lucas pseudoprime" are standard, and apply in particular to what you are describing, as well as to any number of other similar tests.

2) Let L_n = trace(norm(Mod(2 + x, x^2 - 3)^n)); L₀ = 2, L₁ = 4, L_n+2 = 4*L_n+1 - L_n.

It is true (and not difficult to prove) that if p is prime, and p == 7 (mod 24), then L_(p+1)/4 == 0 (mod p).

3) Curiously, the proof that L_(p+1)/4 == 0 (mod p) [at least, the one that imitates the usual proof that this holds for Mersenne primes] depends on the fact that, for p prime, p == 7 (mod 8) we have

2^(p-1)/2 == 1 (mod p).

Using a clumsy, inefficient, totally mindless Pari-GP script, I checked the composite numbers n == 7 (mod 24), n < 50000000 for which L_(n+1)/4 == 0 (mod n). And the congruence 2^(n-1)/2 (mod n) does not hold for any of them.

? u=Mod(x+2,x^2-3);forstep(n=7,50000000,24,r=lift(trace((Mod(1,n)*u)^((n+1)/4)));if(r==0&&!isprime(n),print(n" "factor(n)" "lift(Mod(2,n)^((n-1)/2)))))
1037623 [337, 1; 3079, 1] 246074
2211631 [271, 1; 8161, 1] 1898884
4196191 [31, 1; 223, 1; 607, 1] 1556449
7076623 [271, 1; 26113, 1] 3020878
9100783 [1231, 1; 7393, 1] 8262536
11418991 [2287, 1; 4993, 1] 8616593
15219559 [919, 1; 16561, 1] 13719061
21148399 [1327, 1; 15937, 1] 19931655
29486239 [31, 1; 607, 1; 1567, 1] 745287
32060503 [2311, 1; 13873, 1] 29795787
36035383 [5479, 1; 6577, 1] 21243887
?

4) An integer base "strong Rabin-Miller" test (which we have here with base 2 for n == 7 (mod 8)) is [to the best of my understanding] much faster than a Lucas test. Combining a base-2 strong Miller-Rabin test with a judiciously-chosen Lucas test gives a BPSW test as implemented in, e.g. Pari-GP's ispseudoprime() function. Although the smart money is on there being infinitely many BPSW pseudoprimes (i.e. composite numbers that "pass" the test), not a single example is known.

5) This is the information age. Before posting, try doing a Forum search. If that is unfruitful, try feeding likely search parameters, e.g. "lucas pseudoprime" into your favorite Internet search engine. But be prepared to jump back. The hit parade will be a long one. It will take some practice to learn how to sort the wheat from the chaff. It is a skill worth learning.

[paulunderwood]

Originally Posted by Dr Sardonicus

1) The usage "LL pseudoprime" is gratuitously confusing. "LL" meaning "Lucas-Lehmer" is universally understood to mean the conclusive primality test for Mersenne numbers. The terms "Lucas test" and "Lucas pseudoprime" are standard, and apply in particular to what you are describing, as well as to any number of other similar tests.

2) Let L_n = trace(norm(Mod(2 + x, x^2 - 3)^n)); L₀ = 2, L₁ = 4, L_n+2 = 4*L_n+1 - L_n.

It is true (and not difficult to prove) that if p is prime, and p == 7 (mod 24), then L_(p+1)/4 == 0 (mod p).

3) Curiously, the proof that L_(p+1)/4 == 0 (mod p) [at least, the one that imitates the usual proof that this holds for Mersenne primes] depends on the fact that, for p prime, p == 7 (mod 8) we have

2^(p-1)/2 == 1 (mod p).

Using a clumsy, inefficient, totally mindless Pari-GP script, I checked the composite numbers n == 7 (mod 24), n < 50000000 for which L_(n+1)/4 == 0 (mod n). And the congruence 2^(n-1)/2 (mod n) does not hold for any of them.

? u=Mod(x+2,x^2-3);forstep(n=7,50000000,24,r=lift(trace((Mod(1,n)*u)^((n+1)/4)));if(r==0&&!isprime(n),print(n" "factor(n)" "lift(Mod(2,n)^((n-1)/2)))))
1037623 [337, 1; 3079, 1] 246074
2211631 [271, 1; 8161, 1] 1898884
4196191 [31, 1; 223, 1; 607, 1] 1556449
7076623 [271, 1; 26113, 1] 3020878
9100783 [1231, 1; 7393, 1] 8262536
11418991 [2287, 1; 4993, 1] 8616593
15219559 [919, 1; 16561, 1] 13719061
21148399 [1327, 1; 15937, 1] 19931655
29486239 [31, 1; 607, 1; 1567, 1] 745287
32060503 [2311, 1; 13873, 1] 29795787
36035383 [5479, 1; 6577, 1] 21243887
?

4) An integer base "strong Rabin-Miller" test (which we have here with base 2 for n == 7 (mod 8)) is [to the best of my understanding] much faster than a Lucas test. Combining a base-2 strong Miller-Rabin test with a judiciously-chosen Lucas test gives a BPSW test as implemented in, e.g. Pari-GP's ispseudoprime() function. Although the smart money is on there being infinitely many BPSW pseudoprimes (i.e. composite numbers that "pass" the test), not a single example is known.

5) This is the information age. Before posting, try doing a Forum search. If that is unfruitful, try feeding likely search parameters, e.g. "lucas pseudoprime" into your favorite Internet search engine. But be prepared to jump back. The hit parade will be a long one. It will take some practice to learn how to sort the wheat from the chaff. It is a skill worth learning.

I have just confirmed 2-PRP + Lucas(n,4,1) does not give any pseudoprimes for Jan Feitsma's list < 2^64. This is not surprising since Pari/GP uses TF + strong versions and min a for Lucas(n,a,1) with kronecker(a^2-4,n)==-1.

The "smart money" on there being inifinitely many pseudoprimes may never see the light of day!

[Andrew Usher]

The list Dr. Sardonicus shows is the initial part of the pseudoprimes I computed. It doesn't surprise me that they all fail to be 2-SPRP, and it may be a matter of faith that some tests or combined tests will have pseudoprimes because of the practical limits of how far we can compute.

The algorithm I came up with requires twice as many mulmods as a Fermat test, and this may well be optimal. Note that I computed, as I discussed, the bisection V(14,1), not V(4,1) - it saves time and the odd terms are never used anyway.

The term 'Lucas pseudoprime' was avoided because of its vagueness (it can refer to several different tests for each of infinitely many suitable Lucas sequences) so that it would not have adequately described what specifically I was looking at.

[chalsall]

Originally Posted by Andrew Usher

The list Dr. Sardonicus shows...

If I may please share. Reflect, etc et al...

I spent a delightful day today with three friends. We talked to each other. We heard each other. We supported each other. We got things done. Thanks for lunch, BTW... 8^)

When I read your language, Andrew, all I do is sigh... And ask myself how can you possibly have so much time to waste?

That is serious ask. Have a nice day.

[Andrew Usher]

Even if that were a sincere question it would not be your business, and also out of place in a thread about actual mathematics - which no one interested would call a waste of time.