mersenneforum.org

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]

Link to PFGW download:
[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.

lukerichards 2019-03-18 06:17

[QUOTE=axn;511008]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.[/QUOTE]


Thanks.


Last time I tackled this, I did actually partially factor the N+1 composite. I forgot how far.


[url]http://factordb.com/index.php?query=3%5E504206%2B3[/url]


The unknown-status large factor doesn't have a neat expression for forming it though:


[url]http://factordb.com/index.php?id=1100000001124807633[/url]

axn 2019-03-18 06:39

[QUOTE=lukerichards;511021]The unknown-status large factor doesn't have a neat expression for forming it though:


[url]http://factordb.com/index.php?id=1100000001124807633[/url][/QUOTE]
Check now.

GP2 2019-03-18 06:49

[QUOTE=lukerichards;511020]Have tried 3^504206+2, as well as 3^226+1. Neither work.


Am running Ubuntu 18.04 64-bit.[/QUOTE]

The program pfgw64 uses dynamically linked shared libraries. So maybe it's not finding them.

Try running ldd on the executable file and see what it tells you: [c]ldd pfgw64[/c]

I think on RedHat-based Linuxes, ld-linux-x86-64.so.2 is found at /lib64/ld-linux-x86-64.so.2 whereas on Ubuntu it's found at /lib/x86_64-linux-gnu/ld-linux-x86-64.so.2

lukerichards 2019-03-18 19:59

[QUOTE=GP2;511023]The program pfgw64 uses dynamically linked shared libraries. So maybe it's not finding them.

Try running ldd on the executable file and see what it tells you: [c]ldd pfgw64[/c]

I think on RedHat-based Linuxes, ld-linux-x86-64.so.2 is found at /lib64/ld-linux-x86-64.so.2 whereas on Ubuntu it's found at /lib/x86_64-linux-gnu/ld-linux-x86-64.so.2[/QUOTE]


Thanks for your advice here. I have run ldd, but the output means little to me on its own.


[CODE]user1@ubuntu-upstairs:~/OpenPFGW$ ldd pfgw64
linux-vdso.so.1 (0x00007ffd8af0b000)
libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007f9c7abb0000)
libstdc++.so.6 => /usr/lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007f9c7a820000)
libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f9c7a480000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f9c7a088000)
/lib64/ld-linux-x86-64.so.2 (0x00007f9c7add0000)
libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007f9c79e70000)
[/CODE]


I also have the static binary (pfgw64s) was well as the dynamic one and they both provide the same error, suggesting its possibly not a problem with dynamic links?

paulunderwood 2019-03-18 20:41

[QUOTE=lukerichards;511058]

I also have the static binary (pfgw64s) was well as the dynamic one and they both provide the same error, suggesting its possibly not a problem with dynamic links?[/QUOTE]

Do you have the GMP libgmp library installed?

I get:

[code] ldd pfgw64
linux-vdso.so.1 (0x00007ffe15fe1000)
libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007ff81fb44000)
libstdc++.so.6 => /usr/lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007ff81f7c2000)
libgmp.so.10 => /usr/lib/x86_64-linux-gnu/[COLOR="Red"]libgmp.so.10 [/COLOR](0x00007ff81f53f000)
libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007ff81f23b000)
libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007ff81f024000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007ff81ec85000)
/lib64/ld-linux-x86-64.so.2 (0x00007ff81fd61000)[/code]

lukerichards 2019-03-18 20:52

[QUOTE=paulunderwood;511062]Do you have the GMP libgmp library installed?[/QUOTE]


Nope! Installing now...

lukerichards 2019-03-18 20:58

[QUOTE=lukerichards;511065]Nope! Installing now...[/QUOTE]


#headdesk


Installed from [url]https://gmplib.org/manual/Installing-GMP.html#Installing-GMP[/url]


Using latest version.


Still getting the same output from ldd.


Trying to compile using 'make' from source files on sourceforge throws this error:


[CODE]
g++: error: packages/gmp/64bit/libgmp.a: No such file or directory
g++: error: packages/gwnum/64bit/gwnum.a: No such file or directory
[/CODE]


So somehow, installing gmplib hasn't had the desired effect!

paulunderwood 2019-03-18 21:00

The library should be in the Ubuntu repository. Try

[CODE]sudo apt-get install libgmp10[/CODE]

For installing GMP from source you should have run (in the source directory):

[code]
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install build-essential
./configure
make
make check
sudo make install
[/code]

lukerichards 2019-03-18 21:31

[QUOTE=paulunderwood;511067]The library should be in the Ubuntu repository. Try

[CODE]sudo apt-get install libgmp10[/CODE]For installing GMP from source you should have run (in the source directory):

[code]
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install build-essential
./configure
make
make check
sudo make install
[/code][/QUOTE]


