mersenneforum.org Math subforum (I am not a crank)
 Register FAQ Search Today's Posts Mark Forums Read

2023-01-24, 01:24   #1
Andrew Usher

Dec 2022

1B816 Posts
Math subforum (I am not a crank)

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:

Quote:
 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.

 2023-01-24, 03:14 #2 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 22·5·19·29 Posts 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.
 2023-01-24, 03:26 #3 Andrew Usher   Dec 2022 1101110002 Posts 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.
 2023-01-24, 06:53 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·3·1,697 Posts 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.
 2023-01-24, 08:42 #5 paulunderwood     Sep 2002 Database er0rr 123D16 Posts Here BPSW is king. I have come up with several test over the years for example: f=x^2-2 is "prime" if x^f==x mod f. 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). (x+2)^(n+1)==5+2*a (mod x^2-a*x+1) ( a minimal). 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. Last fiddled with by paulunderwood on 2023-02-10 at 19:32 Reason: The second test needed some extra conditions,
 2023-01-25, 01:18 #6 Andrew Usher   Dec 2022 44010 Posts 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.
 2023-01-25, 15:14 #7 Dr Sardonicus     Feb 2017 Nowhere 24·3·7·19 Posts 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 Ln = trace(norm(Mod(2 + x, x^2 - 3)^n)); L0 = 2, L1 = 4, Ln+2 = 4*Ln+1 - Ln. 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. Code: ? 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. Last fiddled with by Dr Sardonicus on 2023-01-25 at 15:19 Reason: Remove extraneous paren
2023-01-25, 15:54   #8
paulunderwood

Sep 2002
Database er0rr

7·23·29 Posts

Quote:
 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 Ln = trace(norm(Mod(2 + x, x^2 - 3)^n)); L0 = 2, L1 = 4, Ln+2 = 4*Ln+1 - Ln. 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. Code: ? 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!

Last fiddled with by paulunderwood on 2023-01-25 at 15:57

 2023-01-26, 01:01 #9 Andrew Usher   Dec 2022 23·5·11 Posts 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.
2023-01-26, 01:11   #10
chalsall
If I May

"Chris Halsall"
Sep 2002

2·5,647 Posts

Quote:
 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.

 2023-01-26, 02:38 #11 Andrew Usher   Dec 2022 23·5·11 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Lounge 21 2019-10-23 02:57 Uncwilly Miscellaneous Math 85 2017-12-10 16:03 Don Blazys Miscellaneous Math 646 2017-02-06 23:09 TimSorbet Forum Feedback 21 2007-03-06 19:21 Mystwalker Math 18 2005-05-30 03:53

All times are UTC. The time now is 21:38.

Thu Jun 1 21:38:55 UTC 2023 up 287 days, 19:07, 0 users, load averages: 0.70, 0.83, 0.99