mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-03-22, 19:36   #23
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29×151 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Without checking Feitsma, we now have simple tests for n%8 = {3,5,7}
Transforming the test of x over x^2-136*x+16, I have now checked Feitsma's 2^64 PSP-2 list against:
(n%8==3||n%8==5)&&Mod(Mod(x,n),x^2-1154*x+1)^((n+1)/2)==1.

Given the test Mod(Mod(x+2),x^2+1)^(n+1)==5 seems to be good enough for n%4==3, then n%8==3 is covered by both tests. Which you choose depends on your needs and FFT arithmetic etc.

I am pleased with this advancement spurred on by the good doctor.

Similar antics for 3 mod 8 and 5 mod 8 can be done with x^2-20*x+2 with discriminant 2*2^2*3^2. Fietsma's list check out with Euler 2-PSPs against (n%8==3||n%8==5)&&Mod(Mod(x,n),x^2-198*x+1)^((n+1)/2)==kronecker(2,n).

Last fiddled with by paulunderwood on 2022-03-22 at 20:01
paulunderwood is offline   Reply With Quote
Old 2022-03-22, 19:43   #24
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

137248 Posts
Default

I did come up with a "reduced" version of part of your condition Mod(Mod(1,n)+x,1+x^4)^n = Mod(1, n)*(1 - x) for n == 5 (mod 8)

First, when n == 5 (mod 8), lift(Mod(1 + x, 1 + x^4)^n) is a polynomial of degree less than 4, in which the coefficients of x^3 and x^2 are always equal, and the coefficients of x and 1 are always equal and opposite.

Let ak be the coefficient of x in lift(Mod(1 + x, x^2 - 2)^k). This is a "Fibonacci-like" sequence: a0 = 0, a1 = 1, and ak+2 = 2*ak+1 + ak.

Starting with a1 we have 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, ...

When n == 5 (mod 8) the coefficients of x^3 and x^2 in lift(Mod(1 + x, 1 + x^4)^n) are divisible by n when n divides a(n+1)/2.

Note that 5 divides a3 = 5 and 13 divides a7 = 169, but 21 does not divide a11 = 5741.

I have not checked for composite n == 5 (mod 8) which fulfill this condition. (As you have noted, to satisfy your condition, n also has to be a base-2 pseudoprime.)
Dr Sardonicus is offline   Reply With Quote
Old 2022-03-22, 22:14   #25
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29·151 Posts
Default

I don't see why it has to be base 2 Fermat PRP; The norm is -1.

Last fiddled with by paulunderwood on 2022-03-22 at 22:53
paulunderwood is offline   Reply With Quote
Old 2022-03-23, 00:07   #26
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·52·61 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I don't see why it has to be base 2 Fermat PRP; The norm is -1.
By "your condition" I mean, any of Mod(Mod(1,n) + x, x^4 + 1)^n == Mod(1 + x^r, x^4 + 1) for n == r (mod 8), r =3, 5, or 7.

Any of these conditions imply that Mod(2,n)^n = Mod(2,n).

My "reduced" condition does NOT imply that Mod(2,n)^n = Mod(2,n) (see example next paragraph). It only covers part of the test for n == 5 (mod 8). It merely insures that in Mod(Mod(1,n) + x, x^4 + 1)^n, the coefficients of x^3 and x^2 are 0.

A mindless numerical sweep found that 1189 = 29*41 is not a 2-psp but does satisfy my "reduced" condition.

I note that 341, a 2-psp congruent to 5 (mod 8), does not satisfy my "reduced" condition.

So combining 2-psp with my "reduced" condition may work fairly well for n == 5 (mod 8), but I suspect there are 2-psp's congruent to 5 (mod 8) which satisfy my "reduced" condition, but not your condition

Mod(Mod(1,n) + x, x^4 + 1) = Mod(Mod(1,n) - x, x^4 + 1).
Dr Sardonicus is offline   Reply With Quote
Old 2022-03-23, 13:01   #27
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×52×61 Posts
Default

