what is the best primality software? - Page 2

bbb120 · 2022-09-14, 06:22

Quote:

Originally Posted by rogue

That depends upon the numbers you want to test. Please provide more details.

why prp test? miller-rabin is much better than prp test！

VBCurtis · 2022-09-14, 07:03

If you have such strong opinions about all this, why are you asking us what to run?
Define "better". Faster?
False positives don't matter beyond a couple hundred digits, and if your interests are under 500 digits then speed doesn't matter for what software you pick- you should pick the one you can use without asking 30 questions where you argue with the answers.

bbb120 · 2022-09-14, 08:13

Quote:

Originally Posted by VBCurtis

If you have such strong opinions about all this, why are you asking us what to run?
Define "better". Faster?
False positives don't matter beyond a couple hundred digits, and if your interests are under 500 digits then speed doesn't matter for what software you pick- you should pick the one you can use without asking 30 questions where you argue with the answers.

I can not understand your words very well ,please use simple English.

pfgw output
-----------------------------------
PFGW Version 4.0.3.64BIT.20220704.Win_Dev [GWNUM 29.8]

***WARNING! file input2 may have already been fully processed.

Primality testing 999998912894617 [N+1, Brillhart-Lehmer-Selfridge]
Running N+1 test using discriminant 5, base 5+sqrt(5)
999998912894617 is prime! (0.0011s+0.0006s)

Done.
-----------------------------------
it tell me that 999998912894617 is a prime！
but
5085473*196638329=999998912894617=(3*m - 1) (116*m + 1),where m=1695158

BUG!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

kar_bon · 2022-09-14, 08:27

How you call pfgw64?

I got

Code:

>pfgw64 -q999998912894617
PFGW Version 4.0.3.64BIT.20220704.Win_Dev [GWNUM 29.8]

Switching to Exponentiating using GMP
999998912894617 is composite: RES64: [0003827DA76C6B9C] (0.0001s+0.0033s)

bbb120 · 2022-09-14, 08:30

Quote:

Originally Posted by kar_bon

How you call pfgw64?

I got

Code:

>pfgw64 -q999998912894617
PFGW Version 4.0.3.64BIT.20220704.Win_Dev [GWNUM 29.8]

Switching to Exponentiating using GMP
999998912894617 is composite: RES64: [0003827DA76C6B9C] (0.0001s+0.0033s)

Code:

pfgw -tp input2

it should tell me this number is a lucas-prp not a prime!
so It must be a BUG!

rogue · 2022-09-14, 12:39

Before you do a primality test you should search for factors then run a PRP test.

Although -f doesn't find a factor, -f10000 does.

Code:

pfgw64 -f10000 -tp -q999998912894617 -Cverbose
PFGW Version 4.0.0.64BIT.20190330.Win_Dev [GWNUM 29.7]

Factoring numbers to 10000% of normal.

Primality testing 999998912894617 [N+1, Brillhart-Lehmer-Selfridge]
trial factoring to 10000000
factors: 5085473*196638329
999998912894617 is factored (0.0736s+0.0001s)

As shown above a PRP test (no -t switch) shows PRP.

-tc and -tm show composite.

I see that -tp shows prime, but the number being tested does not meet the conditions that are necessary for the test output to be valid.

-tm is used for numbers of the form k*b^n+1. -tp is used for numbers of the form k*b^n-1.

Dr Sardonicus · 2022-09-14, 12:40

Quote:

Originally Posted by bbb120

why prp test? miller-rabin is much better than prp test！

I see two possibilities here. One is, you don't know the definition of "prp test." The other is, you are feigning an ignorance you do not own. Either way, it looks like trolling to me.

Quote:

Originally Posted by bbb120

-----------------------------------
PFGW Version 4.0.3.64BIT.20220704.Win_Dev [GWNUM 29.8]

***WARNING! file input2 may have already been fully processed.

Primality testing 999998912894617 [N+1, Brillhart-Lehmer-Selfridge]
Running N+1 test using discriminant 5, base 5+sqrt(5)
999998912894617 is prime! (0.0011s+0.0006s)

Done.

If N == 2 or 3 (mod 5) is prime, then (5 + sqrt(5))^(N+1) is congruent to 20 (mod N).

