mersenneforum.org Some T5K prime ideas
 Register FAQ Search Today's Posts Mark Forums Read

 2021-11-08, 17:02 #1 carpetpool     "Sam" Nov 2016 22×83 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.
 2021-12-06, 22:42 #2 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 25·11·17 Posts The reason k and b are kept small is that it allows much smaller and faster FFTs.

 Similar Threads Thread Thread Starter Forum Replies Last Post paul0 Factoring 3 2015-03-14 19:55 Prime95 Software 20 2010-06-25 23:35 Mini-Geek No Prime Left Behind 16 2008-03-01 23:32 TTn 15k Search 15 2003-09-23 16:28 Xyzzy Lounge 17 2003-03-24 16:20

All times are UTC. The time now is 21:36.

Thu May 19 21:36:23 UTC 2022 up 35 days, 19:37, 1 user, load averages: 1.72, 1.66, 1.61