Very (large) PRPs?

[PawnProver44]

I was actually lucky that I got a 1/28676 chance for being prime and only nextprime(x)-x was 2652 for the number I picked. (Could have been worse) or even a 1/120000 chance, so I picked a good range for pfgw's calculations.

[paulunderwood]

Originally Posted by PawnProver44

I was actually lucky that I got a 1/28676 chance for being prime and only nextprime(x)-x was 2652 for the number I picked. (Could have been worse) or even a 1/120000 chance, so I picked a good range for pfgw's calculations.

I ran my pari script with 10000 random(10^12000) numbers which produced ~450 candidates, fed those into PFGW and had a PRP within 14 minutes, whereas yours took a "few weeks" and were "actually lucky"!

[PawnProver44]

I generated 1000 random 1000 digit numbers, manually used pfgw, and found 2 PRPs. (Which I will eventually prove with Primo.)

[paulunderwood]

Originally Posted by paulunderwood

I ran my pari script with 10000 random(10^12000) numbers which produced ~450 candidates, fed those into PFGW and had a PRP within 14 minutes, whereas yours took a "few weeks" and were "actually lucky"!

Checking the log, I actually found 2 ~12000 digit PRPs

[PawnProver44]

Thanks for helping me bring up another point:

My pfgw.out file is too large (I cannot open it with notepad at least), can I create a second file or delete some output?

[danaj]

Originally Posted by paulunderwood

I am not sure how efficient nextprime() is at 500k digits. Anyone?

Pari's nextprime isn't the best choice even at 2000 digits. Perl's ntheory module using GMP is much better. Somewhere between 2000 and 4000 digits gwnum starts being faster than GMP, so it doesn't take long before using PFGW is a big time savings. At 500k digits doing a simple sieve+PFGW is probably a couple orders of magnitude faster.

Sieving and the compositeness test are both important. Perl/ntheory does deep sieving, while the other tools do not. Paul's script isn't the most efficient, but it's a hell of a lot better than not doing it, and it's simple and concise. For the compositeness tests, GMP is great under 1k digits, gwnum can be much faster with big inputs. In 2013 I did some tests on a 140k digit PRP and PFGW's Fermat was 5x faster than GMP M-R (from Perl/ntheory, essentially identical to WraithX's M-R code), and 11x faster than Pari/GP's M-R.

At 8000 digits, Perl/ntheory is about 4x faster than Pari/GP. I suspect most of this is the sieving.


Timing for 10^8000 on an i6700:

58 min 3s PFGW's nextprime
17min 53.5s Pari/GP
4min 29.5s Perl/ntheory
41.7s the script below using Perl/ntheory for sieve and calls to PFGW's PRP test for each candidate

perl -Mntheory=:all -E 'use Math::GMP qw/:constant/; $n=10**8000; @f=Math::Prime::Util::GMP::sieve_primes($n+1,$n+500000,5e8); for (@f) { $i=$_-$n; last if !system("./pfgw64s -k -Cquiet -f0 -u0 -q\"10^8000+$i\"") && is_bpsw_prime($n+$i); }'

Note that script is really crude -- you'd want to change the width and depth appropriately for your value or better yet, make it automatic. It ought to print something nice for PRP and not nice if your width was too short. It could quiet PFGW completely if desired. Using system calls for each candidate is inefficient. On the bright side, it is a fairly small one-command-line solution that is faster than the other tools.

Plugging in 10^12000 I got a PRP (including the BPSW test) in 75 seconds.


I'll point out again the advantages of starting with some expression rather than 500k random digits. Even if you get it to work, you get a big PRP that you can't submit anywhere because it's 500k random digits. Why not 10^500000 or some other succinctly written number? You also won't have shell input problems -- I'm almost sure this is what's going on with your big input for Perl: the DOS shell is barfing on a giant line. It's possible it is Perl itself -- there are lots of ways around this, but this forum seems like a bad place for elementary how-to-use-a-computer threads.

Something things really messed up if it took more than more than a couple hours for nextprime on a 12k digit input that isn't in a large merit gap. Even PFGW's slow nextprime shouldn't be *that* bad.

[PawnProver44]

Using PrimeInc:

Average times for random 1000, 2000, 3000, 4000, 8000, 16000 digit numbers:

1000 digits: 7.8s
2000 digits: 15.9s
3000 digits: 5.0s (25.8s)
4000 digits: 5.9s (50.8s)
5000 digits: 4 min. 51s (2 min. 20s)
6000 digits: 7 min. 22s

I know the time for 3000 and 4000 digits is less extreme for average timing, but my guess for that is I had picked integers close to a prime number. (I'll redo those ones). The 5000 digits is more extreme timing.

[PawnProver44]

I read on another forum when someone told me that I could open a .txt file with Perl functions in the command window (for perl/ntheory). I am basically putting in the commands I would normally use in the command window, except having perl read the .txt file with the commands, then process it:

C:\Users\Username\Documents>perl C:\Users\Username\Documents\Perl Scripts\input.txt

(Nothing)

C:\Users\Username\Documents>

Here is what was in the .txt file:

perl -Mntheory=:all -E "say is_prime('100288370102196085733993')"

With the command window:

C:\Users\Username\Documents> perl -Mntheory=:all -E "say is_prime('100288370102196085733993')"
1

And again does not work after reading it in a Perl Guide for Dummies, so I am doing my last and final solution to see if anyone here knows it.

EDIT: Reason I need to do this in a .txt file is to input all of the digits for a random 500k digit number or more, and output the file back to me with the result.

[paulunderwood]

You are trying to run a command line program from within a file

You need to structure your program file similarly to this

However, running Dana's perl is_prime() on a random 500k digit number will not work. You will have to call out to PFGW instead.

[PawnProver44]

Okay, thanks for that warning. (I believe perl/ntheory handles about 8,000 digits at most? I'll preform more tasks and report the final limit myself.) I'm assuming it's the same with next_prime(x) and random_ndigit_prime(x) too. I know how to use pfgw for nextprime(x), though I was nearly afraid that the number of digits doubled in x would take 16 times as long to compute, or is that only for ECPP proof?

[paulunderwood]

Originally Posted by PawnProver44

... though I was nearly afraid that the number of digits doubled in x would take 16 times as long to compute, or is that only for ECPP proof?

PFGW will take 4 times as long for a doubling in length of the number, remembering that the primes are sparser for bigger numbers.