I ran this test two different ways in Pari-GP for n=999998912894617 (which is congruent to 2 (mod 5)) and got the same answer. It isn't 20 Mod N. The test shows N is composite.

? n=999998912894617;r1=Mod(Mod(1,n)*x,x^2-10*x+20)^(n+1);print(lift(r1))
Mod(988864715305694, 999998912894617)

? n=999998912894617;r2=Mod(Mod(1,n)*(2*x+4),x^2-x-1)^(n+1);print(lift(r2))
Mod(988864715305694, 999998912894617)

bbb120 · 2022-09-15, 01:04

Quote:

Originally Posted by Dr Sardonicus

I see two possibilities here. One is, you don't know the definition of "prp test." The other is, you are feigning an ignorance you do not own. Either way, it looks like trolling to me.

If N == 2 or 3 (mod 5) is prime, then (5 + sqrt(5))^(N+1) is congruent to 20 (mod N).

I ran this test two different ways in Pari-GP for n=999998912894617 (which is congruent to 2 (mod 5)) and got the same answer. It isn't 20 Mod N. The test shows N is composite.

? n=999998912894617;r1=Mod(Mod(1,n)*x,x^2-10*x+20)^(n+1);print(lift(r1))
Mod(988864715305694, 999998912894617)

? n=999998912894617;r2=Mod(Mod(1,n)*(2*x+4),x^2-x-1)^(n+1);print(lift(r2))
Mod(988864715305694, 999998912894617)

my mathematica code to calculate (5+sqrt(5))^(n+1) mod n n=999998912894617

Code:

Clear["Global`*"];(*Clear all variables*)
(*计算calculate:(a+b*sqrt(x))^m mod n*)
QuadraticMod[a_,b_,x_,m_,n_]:=Module[
    {aa,bb,kk,m2},
    m2=IntegerDigits[m,2];(*把m写成二进制的方式*)
    {aa,bb}={1,0};(*初始值*)
    Do[
        {aa,bb}=Mod[{aa*aa+bb*bb*x,2*aa*bb},n];(*(aa+bb*sqrt(x))^2 mod n*)
        If[m2[[kk]]==1,
            {aa,bb}=Mod[{aa*a+bb*b*x,aa*b+a*bb},n](*(aa+bb*sqrt(x))*(a+b*sqrt(x)) mod n*)
        ],
    {kk,1,Length@m2}];
    Return[{aa,bb}](*output输出结果*)
]

Code:

n=999998912894617;
QuadraticMod[5,1,5,n+1,n]

output
{988864715305694, 0}
the same result with you. so It must be a bug in pfgw!

bbb120 · 2022-09-15, 02:28

Quote:

Originally Posted by Dr Sardonicus

I see two possibilities here. One is, you don't know the definition of "prp test." The other is, you are feigning an ignorance you do not own. Either way, it looks like trolling to me.

If N == 2 or 3 (mod 5) is prime, then (5 + sqrt(5))^(N+1) is congruent to 20 (mod N).

I ran this test two different ways in Pari-GP for n=999998912894617 (which is congruent to 2 (mod 5)) and got the same answer. It isn't 20 Mod N. The test shows N is composite.

? n=999998912894617;r1=Mod(Mod(1,n)*x,x^2-10*x+20)^(n+1);print(lift(r1))
Mod(988864715305694, 999998912894617)

? n=999998912894617;r2=Mod(Mod(1,n)*(2*x+4),x^2-x-1)^(n+1);print(lift(r2))
Mod(988864715305694, 999998912894617)

let

Code:

n=803837457453639491257079614341942108138837688287558145837488917522\
2974273765333652186502336163960045457915042023603208766569966760987284\
0439654082329287387918508691668573282677617710293896977394701670823042\
8687109997439976544144845341155872450633409279022275296229414984230688\
1685404326457534018329786111298960644845216191652872597534901

use command

Code:

pfgw -b2 input3.txt

it tell us

Code:

***WARNING! file input3.txt may have already been fully processed.

80383745745363949125......7534901 is 2-PRP! (0.0021s+0.0001s)

Done.

use command(select 14 as the base)

Code:

pfgw -b14 input3.txt

it tell us

Code:

PFGW Version 4.0.3.64BIT.20220704.Win_Dev [GWNUM 29.8]


***WARNING! file input3.txt may have already been fully processed.