I did run that process exactly. And for good measure, I tried to install from apt-get and it told me I already have the latest version.


Have even tried the old favourite of 'turn it off and on again' but still getting the "Illegal instruction 'core dumped'" error.


Could it be that I need to pass pfgw an instruction to look in usr/bin for the GMP library?

lukerichards 2019-03-18 21:41

And if I try to build pfgw from source files I get:



[CODE]user1@ubuntu-upstairs:~/openpfgw-code-r646$ make
make -C pform/pflib
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pflib'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pflib'
make -C pform/pfmath
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfmath'
make[1]: '.libs/pfmath.a' is up to date.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfmath'
make -C pform/pfgwlib
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfgwlib'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfgwlib'
make -C pform/pfoo
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfoo'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfoo'
make -C pform/pfio
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfio'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfio'
make -C pform/pfgw
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfgw'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfgw'
g++ -O3 -m64 -DX86_64 -D_64BIT -I../../packages/gmp/64bit -I../../pfconfig/headers \
pform/pfgw/.libs/pfgw_main.a pform/pfio/.libs/pfio.a pform/pfoo/.libs/pfoo.a pform/pfgwlib/.libs/pfgwlib.a \
pform/pfmath/.libs/pfmath.a pform/pflib/.libs/pflib.a \
packages/gmp/64bit/libgmp.a packages/gwnum/64bit/gwnum.a -Wl,-no_pie -lpthread -lstdc++ -o pfgw64
g++: error: packages/gmp/64bit/libgmp.a: No such file or directory
g++: error: packages/gwnum/64bit/gwnum.a: No such file or directory
makefile:8: recipe for target 'pfgw64' failed
make: *** [pfgw64] Error 1
[/CODE]

Batalov 2019-03-18 21:42

[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]
You will need to recompile the binary. Both static and dynamic pfgw binaries core-dump on some CPUs (but not on most others), because of the way they are compiled.

They work for most people though, so the number of complains was not enough for them to reach the maintainer.

So roll up your sleeves and build the binary from the source.
[QUOTE=lukerichards;511074][CODE]g++: error: packages/gmp/64bit/libgmp.a: No such file or directory
g++: error: packages/gwnum/64bit/gwnum.a: No such file or directory
makefile:8: recipe for target 'pfgw64' failed
make: *** [pfgw64] Error 1
[/CODE][/QUOTE]
Build libgmp and gwnum, too, of course. Do you expect them to show up magically in that path?

lukerichards 2019-03-18 21:44

[QUOTE=Batalov;511075]You will need to recompile the binary. Both static and dynamic pfgw binaries core-dump on some CPUs (but not on most others), because of the way they are compiled.

They work for most people though, so the number of complains was not enough for them to reach the maintainer.

So roll up your sleeves and build the binary from the source.[/QUOTE]


I think our posts have crossed.



See here:


[url]https://www.mersenneforum.org/showpost.php?p=511074&postcount=21[/url]

lukerichards 2019-03-18 21:45

[QUOTE=Batalov;511075]Build libgmp too, of course.[/QUOTE]


Have done - as stated earlier in the thread, I have built libgmp from source inc succesful make, make check and sudo make install.


Have also built libgmp into the 64bit folder of the gmp packages directory within the pfgw source files.

paulunderwood 2019-03-18 21:46

[CODE]g++: error: packages/gmp/64bit/libgmp.a: No such file or directory
g++: error: packages/gwnum/64bit/gwnum.a: No such file or directory[/CODE]

Grab the file "libgmp.a" from your GMP compilation and put it in " packages/gmp/64bit/".

The download and compile the "Prime95/mprime" source and run "make -f make64" in the gwnum directory of the source and copy the file "gwnum.a" to the directory "packages/gwnum/64bit/".

Recompile PFGW.

lukerichards 2019-03-18 21:48

[QUOTE=paulunderwood;511078]Grab the file "libgmp.a" from your GMP compilation and put it in " packages/gmp/64bit/".[/QUOTE]


I don't have a libgmp.a :/


I have a libgmp.la?

Batalov 2019-03-18 21:52

On Ubuntu it is not going to be a smooth sailing. First you will need to build a static lib*.a. Second you will (suddenly) find that Ubuntu doesn't have necessary static system libs... etc etc. So you will have to build those as well from scratch, or try to get them from repo.

paulunderwood 2019-03-18 21:57

[QUOTE=lukerichards;511080]I don't have a libgmp.a :/


I have a libgmp.la?[/QUOTE]

It is here /usr/local/lib/libgmp.a

lukerichards 2019-03-18 21:57

[QUOTE=paulunderwood;511078][CODE]g++: error: packages/gmp/64bit/libgmp.a: No such file or directory
g++: error: packages/gwnum/64bit/gwnum.a: No such file or directory[/CODE]Grab the file "libgmp.a" from your GMP compilation and put it in " packages/gmp/64bit/".

