20211108, 17:02  #1 
"Sam"
Nov 2016
335_{10} Posts 
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))  n1, so it's important to consider other possibilities. Math::Prime::Util 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. 
20211206, 22:42  #2 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
2^{2}×1,499 Posts 
The reason k and b are kept small is that it allows much smaller and faster FFTs.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Some ideas regarding NFS...  paul0  Factoring  3  20150314 19:55 
Any ideas on v26 FFT selection algorithm?  Prime95  Software  20  20100625 23:35 
two ideas for NPLB  MiniGeek  No Prime Left Behind  16  20080301 23:32 
GROUP IDEAS  TTn  15k Search  15  20030923 16:28 
Domain name ideas...  Xyzzy  Lounge  17  20030324 16:20 