80383745745363......72597534901 is 14-PRP! (0.0016s+0.0001s)

Done.

but
14^((n-1)/4)mod n not equal ±1
and 14^((n-1)/2)mod n equal 1 (not equal -1),
thus,miller rabin tell us that n must be a composite number
but,pfgw tell us n is 14-PRP
so pfgw must use fermat test as "prp test",not miller-rabin.

bbb120 · 2022-09-15, 02:30

Quote:

Originally Posted by rogue

Before you do a primality test you should search for factors then run a PRP test.

Although -f doesn't find a factor, -f10000 does.

Code:

pfgw64 -f10000 -tp -q999998912894617 -Cverbose
PFGW Version 4.0.0.64BIT.20190330.Win_Dev [GWNUM 29.7]

Factoring numbers to 10000% of normal.

Primality testing 999998912894617 [N+1, Brillhart-Lehmer-Selfridge]
trial factoring to 10000000
factors: 5085473*196638329
999998912894617 is factored (0.0736s+0.0001s)

As shown above a PRP test (no -t switch) shows PRP.

-tc and -tm show composite.

I see that -tp shows prime, but the number being tested does not meet the conditions that are necessary for the test output to be valid.

-tm is used for numbers of the form k*b^n+1. -tp is used for numbers of the form k*b^n-1.

Code:

but the number being tested does not meet the conditions that are necessary for the test output to be valid

I cannot understand this sentence very well!

VBCurtis · 2022-09-15, 03:15

A "bug" is unexpected behavior. Using a primality test that isn't known to be correct on your input is not a bug.

You don't understand the software, and you're mistaken about having found a bug. Maybe ease up on the accusations until you understand what the various pfgw flags and tests do?

2022-09-14, 08:27	#15
kar_bon Mar 2006 Germany 3003₁₀ Posts	How you call pfgw64? I got Code: >pfgw64 -q999998912894617 PFGW Version 4.0.3.64BIT.20220704.Win_Dev [GWNUM 29.8] Switching to Exponentiating using GMP 999998912894617 is composite: RES64: [0003827DA76C6B9C] (0.0001s+0.0033s)

2022-09-14, 12:39	#17
rogue "Mark" Apr 2003 Between here and the 3×23×101 Posts	Before you do a primality test you should search for factors then run a PRP test. Although -f doesn't find a factor, -f10000 does. Code: pfgw64 -f10000 -tp -q999998912894617 -Cverbose PFGW Version 4.0.0.64BIT.20190330.Win_Dev [GWNUM 29.7] Factoring numbers to 10000% of normal. Primality testing 999998912894617 [N+1, Brillhart-Lehmer-Selfridge] trial factoring to 10000000 factors: 5085473196638329 999998912894617 is factored (0.0736s+0.0001s) As shown above a PRP test (no -t switch) shows PRP. -tc and -tm show composite. I see that -tp shows prime, but the number being tested does not meet the conditions that are necessary for the test output to be valid. -tm is used for numbers of the form kb^n+1. -tp is used for numbers of the form k*b^n-1.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
FastECPP software and >50000 digit primality proof (reposted from NMBRTHRY)	Batalov	And now for something completely different	289	2023-01-30 19:55
For which types of primes is GPU primality test software available?	bur	GPU Computing	6	2020-08-28 06:20
Fastest software for Mersenne primality test?	JonathanM	Information & Answers	25	2020-06-16 02:47
Primality searches and primality successes	marco_calabresi	Information & Answers	3	2009-04-17 19:44
Software	TTn	PSearch	0	2004-05-04 13:16

2022-09-14, 07:03	#13
VBCurtis "Curtis" Feb 2005 Riverside, CA 13013₈ Posts	If you have such strong opinions about all this, why are you asking us what to run? Define "better". Faster? False positives don't matter beyond a couple hundred digits, and if your interests are under 500 digits then speed doesn't matter for what software you pick- you should pick the one you can use without asking 30 questions where you argue with the answers.

2022-09-15, 03:15	#22
VBCurtis "Curtis" Feb 2005 Riverside, CA 3³·11·19 Posts	A "bug" is unexpected behavior. Using a primality test that isn't known to be correct on your input is not a bug. You don't understand the software, and you're mistaken about having found a bug. Maybe ease up on the accusations until you understand what the various pfgw flags and tests do?