The download and compile the "Prime/mprime" source and run "make -f make64" in the gwnum directory of the source and copy the file "gwnum.a" to the directory "packages/gwnum/64bit/".

Recompile PFGW.[/QUOTE]


Some success. Thanks so much for your time!


[CODE]
user1@ubuntu-upstairs:~/openpfgw-code-r646$ make
make -C pform/pflib
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pflib'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pflib'
make -C pform/pfmath
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfmath'
make[1]: '.libs/pfmath.a' is up to date.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfmath'
make -C pform/pfgwlib
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfgwlib'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfgwlib'
make -C pform/pfoo
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfoo'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfoo'
make -C pform/pfio
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfio'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfio'
make -C pform/pfgw
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfgw'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfgw'
g++ -O3 -m64 -DX86_64 -D_64BIT -I../../packages/gmp/64bit -I../../pfconfig/headers \
pform/pfgw/.libs/pfgw_main.a pform/pfio/.libs/pfio.a pform/pfoo/.libs/pfoo.a pform/pfgwlib/.libs/pfgwlib.a \
pform/pfmath/.libs/pfmath.a pform/pflib/.libs/pflib.a \
packages/gmp/64bit/libgmp.a packages/gwnum/64bit/gwnum.a -Wl,-no_pie -lpthread -lstdc++ -o pfgw64
/usr/bin/ld: cannot find -lgcc_s
/usr/bin/ld: cannot find -lgcc_s
collect2: error: ld returned 1 exit status
makefile:8: recipe for target 'pfgw64' failed
make: *** [pfgw64] Error 1[/CODE]



So... no cigar, but a bit closer!

lukerichards 2019-03-18 21:58

[QUOTE=Batalov;511081]On Ubuntu it is not going to be a smooth sailing. First you will need to build a static lib*.a. Second you will (suddenly) find that Ubuntu doesn't have necessary static system libs... etc etc. So you will have to build those as well from scratch, or try to get them from repo.[/QUOTE]


Do you have an alternative version of linux as a suggestion? I'm not wedded to Ubuntu.

paulunderwood 2019-03-18 22:07

[QUOTE=lukerichards;511084]Some success. Thanks so much for your time!


[CODE]
user1@ubuntu-upstairs:~/openpfgw-code-r646$ make
make -C pform/pflib
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pflib'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pflib'
make -C pform/pfmath
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfmath'
make[1]: '.libs/pfmath.a' is up to date.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfmath'
make -C pform/pfgwlib
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfgwlib'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfgwlib'
make -C pform/pfoo
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfoo'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfoo'
make -C pform/pfio
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfio'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfio'
make -C pform/pfgw
make[1]: Entering directory '/home/user1/openpfgw-code-r646/pform/pfgw'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/user1/openpfgw-code-r646/pform/pfgw'
g++ -O3 -m64 -DX86_64 -D_64BIT -I../../packages/gmp/64bit -I../../pfconfig/headers \
pform/pfgw/.libs/pfgw_main.a pform/pfio/.libs/pfio.a pform/pfoo/.libs/pfoo.a pform/pfgwlib/.libs/pfgwlib.a \
pform/pfmath/.libs/pfmath.a pform/pflib/.libs/pflib.a \
packages/gmp/64bit/libgmp.a packages/gwnum/64bit/gwnum.a -Wl,-no_pie -lpthread -lstdc++ -o pfgw64
/usr/bin/ld: cannot find -lgcc_s
/usr/bin/ld: cannot find -lgcc_s
collect2: error: ld returned 1 exit status
makefile:8: recipe for target 'pfgw64' failed
make: *** [pfgw64] Error 1[/CODE]



So... no cigar, but a bit closer![/QUOTE]

[URL="https://askubuntu.com/questions/346377/cannot-find-lgcc-s#346406"]See the part on [/URL]how to create the link with [c]ln[/c]. YMMV

Alternatively, see the solution in this [URL="https://www.mersenneforum.org/showthread.php?t=22018"]mersenneforum thread[/URL].

GP2 2019-03-21 16:10

[QUOTE=lukerichards;511086]Do you have an alternative version of linux as a suggestion? I'm not wedded to Ubuntu.[/QUOTE]

The binary executable straight from the zip file worked for me on Amazon Linux.

Amazon Linux was originally derived from Centos / Red Hat. For instance, it uses yum rather than apt-get.

So perhaps you could try Centos. But it seems like a lot of trouble to install a new distribution and then cross your fingers and hope the program will work.

wblipp 2019-04-02 16:21

The Luke Richards Hobby Project
 
