mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-10-14, 17:40   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×3×11×17 Posts
Talking Fun with quadratic discriminant

Sure, I harp on about x^2-a*x+1=0 enough. It has discriminant D=a^2-4 which is (a-2)*(a+2). As ever we are here only concerned with (D,n)==-1.

The companion matrix of this characteristic equations is [a,-1;1,0].

I now consider the tests Mod(Mod(x-1,n),x^2-a*x+1)^(n+1) and Mod(Mod(x+1,n),x^2-a*x+1)^(n+1), for reasons which will become apparent.

In terms of matrices these are [a+1,-1;1,1]^(n+1) mod n and [a-1,-1;1,-1]^(n+1) mod n.

These matrices have characteristic equations y^2-(a+2)*y+(a+2)==0 and y^2--(a-2)*y-(a-2)=0.

Now you see the connection with the discriminant!

The first equation can be transformed into Mod(Mod(z,n),z^2-((a+2)^2/(a+2)-2)*z+1)^((n+1)/2)==kronecker(a+2,n) and Mod(a+2,n)^((n-1)/2)==kronecker(a+2,n).

Simplifying the equation in z to z^2-a*z+1 and multiplying the two bases of the tests together we get the test:

tst1(n,a)=Mod(Mod((a+2)*z,z^2-a*z+1)^((n+1)/2)==a+2.

Doing the same process -- some homework on your behalf -- to the second test yields:

tst2(n,a)=Mod(Mod(2-a)*z,z^2+a*z+1)^((n+1)/2)==2-a.

Big assumption: I claim that any pseudoprime for both test combined also have a pseudoprime for tst1(n,1) and tst2(n,1), So the only thing left for the grand test is to check gcd(a^2-1,n)==1 and ensure a is not 0.

More to follow on the verification process...


Last fiddled with by paulunderwood on 2022-10-14 at 19:12
paulunderwood is offline   Reply With Quote
Old 2022-10-14, 20:44   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·11·17 Posts
Default

Here are the two major sub-tests:

Code:
{tst1(n,a)=Mod(Mod((a+2)*z,n),z^2-a*z+1)^((n+1)/2)==a+2;}
{tst2(n,a)=Mod(Mod((2-a)*z,n),z^2+a*z+1)^((n+1)/2)==2-a;}
The grand test to be fooled is:

Code:
{tst(n,a)=
n%2==1&&
a!=0&&
kronecker(a^2-4,n)==-1&&
gcd(a^2-1,n)==1&&
tst1(n,a)&&
tst2(n,a);}
The algorithm is:

Code:
{alg(n)=
if(n==2||n==3,return(1));
if(n%2==0,return(0));
if(issquare(n),return(0));
a=3;while(kronecker(a^2-4,n)!=1||gcd(a^2-1,n)!=1,a++);
tst1(n,a)&&tst2(n,a);}
My verification code based on the "big assumption" above:

Code:
{vtst(lb,ub)=
if(lb%6!=5,lb++);
forstep(lb,ub,6
    if(!ispseudoprime(n)&&tst1(n,1),
        for(a=3,(n-1)/2,
            if(kronecker(a^2-4,n)==-1&&tst1(n,a)&&tst2(n,a),
                r=[n,a,gcd(a^2-1,n)];
                print(r);write("vtst_results",r)))));}
(The tst2(n,1) is equivalent to n%6==5 for which the jacobi symbol of discriminant -3 is -1.)


Last fiddled with by paulunderwood on 2022-10-15 at 00:18 Reason: fixed tst. tst1 and tst2
paulunderwood is offline   Reply With Quote
Old 2022-10-15, 00:19   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·11·17 Posts
Default

Quote:
tst(1091*26161, 2093977)
1
Fooled
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New {function, criterion, theorem, conjecture} for discriminant of congruence Zcyyu Miscellaneous Math 40 2021-08-28 02:51
Trying to solve discriminant of a cubic polynomial by product method carpetpool Abstract Algebra & Algebraic Number Theory 6 2018-11-28 13:16
Quadratic PRP test carpetpool Miscellaneous Math 5 2018-03-13 13:37
the multiplicativ structur of the discriminant for quadratic polynomials bhelmes Computer Science & Computational Number Theory 3 2017-05-27 01:33
Polynomial Discriminant is n^k for an n-1 degree polynomial carpetpool Miscellaneous Math 14 2017-02-18 19:46

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


Thu Feb 2 14:36:42 UTC 2023 up 168 days, 12:05, 1 user, load averages: 1.05, 1.06, 1.10

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.

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