mersenneforum.org what is the best primality software?
 Register FAQ Search Today's Posts Mark Forums Read

2022-09-14, 06:22   #12
bbb120

"特朗普trump"
Feb 2019

22×3×11 Posts

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！

 2022-09-14, 07:03 #13 VBCurtis     "Curtis" Feb 2005 Riverside, CA 130138 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-14, 08:13   #14
bbb120

"特朗普trump"
Feb 2019

22×3×11 Posts

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!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Last fiddled with by bbb120 on 2022-09-14 at 08:21

 2022-09-14, 08:27 #15 kar_bon     Mar 2006 Germany 300310 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, 08:30   #16
bbb120

"特朗普trump"
Feb 2019

8416 Posts

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!

 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: 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.
2022-09-14, 12:40   #18
Dr Sardonicus

Feb 2017
Nowhere

141258 Posts

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)

2022-09-15, 01:04   #19
bbb120

"特朗普trump"
Feb 2019

22×3×11 Posts

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*)
{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!

2022-09-15, 02:28   #20
bbb120

"特朗普trump"
Feb 2019

22×3×11 Posts

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.

2022-09-15, 02:30   #21
bbb120

"特朗普trump"
Feb 2019

22·3·11 Posts

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!

 2022-09-15, 03:15 #22 VBCurtis     "Curtis" Feb 2005 Riverside, CA 33·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?

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 289 2023-01-30 19:55 bur GPU Computing 6 2020-08-28 06:20 JonathanM Information & Answers 25 2020-06-16 02:47 marco_calabresi Information & Answers 3 2009-04-17 19:44 TTn PSearch 0 2004-05-04 13:16

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

Tue Feb 7 08:12:17 UTC 2023 up 173 days, 5:40, 1 user, load averages: 1.27, 1.20, 1.11