[QUOTE=lukerichards;510978]having discovered last March that 3[SUP]504206[/SUP]+2 is a PRP.[/QUOTE][QUOTE=lukerichards;511836]
My aim is to factor 3[SUP]504206[/SUP]+1 and 3[SUP]504205[/SUP]+1 sufficiently [b]in my lifetime[/b] to provide a primality proof of 3[SUP]504206[/SUP]+2. As intractable a goal as that might be,[/QUOTE][QUOTE=GP2;511978]Not before the heat death of the universe..[/QUOTE]
[QUOTE=lukerichards;511980]nobody knows what will happen in the next 50 years in terms of advances in computing power and algorithm research. ... .Everyone needs a hobby![/QUOTE]

I was tickled by the idea of a 50 year hobby project and curious about whether continuing trends for 50 years might by sufficient or if algorithmic improvements would be needed to beat the heat death of the universe. I figured one path without algorithmic improvements would be to hope for larger ECM to leave large PRPs, prove the PRPs with ECPP, and make a 26% CHG proof.

Presently we know about 415 digits of factors. 26% would require over 62,500 digits of factors, so we need need over 62,000 more digits of factorization.

I looked at the ECMNET annual records, took the fifth largest factor each year, and projected out to 2069. That projection says you could find 137 digit factors by ECM in 2069.

Then I looked at ECPP records from the Primo pages and Caldwell's Prime pages. A similar projection indicates you might do 130,000 digit ECPP proofs by 2069.

Then look at the remaining composites:
C1996
C2329
C3664
C10253
C14795
C44396
C177395
C225698

The two largest ones aren't much help because even if we get a PRP residual, the PRP would still be outside of ECPP range. So we need to hope to get both the C14795 and the C44396 to factor. We would need the second largest factor of the C14795 to not exceed 137 digits. That's about [URL="http://mathworld.wolfram.com/DickmanFunction.html"]G(0.003)[/URL], which looks like less than half a percent, and the C44396 is even less likely. So 50 years without algorithmic improvements isn't likely.

On the other hand, heat death of the universe seems overly pessimistic. ECPP should be big enough to handle the whole number by 2130.

I'm not sufficiently interested, but if this were my long term hobby project I would redo the regressions using logs instead of digit counts, then forecast out five years. Check if trend lines are holding and re-forecast every five years. I would try a few other methods to see if you can beat the 2130. I would experiment with some [URL="https://primes.utm.edu/prove/prove3_3.html"]William's terms[/URL] such as n^2+n+1 and n^2-n+1 to be sure the special form of the prime didn't lead to more algebraic factorizations. When I got bored with waiting for these forecasts to mature I would think about how to forecast algorithmic improvements.

Just in case anyone cares in five years, the trend lines used in this post indicate that in 2024 we should see ECM at 80 digits and ECPP at 49K digits. Yes, I know that the record ECM is already larger than that, but we need a number people can expect to reach on a composite of their choice, not the largest luckiest factor anybody has ever found.

lukerichards 2019-04-03 15:19

This reply is beautiful, thank you. I'll digest it properly when I get home.

henryzz 2019-04-04 13:14

I would hazard a guess that ECPP may potentially improve more than predicted over that time period. Currently development of ECPP software is restricted by a mess of patents. Speed should improve as those patents expire. [url]https://en.wikipedia.org/wiki/ECC_patents[/url]

Also ECPP has never been truly exposed to distributed computing. This leads to any current records taking months on one pc to finish. If the same effort was put into ecpp as nfs factorisation then much larger numbers would be proven.

Kebbaj 2019-06-05 12:35

list 5000 ?
 
Can you publish on the list 5000 or even a topic that does not exist yet on the Top 20 the PRP 3 ^ 504206 + 2.

lukerichards 2019-06-10 08:36

[QUOTE=Kebbaj;518605]Can you publish on the list 5000 or even a topic that does not exist yet on the Top 20 the PRP 3 ^ 504206 + 2.[/QUOTE]

I'm sorry, Kebbaj, I'm not sure I understand the question.

The PRP is published on a PRP list here:

[url]http://www.primenumbers.net/prptop/prptop.php?page=3#haut[/url]

Currently ranked 542.

xilman 2019-06-10 11:28

[QUOTE=henryzz;512649]I would hazard a guess that ECPP may potentially improve more than predicted over that time period. Currently development of ECPP software is restricted by a mess of patents. Speed should improve as those patents expire. [url]https://en.wikipedia.org/wiki/ECC_patents[/url]

Also ECPP has never been truly exposed to distributed computing. This leads to any current records taking months on one pc to finish. If the same effort was put into ecpp as nfs factorisation then much larger numbers would be proven.[/QUOTE]One of them expires today.

henryzz 2019-06-10 14:11

[QUOTE=xilman;518996]One of them expires today.[/QUOTE]

And it looks like most of the ones listed on that page are either expired or nearly so. The trouble is that there are probably more that we don't know about.


All times are UTC. The time now is 05:34.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.