Very (large) PRPs?

[PawnProver44]

2.16 Gz processor is not that bad. Took 9.768 s. to find this prime, using the same methods I can use for larger PRPs. Now double each prp's digits 7 times, (4x times as much for doubled candidates) is about 1 day, 20 h. 27 min. Seems right?

[danaj]

Joining the party for this random and otherwise uninteresting PRP:

time perl -Mntheory=:all -nE 'chomp; say length($_); say is_bpsw_prime($_); say is_frobenius_pseudoprime($_); say is_frobenius_khashin_pseudoprime($_); say is_frobenius_underwood_pseudoprime($_);' ~/Downloads/prp_6056.txt 
6056
1
1
1
1

real	0m30.460s
user	0m30.425s
sys	0m0.012s

So it passes BPSW (strong pseudoprime base 2 + extra strong Lucas), a Frobenius test, Khashin's Frobenius-type test, and Underwood's Frobenius-type test. The F-U test here uses GMP and takes less than 6 seconds. At 200k these should work fine, but Paul's gwnum version will be quite a bit faster.

On my machine (X5550 2.67GHz), PFGW took 4x longer for a 2x larger input. ~95s at 50k digits, ~390s at 100k digits. No AVX.

The time in the paragraph above is purely the time taken for a given composite candidate, and does not take into account how the expected number of tests until a PRP is found will go up as the size goes up.

[paulunderwood]

But does it have AVX? If you are running Linux on it you can type cat /proc/cpuinfo to see. Under windows you have go clickety click somewhere

[paulunderwood]

Originally Posted by PawnProver44

2.16 Gz processor is not that bad. Took 9.768 s. to find .... using the same methods I can use for larger PRPs. Now double each prp's digits 7 times, (4x times as much for doubled candidates) is about 1 day, 20 h. 27 min. Seems right?

No! The primes will thin out as they get bigger. You need to multiply by 8 and extrapolating from 10 seconds is useless.

[PawnProver44]

Command Window (thanks for command, is availible for up to 200k digits?):

---------
C:\Users\Username\Documents> time perl -Mntheory=:all -nE 'chomp; say length($_); say is_bpsw_prime($_); say is_frobenius_pseudoprime($_); say is_frobenius_khashin_pseudoprime($_); say is_frobenius_underwood_pseudoprime($_);' ~/Downloads/prp_6056.txt
The system cannot accept the time entered.
Enter the new time: 440
The system cannot accept the time entered.
Enter the new time: 16666
The system cannot accept the time entered.
Enter the new time: ?
---------

Just sticking to the sieve if that doesn't work.

[paulunderwood]

time is a Linux command to measure timing.

Under windows it is used for setting the time!!

[PawnProver44]

Sorry for all delay. I was too busy during this week and I haven't got a chance to download linux version of pfgw, pari/gp and more programs like primo and newpgen...

[Xyzzy]

Originally Posted by danaj

It seems to try to open a file named 46, so I couldn't run it, but now I see it just writes one line at a time.

If you are bored and want to see the "program" in action, you can get a copy of that file here: http://www.mersenneforum.org/showthread.php?t=21252

Since there are 49 (so far) files to choose from, we probably should use a command line argument for the file name instead of hard coding it.

[danaj]

For Windows you need to take into account how even today the DOS command shell is basically 1970's CP/M.

C:\>perl -Mntheory=:all -nE "chomp; say length($_); say is_bpsw_prime($_); say is_frobenius_pseudoprime($_); say is_frobenius_khashin_pseudoprime($_); say is_frobenius_underwood_pseudoprime($_);" prp_6056.txt

You have to write your own little .bat script for timing if you want (use your favorite search engine).

It should work on 200k inputs. I just ran it on a Windows laptop with the 50k digit PRP "10^49999 + 91701". It isn't fast -- ~2 hours for all four tests.

Re Xyzzy's file, I was seeing those odd-looking forms on the PRPtop site when I tried the number above. Now I know where they came from!

[PawnProver44]

So here is what I will actually do:

1. Use Paul's pari/gp script for sieve and random number gen. + PFGW's prp test for all remaining candidates

2. Use Dana's perl/netheory script to preform stronger tests.

3. From calculations of 8x as much time for 2x the digits, would take 5.3333 days for my current aim.

4. I am thinking about seeing weather Dana's perl script hold 300k digits, 400k digits, etc. so I know what limits are placed.

5. Or use Xyzzy's Script (for sieving)

6. Laziest, but less efficient is pfgw's nextprime.

If I get pfgw, pari/gp, etc...... set up by tomorrow, I will probably have 200k digit prp to show you soon.

[Xyzzy]

Do you have access to a Linux machine?

If not, there are many free possibilities.