If n == 3 (mod 8) is prime, then Mod(Mod(1,n)+x,x^4 + 1)^n == Mod(Mod(1,n) + Mod(1,n)*x^3, x^4 + 1) coefficients of x and x^2 are 0

If n == 5 (mod 8) is prime, then Mod(Mod(1,n)+x,x^4 + 1)^n == Mod(Mod(1,n) + Mod(-1,n)*x, x^4 + 1) coefficients of x^2 and x^3 are 0

If n == 7 (mod 8) is prime, then Mod(Mod(1,n)+x,x^4 + 1)^n == Mod(Mod(1,n) + Mod(-1,n)*x^3, x^4 + 1) coefficients of x and x^2 are 0

The condition that any of these congruences hold (mod n) implies that Mod(2,n)^n == Mod(2,n).

Let lift(Mod(1+x, x^2 - 2)^k) = F[sub]k[sub]*x + Lk

The "reduced" partial conditions that the "wrong" coefficients of Mod(Mod(1,n)+x, x^4 + 1)^n are zero, are:

n == 3 (mod 8): n divides L(n+1)/2

n == 5 (mod 8): n divides F(n+1)/2

n == 7 (mod 8) n divides L(n-1)/2

The "reductions" are possible because they are conditions of divisibility by n, and n is odd. This allows one to ignore minus signs and powers of 2 in the relevant coefficients.

The main part of getting rid of powers of 2 is to note that in the characteristic polynomial x^2 + 136*x + 16, substituting x = 4*x and dividing through by 16 gives x^2 + 34*x + 1.

It is then a simple matter to figure out the correct power of 2 in the coefficients, divide it out, and match up the (absolute values of) two consecutive of the resulting odd numbers to coefficients below.

Further substituting -x for x in x^2 + 34*x + 1 takes care of the minus signs, giving the polynomial x^2 - 34*x + 1. This is the characteristic polynomial of Mod(1+x, x^2 - 2)^4.

Code:
? for(i=1,20,f=lift(Mod(1+x,x^2-2)^i);print(i" "f))
1 x + 1
2 2*x + 3
3 5*x + 7
4 12*x + 17
5 29*x + 41
6 70*x + 99
7 169*x + 239
8 408*x + 577
9 985*x + 1393
10 2378*x + 3363
11 5741*x + 8119
12 13860*x + 19601
13 33461*x + 47321
14 80782*x + 114243
15 195025*x + 275807
16 470832*x + 665857
17 1136689*x + 1607521
18 2744210*x + 3880899
19 6625109*x + 9369319
20 15994428*x + 22619537
UPDATE: I figured out semi-reasonable formulations of the second partial conditions for n == 3, 5, and 7 (mod 8). In each case, the two conditions together are equivalent to your quartic condition.

I saw no way to eliminate the powers of 2 from the second partial conditions. The F and L sequences are as above.

I still cannot believe I figured out the second condition for n == 5 (mod 8). That one gave me fits!


n == 3 (mod 8)

n divides L(n+1)/2 and (-1)^((n-3)/8) * 2^((n-3)/4) * L(n-1)/2 == 1 (mod n)


n == 5 (mod 8)

n divides F(n+1)/2 and (-1)^((n+3)/8) * 2^((n+3)/4) * F(n-1)/4 * L(n-1)/4 == 1 (mod n)

Note: Second condition can be restated as (-1)^((n+3)/8) * 2^((n-1)/4) * F(n-1)/2 == 1 (mod n)


n == 7 (mod 8)

n divides L(n-1)/2 and (-1)^((n+1)/8) * 2^((n-3)/4) * L(n+1)/2 == 1 (mod n)

Last fiddled with by Dr Sardonicus on 2022-03-24 at 00:03 Reason: Forgot exponents! and update
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 16:25.


Sun Dec 4 16:25:50 UTC 2022 up 108 days, 13:54, 0 users, load averages: 2.23, 1.91, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

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