2021-11-08, 17:02 | #1 |
"Sam"
Nov 2016
2^{3}×41 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)) | n-1, 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. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Some ideas regarding NFS... | paul0 | Factoring | 3 | 2015-03-14 19:55 |
Any ideas on v26 FFT selection algorithm? | Prime95 | Software | 20 | 2010-06-25 23:35 |
two ideas for NPLB | Mini-Geek | No Prime Left Behind | 16 | 2008-03-01 23:32 |
GROUP IDEAS | TTn | 15k Search | 15 | 2003-09-23 16:28 |
Domain name ideas... | Xyzzy | Lounge | 17 | 2003-03-24 16:20 |