Very (large) PRPs?

[danaj]

PFGW's nextprime is not at all optimal (with 3.7.10 at least). It does a shallow small factor check followed by WraithX's GMP BPSW test. It's significantly slower than Pari or Perl/ntheory, when for large inputs (4000+ digits) it could be much faster if it did a sieve followed by its PRP tests, with the BPSW test reserved for anything passing the PRP test.

Of course for the trivial sizes you're showing (sub-40 digits) you're measuring completely wrong. next_prime for 40 digit inputs should be taking less than a millisecond.

For next prime of 10^2000:

22s Perl/ntheory
128s Pari/GP 2.8.0 (55e7256a)
231s PFGW 3.7.10.64bit

Once you get into the 2k-10k range and larger, the fastest strategy I know is to use a sieve (Perl/ntheory or newpgen or whatever) followed by PFGW on each candidate (so it runs the fast PRP test), followed by a better test on the result (Pari/GP, Perl/ntheory, etc.). There isn't any really convenient one-stop solution right now.

There's another thread that was discussing this, and if I had a good gwnum standalone base-2 M-R test I could easily add it to my code. A standalone Fermat would work also -- the one in PFGW exists but doesn't look easy to take out.

[PawnProver44]

I do not think any of those programs can handle nextprime(x) for x around 200k digits, and I think no text editor would support at least 500k lines of next, but if any please let me know of a few editors I can use for something like this:

nextprime(input.txt); (random 200k digit number)

Result = inputprime.out (decimal expansion of nextprime(x))

[danaj]

It depends what you mean by "cannot handle." All three tools ought to work. I've used mine for 100k inputs before, but the time taken can be extreme. I don't see why Pari/GP would have any issues with large inputs other than the time taken.

vim and emacs will both handle 500k character lines without a problem. Older versions of vi work but get slow for such long lines. You can also just generate 500k random digits with a program and have it output to your file.

You could also just do something like:

perl -Mntheory=:all -E 'prime_set_config(use_primeinc=>1); say random_ndigit_prime(1000);'

which will do basically what you're suggesting. It turns on the fast-but-bad-distribution PRIMEINC method for random primes, then asks for a random prime of however many digits. Which means it chooses a random number of that many digits, then runs next_prime on it. But at 100k digits, gwnum is *much* faster than GMP, so doing things the long way around is going to save a lot of time.

I would think that doing next_prime of simple expressions would be more palatable than completely random PRPs. It sounds like there are already issues with submitting giant numbers like these. Wouldn't next_prime(10^100000+10^12345) or something be different enough and yet still easily describable?

[a1call]

Originally Posted by danaj

I would think that doing next_prime of simple expressions would be more palatable than completely random PRPs. It sounds like there are already issues with submitting giant numbers like these. Wouldn't next_prime(10^100000+10^12345) or something be different enough and yet still easily describable?

That's a good point. There are limitations to web "form submission" by design. The best that can be done to submit a large decimal expansion with a form is to use loss-less compressed files. However there is always other means of file transfer other than form submission (which is not really designed for the purpose). FTP link in an email should work (at least in theory).

[PawnProver44]

Originally Posted by danaj

Once you get into the 2k-10k range and larger, the fastest strategy I know is to use a sieve (Perl/ntheory or newpgen or whatever) followed by PFGW on each candidate (so it runs the fast PRP test), followed by a better test on the result (Pari/GP, Perl/ntheory, etc.). There isn't any really convenient one-stop solution right now.

There's another thread that was discussing this, and if I had a good gwnum standalone base-2 M-R test I could easily add it to my code. A standalone Fermat would work also -- the one in PFGW exists but doesn't look easy to take out.

Is there some program I can use to generate large random numbers (500k+digits), then input them in wordpad for text editing and input into pfgw: -f -i input.txt, but how can I do this using Pari/Gp or ntheory to do that? For pfgw using a 2.16 Gz processor, I get timing greater than a decade for: nextprime(200k digit number) which is "extreme".

The problem with prp testing each candidate is the command line will freeze due to several lines of digits. Ntheory should not take more than two weeks for this using the same processor is my guess? Thanks. Seems complicated to me.

[danaj]

Pari/GP easily generates large random numbers. E.g.

echo 'random(10^1000)' | gp -f -q > /tmp/input.txt

There are plenty of other ways. I have a suspicion your next point will be what to do with the number you get (sieving or PFGW). At some point you really need to learn to read the man pages and figure out how to run things yourself.

[paulunderwood]

Something like the following might work:

 c=0;for(k=1,10000,n=random(10^500000);forprime(p=2,1000000,if(n%p==0,break(2)));c=c+1;write("pf500000.txt",n));print(c" numbers added")

Bear in mind that the file might be large, if you up the "k"!

[PawnProver44]

Set nextprime(2^620000) in pfgw a month ago and it is still working on it . For perl n/theory, I still get over a month (unless I am extremely lucky) using the same processor.

I am currently unsure if Pari/GP or perl/ntheory do sieves before prp testing remaining candidates for next_prime(n).

[paulunderwood]

This is better code for random primes. (The previous code I gave only produce one candidate )

 c=0;for(k=1,100,n=random(10^500000);factored=0;forprime(p=2,1000000,if(n%p==0,factored=1;break));if(factored==0,c=c+1;write("pf500000.txt",n)));print(c" numbers added")
5 numbers added

If you go down this line, use PFGW's "-f" switch.

[PawnProver44]

Originally Posted by paulunderwood

This is better code for random primes. (The previous code I gave only produce one candidate )

 c=0;for(k=1,100,n=random(10^500000);factored=0;forprime(p=2,1000000,if(n%p==0,factored=1;break));if(factored==0,c=c+1;write("pf500000.txt",n)));print(c" numbers added")
5 numbers added

for perl/ntheory my guess? That code just restarted my computer for some reason?

[paulunderwood]

Originally Posted by PawnProver44

for perl/ntheory my guess? That code just restarted my computer for some reason?

I don't why that pari/gp should do that. Heat? Lack of memory? Watch out for the file size of "pf500000.txt"!