mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Forum Feedback

Reply
 
Thread Tools
Old 2023-01-24, 01:24   #1
Andrew Usher
 
Dec 2022

22·59 Posts
Default 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.
Andrew Usher is offline   Reply With Quote
Old 2023-01-24, 03:14   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

252208 Posts
Default

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.
Uncwilly is offline   Reply With Quote
Old 2023-01-24, 03:26   #3
Andrew Usher
 
Dec 2022

23610 Posts
Default

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.
Andrew Usher is offline   Reply With Quote
Old 2023-01-24, 06:53   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

10,061 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2023-01-24, 08:42   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·281 Posts
Default

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) (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.

Last fiddled with by paulunderwood on 2023-01-24 at 09:42
paulunderwood is offline   Reply With Quote
Old 2023-01-25, 01:18   #6
Andrew Usher
 
Dec 2022

23610 Posts
Default

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.
Andrew Usher is offline   Reply With Quote
Old 2023-01-25, 15:14   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

23×19×41 Posts
Default

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
Dr Sardonicus is online now   Reply With Quote
Old 2023-01-25, 15:54   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·281 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
paulunderwood is offline   Reply With Quote
Old 2023-01-26, 01:01   #9
Andrew Usher
 
Dec 2022

111011002 Posts
Default

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.
Andrew Usher is offline   Reply With Quote
Old 2023-01-26, 01:11   #10
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22×47×59 Posts
Default

Quote:
Originally Posted by Andrew Usher View Post
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.
chalsall is online now   Reply With Quote
Old 2023-01-26, 02:38   #11
Andrew Usher
 
Dec 2022

22×59 Posts
Default

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.
Andrew Usher is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Was Rejected as a Crank Idea 500 Years Ago a1call Lounge 21 2019-10-23 02:57
Do-it-yourself, crank, mersenne prediction thread. Uncwilly Miscellaneous Math 85 2017-12-10 16:03
Standard crank division by zero thread Don Blazys Miscellaneous Math 646 2017-02-06 23:09
Crank Emoticon TimSorbet Forum Feedback 21 2007-03-06 19:21
Proposal: "Math for beginners" subforum Mystwalker Math 18 2005-05-30 03:53

All times are UTC. The time now is 14:08.


Wed Feb 8 14:08:06 UTC 2023 up 174 days, 11:36, 1 user, load averages: 0.71, 0.82, 0.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