mersenneforum.org  

Go Back   mersenneforum.org > Search Forums

Showing results 1 to 25 of 35
Search took 0.01 seconds.
Search: Posts Made By: paulunderwood
Forum: Miscellaneous Math 2022-02-05, 06:26
Replies: 34
Views: 6,449
Posted By paulunderwood
Question Generalization II

I have now devised a general test of the polynomial x^2-b^r*x+b with an Euler PRP test for the discriminant b^(2*r)-4*b:

{tst(n,b,r)=local(t=lift(Mod(b,n)^(2*r-1)),k=kronecker(b,n));...
Forum: Miscellaneous Math 2022-01-31, 15:32
Replies: 34
Views: 6,449
Posted By paulunderwood
Red face Generalization

Based on a Lucas PRP test over x^2-b^r*x+b, I have come up with a general test:


{tst(n,b,r)=local(t=lift(Mod(b,n)^(2*r-1)));
kronecker(b,n)==-1&&
kronecker(t-4,n)==1&&
gcd(t-3,n)==1&&...
Forum: Miscellaneous Math 2021-10-26, 05:03
Replies: 34
Views: 6,449
Posted By paulunderwood
version for bash

The attached program returns exit(0) iff the input is 2-Euler PRP and Lucas PRP. (It also uses gcd((r-1)*(2*r-1),n-1)<=2.)

// gcc -o prp_v2 prp_v2.c -lgmp
// bash use case:-
/*
for i in...
Forum: Miscellaneous Math 2021-10-24, 15:38
Replies: 34
Views: 6,449
Posted By paulunderwood
2 selfidge version

We can fuse the Euler and Lucas test thusly:


{
tst(n,r)=local(fr=lift(Mod(4,n)^r));
gcd((r-1)*(2*r-1),n-1)<=2&&
kronecker(fr-8,n)==-1&&
Mod(Mod(2*x,n),x^2-(fr/2-2)*x+1)^((n+1)/2)==2;
}
Forum: Miscellaneous Math 2021-10-24, 08:25
Replies: 34
Views: 6,449
Posted By paulunderwood
A slight speed up

Rather than taking gcd(4^r-4,n)==1 and gcd(4^r-2,n)==1 the substitute gcd((r-1)*(2*r-1),n-1)<=2 is quicker, resulting in the test:


{
tst(n,r)=local(k=kronecker(2,n);fr=lift(Mod(4,n)^r));...
Forum: Miscellaneous Math 2021-10-20, 02:59
Replies: 34
Views: 6,449
Posted By paulunderwood
GMP code for test #3

I have coded up test #3 from the above paper.


// gcc -o prp prp.c -lgmp
// usages:-
// ./prp
// ./prp <integer>
// echo "print(<expression>)" | gp -q | ./prp
Forum: Miscellaneous Math 2021-07-08, 03:01
Replies: 34
Views: 6,449
Posted By paulunderwood
Revised paper

Here us the revised paper. I'll leave the original up for contrast, :book: :book:
Forum: Miscellaneous Math 2021-07-07, 19:40
Replies: 34
Views: 6,449
Posted By paulunderwood
It occurred to me that since the tests involve...

It occurred to me that since the tests involve t^2+something that only half of t might be used. For example:

{
tst(n)=local(t=2,k=kronecker(-2,n),limit=2*log(n)*log(log(n)),l=0,nm1d2=(n-1)/2);...
Forum: Miscellaneous Math 2021-07-06, 15:13
Replies: 34
Views: 6,449
Posted By paulunderwood
Four Lucas Tests

Here my paper distilled from this thread :book:
Forum: Miscellaneous Math 2021-07-02, 01:44
Replies: 34
Views: 6,449
Posted By paulunderwood
If r=(z+2)/4 then the quadratic x^2+(t^2/2+2)*x+1...

If r=(z+2)/4 then the quadratic x^2+(t^2/2+2)*x+1 is x^2+(2^((z+2)/2)/2+2)*x+1 is x^2+(2^(z/2)*2/2+2)*x+1. Since 2^(z/2)==-1 then the quadratic reduces to x^2+x+1 which is cyclotomic. A similar...
Forum: Miscellaneous Math 2021-06-29, 01:55
Replies: 34
Views: 6,449
Posted By paulunderwood
For my blanket testing of all r, I notice those n...

For my blanket testing of all r, I notice those n that require a gcd are 5 mod 6. This will speed up a little of my search where "the pattern" holds.

Status: all 2-PSPs < 3*10^10 and using "the...
Forum: Miscellaneous Math 2021-06-28, 15:58
Replies: 34
Views: 6,449
Posted By paulunderwood
Algorithm

Here is the algorithm for x^2-2^r*x-2


{
tst(n)=local(t=2); \\ t=2^r
if(n==2||n==3,return(1)); \\ trivialiies
if(n%2==0||issquare(n)||Mod(-2,n)^((n-1)/2)!=kronecker(-2,n),return(0)); \\ even...
Forum: Miscellaneous Math 2021-06-28, 11:58
Replies: 34
Views: 6,449
Posted By paulunderwood
Smile Assuming z%4==2 and ...

Assuming z%4==2 and Mod(Mod(x,n),x^2+(t^2/2+2)*x+1)^((n+1)/2)==kronecker(-2,n) are necessary conditions, -- poof anyone? -- the next to break "the pattern" is


{
for(v=305962,#V,n=V[v];...
Forum: Miscellaneous Math 2021-06-27, 21:38
Replies: 34
Views: 6,449
Posted By paulunderwood
Only x^2-2^r*x-2

Just when I was about to give up on this thread I have a great test based on x^2-2^r*x-2, which can be transformed into

Mod(-2,n)^((n-1)/2)==kronecker(-2,n)...
Forum: Miscellaneous Math 2021-06-26, 20:32
Replies: 34
Views: 6,449
Posted By paulunderwood
Fibonacci

Back to the drawing board...

Restrict n to 3 or 7 mod 20. Then x^(n+1) == -b^2 (mod n, x^2-b*x-b^2) can be transformed into x^((n+1)/2) == -1 (mod n, x^2+3*x+1) and b^(n-1) == 1 (mod n). I am now...
Forum: Miscellaneous Math 2021-06-25, 21:25
Replies: 34
Views: 6,449
Posted By paulunderwood
I am slightly change the last test for practical...

I am slightly change the last test for practical purposes


{
tst(n,r)=local(t=lift(Mod(2,n)^r));
if(n==2||n==3||n==5,return(1));
if(gcd(30,n)!=1||issquare(n),return(0));...
Forum: Miscellaneous Math 2021-06-25, 12:39
Replies: 34
Views: 6,449
Posted By paulunderwood
I have tested n < 3*10^11. If r=1 the this...

I have tested n < 3*10^11.

If r=1 the this test is the same as the $620 quest given on this page (https://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html) which purports to have around 740...
Forum: Miscellaneous Math 2021-06-23, 18:29
Replies: 34
Views: 6,449
Posted By paulunderwood
GMP is an order quicker than Pari/GP for this...

GMP is an order quicker than Pari/GP for this task. I have attached my GMP code. Note that it misses out x^2-x-4, but it would take a minute to test this special case with Pari/GP.

I fixed that...
Forum: Miscellaneous Math 2021-06-21, 23:34
Replies: 34
Views: 6,449
Posted By paulunderwood
Cool Only x^2-2^r*x-4

Based on only x^2-2^r*x-4 ...

And it's clunky:


{
tst(n,r)=local(t=lift(Mod(2,n)^r));
((n%4==1&&gcd(t^2+4,n)==1)||
(n%4==3&&gcd(t^2+8,n)==1))&&
kronecker(t^2+16,n)==-1&&
Forum: Miscellaneous Math 2021-06-21, 20:49
Replies: 34
Views: 6,449
Posted By paulunderwood
Lightbulb base 3 variant

This time based on x^2-3^r*x+-9 ...

n%4==1:


{
tst(n,r)=local(t=lift(Mod(3,n)^r));
gcd(t^2-3,n)==1&&gcd(t^2-9,n)==1&&
kronecker(t^2-4*9,n)==-1&&
Mod(3,n)^(n-1)==1&&
Forum: Miscellaneous Math 2021-06-21, 16:48
Replies: 34
Views: 6,449
Posted By paulunderwood
Smile 1+2 selfridges

Based on x^2-2^r*x+-4 ...

If n%4==1 then:


{
tst(n,r)=local(t=lift(Mod(2,n)^r));
gcd(t^2-4,n)==1&&
kronecker(t^2-16,n)==-1&&
Mod(2,n)^(n-1)==1&&
Forum: Miscellaneous Math 2021-06-20, 17:33
Replies: 34
Views: 6,449
Posted By paulunderwood
I have verified this for all r for all n<10^11. ...

I have verified this for all r for all n<10^11.

I will convert to GMP soon.
Forum: Miscellaneous Math 2021-06-20, 05:04
Replies: 34
Views: 6,449
Posted By paulunderwood
Thumbs up Efficent Test

The efficient test is:


{
tst(n,r)=local(t=lift(Mod(1/2,n)^r));
gcd(t^2-1,n)==1&&
gcd(t-2,n)==1&&
kronecker(t^2-4*t,n)==-1&&
Mod(2,n)^((n-1)/2)==kronecker(t,n)&&...
Forum: Miscellaneous Math 2021-06-20, 00:22
Replies: 34
Views: 6,449
Posted By paulunderwood
Cool Extra gcd

This test looks good:


{
tst(n,r)=local(t=lift(Mod(2,n)^r));
gcd(t^2-1,n)==1&&
gcd(2*t-1,n)==1&&
kronecker(1-4*t,n)==-1&&
Mod(2,n)^((n-1)/2)==kronecker(t,n)&&...
Forum: Miscellaneous Math 2021-06-19, 08:02
Replies: 34
Views: 6,449
Posted By paulunderwood
Restricted domain variation

Here I test over

x^2-x+2^r where kronecker(1-4*2^r,n)==-1
x^2-x-2^r where kronecker(1+4*2^r,n)==-1

If r is even this is the same as:

2^(n-1)==1 (mod n)
x^((n+1)/2)==1 (mod n,...
Showing results 1 to 25 of 35

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


Mon Dec 5 16:57:52 UTC 2022 up 109 days, 14:26, 0 users, load averages: 1.02, 1.05, 1.09

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.

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