Very (large) PRPs?

[PawnProver44]

Phew. Thanks for saving me the stress about the time. I am only finding prps up to 200k digits to save even more hassel.

[axn]

Originally Posted by paulunderwood

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

Wouldn't that be 8 times as much (4x for an individual PRP test, and 2x number of PRP tests)?

[paulunderwood]

Originally Posted by axn

Wouldn't that be 8 times as much (4x for an individual PRP test, and 2x number of PRP tests)?

Yes, this is what I have experienced when searching.

[danaj]

I'm confused where this 8k digit restriction is coming from. It works fine on 140k digit numbers.

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.

It would work fine if done correctly, but it in a practical sense you're right -- at this size PFGW is so much faster at this size that you really should run it first.
]

[PawnProver44]

200k digits for n/thoery at most?

EDIT: Is it the same for Dana's perl next_prime(x) and random_ndigit_prime(x) functions?

[paulunderwood]

Originally Posted by danaj

It would work fine if done correctly, but it in a practical sense you're right -- at this size PFGW is so much faster at this size that you really should run it first.

Aha, your is_prime(n) is BPSW+another test; I was thinking in terms of is_provable_prime(n). I was confused.

I guess PawnProver44 can, in a single script file, sieve with one of your perl functions and call PFGW on surviving candidates. Is this right?

[danaj]

I guess I should try some larger numbers just to say that it's been done.

Even at 10k digits, using PFGW is faster, but not overwhelmingly so. Once you get much larger, I think using PFGW for an initial test, followed by Paul's standalone F-U program would give a very good combination. Paul's program uses gwnum, same as PFGW, takes about 3x longer to run, but a much more stringent test so good to use to confirm PFGW's result. It's still a PRP, but passing two Fermat tests and a Lucas test is good.

There has been a bit of confusion on the nextprime issue. PFGW has the (AFAIK) fastest available PRP test (albeit just a Fermat test). It also includes an expression evaluator that includes a nextprime command that happens to be very slow. I suspect it was intended for simple things like 'nextprime(50)#+59' where it works great, rather than for huge inputs.

[PawnProver44]

So then I can use the text file link like you sugessted earlier, then use the sieve command not listed in the module description, then prp test remaining candidates, then after that preform Paul's BPSW test and verify to make sure it is a Fermat and Lucus PRP? Perfect!

[PawnProver44]

Originally Posted by axn

Wouldn't that be 8 times as much (4x for an individual PRP test, and 2x number of PRP tests)?

Ok, I'll just record the time for a 391 digit prime using pfgw's nextprime(x) and then double each candidate 9 times to get to 200192 digits (close to my aim of 200k digits).

[danaj]

Originally Posted by paulunderwood

Aha, your is_prime(n) is BPSW+another test; I was thinking in terms of is_provable_prime(n). I was confused.

Ah, that makes sense. Yes, my is_provable_prime is good for maybe 2k digits (and honestly you need one of the extended poly sets to run well past 500 digits). Primo is better once past 1k. Practically good to maybe 15k, works fine to ~35k if you have the time and resources.

I guess PrawnProver44 can, in a single script file, sieve with one of your perl functions and call PFGW on surviving candidates. Is this right?

Yes. You could do the same with cnewpgen I believe, and I'm sure others have sieves that work well. I wrote a slightly nicer script in the 500k+ prime gaps thread, and tested it on Windows. It is appropriate for simple expressions -- using huge random inputs would need something different.

[danaj]

Originally Posted by PawnProver44

So then I can use the text file link like you sugessted earlier, then use the sieve command not listed in the module description, then prp test remaining candidates, then after that preform Paul's BPSW test and verify to make sure it is a Fermat and Lucus PRP? Perfect!

Yes, that should be the most efficient method.

1. Sieve a range using whatever appropriate tool to get just the candidates without small factors.
   
2. Run PFGW on those candidates. This just runs its Fermat test with the default base. When one passes, congrats, you have your PRP.
   
3. (Optional) A Fermat test is one of the weaker tests, so we might want to do a little better.
   • We could run PFGW with a few different bases. I believe this is what factordb does.
   • We could run Paul's program that does his Frobenius-Underwood test, which is an efficient and pretty stringent test. If you go through the math, it essentially runs a Fermat and Lucas test at the same time with a good base selection process. I believe this is better than running a few more Fermat bases. Since this uses gwnum it's quite fast for large numbers.
   • We could run BPSW. Sadly there is no gwnum implementation, so it will be much slower at the sizes we're talking about. Since we only run one, the speed isn't as critical. You could run various Frobenius tests as well, but I think a Fermat plus BPSW would be convincing enough: people who accept PRPs would think this is enough, while people that want proofs aren't going to be more convinced by further PRP testing.