mersenneforum.org PRP test largely on input number
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2019-03-17, 18:08 #1 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 4408 Posts PRP test largely on input number Hi, It's been ages since I devoted some attention to prime numbers. After a year or so since I came to accept that the cause was hopeless, I'm now wondering again about factoring 3504206+1, having discovered last March that 3504206+2 is a PRP. Thanks to some people on here, I found some factors of 3504206+1. Some small-ish ones are known to be composite, but there is this one here: http://factordb.com/index.php?id=1100000001124718606 $(3^{504206}+1)*(3^{226}+1)*(3^{194}+1)*(3^{46}+1)/(3^{21922}+1)/(3^{5198}+1)/(3^{4462}+1)/628417430425585476026210$ Which is of unknown status. If it is composite, fine. If its a PRP, I could then dedicate some time to trying to prove its primality, thus prove the primality of my original PRP. Any suggestions on suitable software for PRP-testing the large factor linked above? LLR won't allow such a complicated input.
 2019-03-17, 18:46 #2 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 3×11×59 Posts Congratulations! according to PFGW: Code: .....3315861 is 3-PRP! (1388.4907s+0.6161s)
2019-03-17, 18:56   #3
GP2

Sep 2003

2×1,291 Posts

Quote:
 Originally Posted by lukerichards http://factordb.com/index.php?id=1100000001124718606 $(3^{504206}+1)*(3^{226}+1)*(3^{194}+1)*(3^{46}+1)/(3^{21922}+1)/(3^{5198}+1)/(3^{4462}+1)/628417430425585476026210$ Which is of unknown status. If it is composite, fine. If its a PRP, I could then dedicate some time to trying to prove its primality, thus prove the primality of my original PRP. Any suggestions on suitable software for PRP-testing the large factor linked above? LLR won't allow such a complicated input.
PFGW can do this fairly quickly. I ran it already. No surprise, it is composite.

Note, you have to choose a PRP base other than 3, since that will give you a false positive here. You could choose 2 or 5, for instance:

Code:
./pfgw64 -b5 --help
Enter expression followed by carriage return:
(3^504206+1)*(3^226+1)*(3^194+1)*(3^46+1)/(3^21922+1)/(3^5198+1)/(3^4462+1)/628417430425585476026210
PFGW Version 3.8.3.64BIT.20161203.x86_Dev [GWNUM 28.6]

(3^504206+1)*(3^....0425585476026210 is composite: RES64: [07271415C222E58C] (780.3876s+0.0099s)
Even if it had been PRP, how could you prove primality of an arbitrary 225698-digit PRP? This cofactor is about 94% of the length of the original number, so your new problem would hardly be less difficult than your old problem.

2019-03-17, 19:02   #4
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts

Quote:
 Originally Posted by GP2 Even if it had been PRP, how could you prove primality of an arbitrary 225698-digit PRP? This cofactor is about 94% of the length of the original number, so your new problem would hardly be less difficult than your old problem.

Well, quite. I am aware of this. But in a series of highly improbable possibilities, if this had been PRP I'd have subtracted 1 from it and attempted to factor that number, in the hope that I would then get some large PRP factor, and so on.

Not likely, but worth spending an hour or two looking into.

Thanks to both of you for running it in PFGW. Are you running OpenPFGW?

2019-03-17, 19:11   #5
GP2

Sep 2003

2·1,291 Posts

Quote:
 Originally Posted by lukerichards Are you running OpenPFGW?
I am running pfgw64 from pfgw_linux_3.8.3_20170121.zip

I don't recall where I downloaded it, but based on this forum thread, it probably did come from the OpenPFGW archive at sourceforge

 2019-03-17, 19:24 #6 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 3·11·59 Posts I stand corrected. In base 5: Code: ....36795483315861 is composite: RES64: [07271415C222E58C] (1229.6702s+0.6114s) Link to PFGW download: https://sourceforge.net/projects/openpfgw/ Last fiddled with by a1call on 2019-03-17 at 19:24
2019-03-17, 22:32   #7
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

4408 Posts

Quote:
 Originally Posted by GP2 Code: ./pfgw64 -b5 --help Enter expression followed by carriage return: (3^504206+1)*(3^226+1)*(3^194+1)*(3^46+1)/(3^21922+1)/(3^5198+1)/(3^4462+1)/628417430425585476026210 PFGW Version 3.8.3.64BIT.20161203.x86_Dev [GWNUM 28.6] (3^504206+1)*(3^....0425585476026210 is composite: RES64: [07271415C222E58C] (780.3876s+0.0099s)

When I try the same input, I get:

Code:
Illegal instruction (core dumped)

Any idea what I'm doing wrong?

2019-03-17, 22:42   #8
wblipp

"William"
May 2003
New Haven

93816 Posts

Quote:
 Originally Posted by lukerichards I'm now wondering again about factoring 3504206+1, having discovered last March that 3504206+2 is a PRP.
You should also consider a P+1 proof. 3504206+3 = 3504207+1, which also has algebraic factors. Although also unlikely to factor, this side has multiple combinations that could reach sufficient factorizations. And unlike P-1, these factorizations would lead to a noticeably smaller prime.

2019-03-18, 02:45   #9
axn

Jun 2003

479010 Posts

Quote:
 Originally Posted by wblipp You should also consider a P+1 proof. 3504206+3 = 3504207+1, which also has algebraic factors.
3^504206+3 = 3(3^504205+1).

3^504205+1 does have a few algebraic factors, but not nearly as many as the other one.

2019-03-18, 03:50   #10
GP2

Sep 2003

1010000101102 Posts

Quote:
 Originally Posted by lukerichards When I try the same input, I get: Code: Illegal instruction (core dumped) Any idea what I'm doing wrong?
Does simpler input work? For instance, 3^504206+2

Are you running a 32-bit operating system?

2019-03-18, 06:14   #11
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts

Quote:
 Originally Posted by GP2 Does simpler input work? For instance, 3^504206+2 Are you running a 32-bit operating system?

Have tried 3^504206+2, as well as 3^226+1. Neither work.

Am running Ubuntu 18.04 64-bit.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post mersenne1588 Information & Answers 6 2019-02-12 22:13 Kalli Hofmann Information & Answers 1 2018-01-08 12:24 Welton Information & Answers 7 2016-07-29 12:07 Bundu Programming 20 2012-02-19 18:09 Capone GMP-ECM 17 2007-06-17 09:19

All times are UTC. The time now is 23:21.

Wed Dec 2 23:21:32 UTC 2020 up 83 days, 20:32, 2 users, load averages: 1.53, 1.70, 1.66

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