mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2019-03-17, 18:08   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

12016 Posts
Default 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.
lukerichards is offline   Reply With Quote
Old 2019-03-17, 18:46   #2
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·641 Posts
Default

Congratulations!

according to PFGW:

Code:
.....3315861 is 3-PRP! (1388.4907s+0.6161s)
a1call is offline   Reply With Quote
Old 2019-03-17, 18:56   #3
GP2
 
GP2's Avatar
 
Sep 2003

29·89 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
GP2 is offline   Reply With Quote
Old 2019-03-17, 19:02   #4
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

Quote:
Originally Posted by GP2 View Post
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?
lukerichards is offline   Reply With Quote
Old 2019-03-17, 19:11   #5
GP2
 
GP2's Avatar
 
Sep 2003

29×89 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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
GP2 is offline   Reply With Quote
Old 2019-03-17, 19:24   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

111100000112 Posts
Default

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
a1call is offline   Reply With Quote
Old 2019-03-17, 22:32   #7
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

12016 Posts
Default

Quote:
Originally Posted by GP2 View Post
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?
lukerichards is offline   Reply With Quote
Old 2019-03-17, 22:42   #8
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

92416 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
wblipp is offline   Reply With Quote
Old 2019-03-18, 02:45   #9
axn
 
axn's Avatar
 
Jun 2003

111448 Posts
Default

Quote:
Originally Posted by wblipp View Post
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.
axn is online now   Reply With Quote
Old 2019-03-18, 03:50   #10
GP2
 
GP2's Avatar
 
Sep 2003

258110 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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?
GP2 is offline   Reply With Quote
Old 2019-03-18, 06:14   #11
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Quote:
Originally Posted by GP2 View Post
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.
lukerichards is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How do I get a bigger number to test ? mersenne1588 Information & Answers 6 2019-02-12 22:13
Shift Number in LL Test Kalli Hofmann Information & Answers 1 2018-01-08 12:24
how can I test a number in any prime95? Welton Information & Answers 7 2016-07-29 12:07
sequential number test Bundu Programming 20 2012-02-19 18:09
ecm_factor returning the same number as input Capone GMP-ECM 17 2007-06-17 09:19

All times are UTC. The time now is 03:20.

Thu Oct 22 03:20:23 UTC 2020 up 42 days, 31 mins, 0 users, load averages: 1.69, 1.87, 1.85

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.