 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Software (https://www.mersenneforum.org/forumdisplay.php?f=10)
-   -   PRP test largely on input number (https://www.mersenneforum.org/showthread.php?t=24177)

 lukerichards 2019-03-17 18:08

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 3[SUP]504206[/SUP]+1, having discovered last March that 3[SUP]504206[/SUP]+2 is a PRP.

Thanks to some people on here, I found some factors of 3[SUP]504206[/SUP]+1. Some small-ish ones are known to be composite, but there is this one here:

[URL]http://factordb.com/index.php?id=1100000001124718606[/URL]

[TEX](3^{504206}+1)*(3^{226}+1)*(3^{194}+1)*(3^{46}+1)/(3^{21922}+1)/(3^{5198}+1)/(3^{4462}+1)/628417430425585476026210[/TEX]

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.

 a1call 2019-03-17 18:46

Congratulations!

according to PFGW:

[CODE]

.....3315861 is 3-PRP! (1388.4907s+0.6161s)

[/CODE]:smile:

 GP2 2019-03-17 18:56

[QUOTE=lukerichards;510978]
[URL]http://factordb.com/index.php?id=1100000001124718606[/URL]

[TEX](3^{504206}+1)*(3^{226}+1)*(3^{194}+1)*(3^{46}+1)/(3^{21922}+1)/(3^{5198}+1)/(3^{4462}+1)/628417430425585476026210[/TEX]

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.[/QUOTE]

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)
[/CODE]

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.

 lukerichards 2019-03-17 19:02

[QUOTE=GP2;510983]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.[/QUOTE]

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?

 GP2 2019-03-17 19:11

[QUOTE=lukerichards;510984]Are you running OpenPFGW?[/QUOTE]

I am running pfgw64 from pfgw_linux_3.8.3_20170121.zip

I don't recall where I downloaded it, but based on [URL="https://www.mersenneforum.org/showthread.php?t=13969"]this forum thread[/URL], it probably did come from the [URL="https://sourceforge.net/projects/openpfgw/files/"]OpenPFGW archive at sourceforge[/URL]

 a1call 2019-03-17 19:24

I stand corrected. In base 5:

[CODE]

....36795483315861 is composite: RES64: [07271415C222E58C] (1229.6702s+0.6114s)
[/CODE]

[url]https://sourceforge.net/projects/openpfgw/[/url]

 lukerichards 2019-03-17 22:32

[QUOTE=GP2;510983]
[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)
[/CODE][/QUOTE]

When I try the same input, I get:

[CODE]Illegal instruction (core dumped)[/CODE]

Any idea what I'm doing wrong?

 wblipp 2019-03-17 22:42

[QUOTE=lukerichards;510978]I'm now wondering again about factoring 3[SUP]504206[/SUP]+1, having discovered last March that 3[SUP]504206[/SUP]+2 is a PRP.[/QUOTE]

You should also consider a P+1 proof. 3[SUP]504206[/SUP]+3 = [URL="http://factordb.com/index.php?id=1100000001270038807"]3[SUP]504207[/SUP]+1[/URL], 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.

 axn 2019-03-18 02:45

[QUOTE=wblipp;510997]You should also consider a P+1 proof. 3[SUP]504206[/SUP]+3 = [URL="http://factordb.com/index.php?id=1100000001270038807"]3[SUP]504207[/SUP]+1[/URL], which also has algebraic factors. [/QUOTE]

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.

 GP2 2019-03-18 03:50

[QUOTE=lukerichards;510996]When I try the same input, I get:

[CODE]Illegal instruction (core dumped)[/CODE]

Any idea what I'm doing wrong?[/QUOTE]

Does simpler input work? For instance, 3^504206+2

Are you running a 32-bit operating system?

 lukerichards 2019-03-18 06:14

[QUOTE=GP2;511015]Does simpler input work? For instance, 3^504206+2

Are you running a 32-bit operating system?[/QUOTE]

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

Am running Ubuntu 18.04 64-bit.

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