Prime Pages How to's

[paulunderwood]

Originally Posted by PawnProver44

Is 59*46^860-31 (proven) prime? I have two sources one saying it is a PRP (factordb.com) and one saying it is a prime (wolframalpha.com). I think it is prime, but two sources are saying opposite statuses.

You just need to be patient. The PRP status will be updated in time.

[paulunderwood]

Originally Posted by PawnProver44

I read the entire site, but do not explain if you can submit prime neither of Achievable forms, or greater than 388341 digits. They quickly deleted a few small primes around 1500 digits I tried to submit. I just wanted them to be in the database, not necessarily the list. That's all.

Sorry: you need to meet the size requirements or be an archivable form for that database

[PawnProver44]

Primes around 2,000 digits usually take me seconds to prove. factordb says that 38*69^1172+1 is a PRP, and I should upload a certificate when I don't need one. Will it update the prime on its own?

[danaj]

Originally Posted by PawnProver44

Is 59*46^860-31 (proven) prime? I have two sources one saying it is a PRP (factordb.com) and one saying it is a prime (wolframalpha.com). I think it is prime, but two sources are saying opposite statuses.

Opposite would be prime vs. composite. PRPs are a superset of primes, so there isn't a surprise here. But the situation isn't quite like this, because Wolfram is using different terminology. They're both reporting PRP.

Wolfram Alpha uses some variant of a BPSW test and calls the resulting probable prime "prime." The link you provided is not doing a proof. See their documentation for PrimeQ for an example of how they use the term "is a prime number" with no caveats, but then the notes in internal implementation show that this is a BPSW variant (we don't know anything about their Lucas test other than it used to be incorrect [Pinch 1993] before they added the additional base 3 test). It's a good test and if the Lucas test is correct it's an excellent test and should be good enough for almost any use. But it isn't a proof.

factordb uses PFGW to check if it is a PRP. With a single base it's definitely not as discriminating as BPSW, but two bases at this size gives a pretty good idea. PFGW is also *very* fast for large inputs (>5k digits), so it's an excellent choice for factordb. It's in the database, and various generous people regularly pull lists of PRPs to run through Primo then upload the certs. These get verified and then the status changes. It looks like the frontier is around 3k digits these days (wow). Hence PRPs less than 3k or so digits can be expected to get a certificate uploaded within a relatively short time frame without your having to do any work.

It passes my ES BPSW. It's a strong pseudoprime to all prime bases < 100. It passes the Underwood and Khashin variants of the Frobenius test. It passes yet another Frobenius variant. It's extremely unlikely to be composite.

[danaj]

Originally Posted by PawnProver44

Primes around 2,000 digits usually take me seconds to prove.

You mean this example (since it's easy with N-1), or that you can prove arbitrary 2000 digit primes? If the latter, you're saying you're getting certificates for numbers like "59*46^860-31" or "7229^518+11086" in less than 10 seconds?

factordb says that 38*69^1172+1 is a PRP, and I should upload a certificate when I don't need one. Will it update the prime on its own?

It's already done. factordb doesn't have a company funding racks of servers to support it so has to be smart with dividing its time spent. It's mostly a repository of work done by other people, and is an excellent resource. That it automates so much is pretty cool.

[PawnProver44]

Originally Posted by danaj

As far as I can tell, the OP is suggesting doing one step of Maurer's or Shawe-Taylor's method for generating random proven primes. Which is just applying Pocklington, Generalized Pocklington, BLS75 theorem 5, etc. Rather than struggle with the ambiguity of what is getting factored in his text, I'll just state this method.

For instance, using the simple BLS75 theorem 3,

1. Let P be some odd prime with a proof already available.

2. Let M be an arbitrary even number 1 < M < 4P.

3. Let N = P*M+1. Hence N-1 = P*M. Verify 2P+1 > sqrt(N). This should be true from our selection in step 2, but we should always include a verification of necessary conditions to protect from programmers or post-writers getting something off by 1.

4. Run some sort of compositeness test on N (e.g. a little trial division plus a Fermat test). If composite, go to 2.

5. Find an a such that and . Search prime 'a' from 2 to 100 for instance. If we cannot find one, then go to 2.

6. By BLS75 theorem 3, N is prime (assuming P is prime).

There are some decision points that are tunable. If the test in step 4 is stringent, e.g. BPSW, then the chance step 5 will fail approaches zero, so we should increase the number of 'a' values we examine. Alternately we could make the step 4 test cheap (e.g. divisibility or a single Fermat test) then assume some composites will go to step 5, so we shorten its search.

We could improve this with BLS theorem 5 to allow M and hence N to be much larger (which is where the 33.33% comes in, though there are linear factors as well). The basic structure is pretty similar (choose an M, get an N value, do compositeness test, find 'a' values for proof).

The same thing can be done with ECPP proofs, though more involved. In either case, we're reversing the steps to remove the difficult factoring part. But we end up with a proof of some semi-arbitrary number, which is good enough for these sorts of records and useful for selecting random primes, but of course of completely different utility than a "is N prime" question.

There are some non-trivial operations involved in this, and once N is large enough (e.g. 10k digits) step 4 starts taking appreciable time so we'd want to add some fast pre-tests or even sieving. I have no idea where arithmetic progressions come in.

M does not have to be completely factored, correct?

[VBCurtis]

Originally Posted by PawnProver44

Primes around 2,000 digits usually take me seconds to prove. factordb says that 38*69^1172+1 is a PRP, and I should upload a certificate when I don't need one. Will it update the prime on its own?

Define "prove" here. wolfram alpha does not count, danaj explained why.

[danaj]

Originally Posted by PawnProver44

M does not have to be completely factored, correct?

M doesn't have to be factored at all, though it is even hence we know it has at least the factor 2. This theorem is a special case where the large factored part is a single prime. Theorem 3 isn't very complicated but it's very handy for either Maurer's algorithm (it's similar to, but slightly better and faster than what Maurer's paper uses), or as part of an ECPP step where we might be able to reduce N a bit without too much effort.

From the paper:

Originally Posted by Brillhart, Lehmer, and Selfridge (1975), page 622-623

Theorem 3. Let N-1 = mp, where p is an odd prime such that . If there exists an a for which , but , then N is prime.

The point of the algorithm I gave is to find an 'm' and 'a' such that we meet all the conditions. Then N is prime if you believe this theorem (the paper gives a proof which one is free to examine, and the paper is widely known) and your implementation is correct.

We started with "a large prime" which I called 'p'. Since 'p' is large, it isn't 2 and hence is odd. We picked an 'm' but don't need any factors other than it being even. The result does have a big "if 'p' is prime" attached but we decided that was given to us.

Step 3 verifies that p is large enough. 'p' is representing the factored portion, so we want to make sure it is large enough. 'm' represents the unfactored portion. Theorem 3 really is simple.

Step 5 finds an 'a' that meets the conditions.