Go Back > Extra Stuff > Blogorrhea > carpetpool

Thread Tools
Old 2021-11-08, 17:02   #1
carpetpool's Avatar
Nov 2016

23×41 Posts
Post 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.
carpetpool is offline   Reply With Quote

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

All times are UTC. The time now is 11:14.

Sat Nov 27 11:14:51 UTC 2021 up 127 days, 5:43, 0 users, load averages: 1.60, 1.26, 1.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.