mersenneforum.org (https://www.mersenneforum.org/index.php)
-   carpetpool (https://www.mersenneforum.org/forumdisplay.php?f=145)
-   -   Some T5K prime ideas (https://www.mersenneforum.org/showthread.php?t=27304)

 carpetpool 2021-11-08 17:02

Some T5K prime ideas

So most primes on the T5K list as you all might know are primes of the form k*b^n+-1 where k and b are rather small.

While I haven't searched for many primes in a long time, I thought of trying to do something different.

Generating a large random number and getting the smallest prime larger than it (nextprime) is likely to result in a probable prime, not a proven prime number.

My idea is to do the next best thing:

Given some random provable prime p (provable by any means, ECPP, N+-1, etc.), we can generate a new larger prime n = k*p + 1, where k is randomly chosen between 1 and R, where R < p^2. Basically, we can repeat this process over and over again until we get a prime of desired size.

Then again, this also works for arbitrary integers p (not necessarily primes), as long as we can fully factorize p.

To add some randomness to the sequence of primes involved, we can select a different bound for R every time (i.e. the first iteration will have R = n^2, the next will have R = 1000000, etc.).
In addition, we can also construct multiple primes at once (q, q2, q3, qk)… then multiply them all together p = q*q2*q3*...*qk, so that p isn't necessarily prime every iteration.

Again, both of these techniques allow for more variety of different primes that may not be constructible if p is always prime and we use the bound R = n^2 every time).
This is because not every prime n may have some prime p ≈ O(n^(1/3)) | n-1, so it's important to consider other possibilities.

[URL="https://metacpan.org/pod/Math::Prime::Util#random_proven_prime"]Math::Prime::Util[/URL] seems to have some pretty good implementations of an algorithm similar to this one, although it seems not all primes are possible to construct via this method.

Using PFGW for large numbers (especially mega numbers), is going to be a huge drawback (LLR is much faster, but it won't work here!). Sieving is also going to be interesting. While I've developed some programs to sieve for such primes, they are nowhere near as fast as programs like psieve or srsieve.

I'll keep updated and may post some examples later if anyone's interested. Can't wait to see how this turns out, and if I can find a T5K prime using this method.

 henryzz 2021-12-06 22:42

The reason k and b are kept small is that it allows much smaller and faster FFTs.

 All times are UTC. The time now is 09:45.