PRP test largely on input number

lukerichards · 2019-03-17, 18:08

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⁵⁰⁴²⁰⁶+1, having discovered last March that 3⁵⁰⁴²⁰⁶+2 is a PRP.

Thanks to some people on here, I found some factors of 3⁵⁰⁴²⁰⁶+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.

a1call · 2019-03-17, 18:46

Congratulations!

according to PFGW:

Code:

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

GP2 · 2019-03-17, 18:56

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.

lukerichards · 2019-03-17, 19:02

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?

GP2 · 2019-03-17, 19:11

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

a1call · 2019-03-17, 19:24

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/

lukerichards · 2019-03-17, 22:32

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?

wblipp · 2019-03-17, 22:42

Quote:

Originally Posted by lukerichards

I'm now wondering again about factoring 3⁵⁰⁴²⁰⁶+1, having discovered last March that 3⁵⁰⁴²⁰⁶+2 is a PRP.

You should also consider a P+1 proof. 3⁵⁰⁴²⁰⁶+3 = 3⁵⁰⁴²⁰⁷+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.

axn · 2019-03-18, 02:45

Quote:

Originally Posted by wblipp

You should also consider a P+1 proof. 3⁵⁰⁴²⁰⁶+3 = 3⁵⁰⁴²⁰⁷+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.

GP2 · 2019-03-18, 03:50

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?

lukerichards · 2019-03-18, 06:14

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.

2019-03-17, 18:08	#1
lukerichards "Luke Richards" Jan 2018 Birmingham, UK 2⁵×3² 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 3⁵⁰⁴²⁰⁶+1, having discovered last March that 3⁵⁰⁴²⁰⁶+2 is a PRP. Thanks to some people on here, I found some factors of 3⁵⁰⁴²⁰⁶+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 7·283 Posts	Congratulations! according to PFGW: Code: .....3315861 is 3-PRP! (1388.4907s+0.6161s)

2019-03-17, 19:24	#6
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 1981₁₀ 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

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