The "one billion minus 999,994,000" digits prime number

[science_man_88]

Originally Posted by a1call

Thank you for your reply.
Your method is faster than mine which basically is a very short routine which takes in 2 relatively small variables (<100 in this case) that I have to try inputting manually due to free account limitation (no random function is used). A thereon such as theorem 1 is of value for finding primes even when it does not converge to less than the square .

product of prime -product of primes using all primes less than in only one place will be prime up to as I already told you based on it having no factor to divide out ( which you came to)

[a1call]

Regarding the simplified example on my reply 77, the double factorial must be of an odd number so for the sake of correctness:

p=(2x-1)!!-2^y , p<(2x-1)^2
For integers x and y.

[science_man_88]

Originally Posted by a1call

Regarding the simplified example on my reply 77, the double factorial must be of an odd number so for the sake of correctness:

p=(2x-1)!!-2^y , p<(2x-1)^2
For integers x and y.

it's less than (nextprime(2x-1))^2 example find the numbers that are between 9 and 25 and don't divide by 2 3 answer 11,13, 17,19,23 because 10,12,14,16,18,20,22,and 24 all divide by 2 which our product sum does not, 15,and 21 both divide by 3 which our product sum can not.

[danaj]

Originally Posted by a1call

Your method is faster than mine [...]

Maybe -- it's hard to compare directly, as my code is in Perl calling GMP functions, while yours is in some Mathematica system. I'm sure the performance characteristics are very different. But it does give some idea of the time for existing methods that generate random proven primes.

A thereon such as theorem 1 is of value for finding primes even when it does not converge to less than the square since it can be used to construct routines which yield primes with astronomically higher probability than random trials. For example odd numbers are twice as likely to be primes than integers in general. Factor out divisible by 3s and you improve your odds substantially more.

Checking for small factors is quite fast however. The main problem is typically that one is consuming randomness. This may be a non-issue (if we don't care about crypto or are using a very fast CSPRNG with high-delay reseeding), but it can be huge if we want good entropy on embedded or isolated devices without entropy hardware.

I recommend reading the paper: "Close to Uniform Prime Number Generation With Fewer Random Bits" by Pierre-Alain Fouque and Mehdi Tibouchi, 2011. It gives a good overview of some earlier methods, then shows their technique. It is targeted to a different situation than your goal, but I think it gives a good understanding of current methods for random prime generation. They also point out how one can easily skip results with small divisors. My modified A1 algorithm of course doesn't generate evens, and skips anything with factors 3-19 with simple native integer calculations -- so constructing the large integer is only done when we know the result has no tiny factors.

Maurer's method will double or triple the number of bits at each step. Doubling is pretty common, using Pocklington or BLS theorem 3. Tripling is possible using BLS theorem 5 or similar. BLS75 theorem 3 says:

Let N-1 = mp, where p is an odd prime such that 2p + 1 > sqrt(N). If there exists an a for which a^((N-1)/2) = -1 mod N, but a^(m/2) != -1 mod N, then N is prime.

So we work backwards, starting with a small prime p verified with some deterministic method (e.g. trial division, deterministic M-R, or BPSW). Then select a random m of size such that the 2p+1> sqrt(N) holds, and N isn't obviously composite (simple divisibility checks). At this point I think it's best to do a strong pseudoprime test on N -- one modular power will verify whether we should proceed. At the sizes we're looking at, if it succeeds then we almost certainly pass the next step. Search for an a that works with the final two conditions, trying just a few values (e.g. 3 to 5) -- if we found one, then N is prime, otherwise go back to selecting a different random m. It should be clear how we can do this repeatedly to build up N to our desired size.

Shawe-Taylor does a similar process. My code does the pedantic implementation from FIPS 186-4, which defines very specific methods for using SHA256 to generate a pseudo-random stream from the seed and how to construct the candidates. It also defines the method for searching for a values and uses the Pocklington test.

One thing I did with my implementation of both was add a BPSW test before returning N. With a correct implementation this is a waste of time, but I've seen a different implementation goof up one of the conditions and return composites in very rare cases. The extra BPSW test is just there to catch anything like that (I'd much rather than the code assert than return a composite, and I'm willing to spend a tiny bit of extra time on it). For a billion digits you wouldn't want that :). There are other modifications one could make to speed things up for generating a large prime quickly vs. a random prime. Maurer's method, for instance, doesn't always use the largest m possible, as it is trying to take into account the factor distribution of uniformly random N-1 values, hence often chooses something smaller.

The main problem is that as the size grows, we spend more and more time selecting random m values that don't result in N being prime. This could be sped up some, e.g. (I haven't implemented it) we could sieve N-1=(m+j)p for some range of j, which would be faster than choosing random m and checking each one for divisibility.

My Thereon 1 and to a greater degree Theorem 2 (undisclosed so far) has a much more probable solution. Obviously my mathematical skills have not sufficed to find a solution yet. But I am convinced that such a solution is feasible given proper mathematical skills (much better than mine).

Definitely keep working on it. I do think it's good to get at least some idea of previous work in the field. Even if it doesn't result in a billion digit prime, another method for random proven primes sounds interesting.

[a1call]

Thank you danaj for your expert and kind opinion. I will look into your recommended reads but doubt very much that my mathematical background is advanced enough to get understand/get much out of it.

Now for my new hobby of finding primes this is the largest so far.

A 2947 digit prime:

1805466980889895444152083705580546438904586504024677600165535188575543429685794077960505989625214808524915116303899705491315603164094343044084813795581043757530995487552235487902523723086567740452893727595719880372980597935541450742314924709084464477805706347801215564892828477742072237573906563782370272100579388686003721262122865977590597671663276817313957626949815633164020079618129756124758514473258952668713086668728327275687891046096802123432511845769670152445319814829069235728684165231695321332342334367088705269590536527660092629353864957805226857372134492239182271773319271671060039879398708305623924423944843161074165034154548690879881017033937390305637610815820841838308524829591690956013832210832989143539340531227350566275290758441812554637924971005663040725834078658718911848208299986651450324251660389891917952141142210279447598049220945655658626052995732959245011919822884830765020739809511578315007267171708637682291056185797473317747764366344004828507106666721146537504910198413255887344019105030885272695106644022148170279957406811811911585778607600739191941607919630180234280031608973517046509793449110316428492468696779825270101530626635344218034017307575001966882491611934891738871974963517180137793058469000240528839225740256912452059160288057505444198500439633240583962147605681672854210974037353231750759224515933944959499070415928622085379698744189526577111698223307107665376762465818342167706880502158694017253486016700231248897694374400855441474197730980037468658876592266138720858442852935844690619167220560914289672460090283731271531544337770738859857007393568030507020182480999526498540545600903227122621230800437089885978984230703506985324720816164021613478285374762602855643139663257847197959455588902981428173235460646940557633065072026465549146471366173033516852539147433182479114301404886920957104251678805504412494200796533347564550660712562917738939205873028504412308575509495761954814647711657139410849691685321052885903832951506346892246167734326681830599628039736287055861356443181022534485795392105080607228795912012553024445415098038410720044479890661532850673130219375779899531376107672518236277402316679487610396175030330672991287042582145245368628067527664022783999883065155230024645864740144778843763548011487620955941889185683824851653206897896900747451378467342402311606349922692725297663302384680026620955340896805371466046084505923777439953896738500215013385523653896095796144761307282761834587963060324115970111770272476498848789114830467810498345867446037192452020756530749047624747739018468419463872849159279940652772445668411860820516407239704696025418086495779571719406376523548257847350367035686315656048518163977035026758194250214340115912569626831728654997932815440375880817644385932476040941555231541267305721707269170287184587787567356129062681652484241589553874347773466273391056360920384479015168760367513723387661000831706805133731080182032638806917395759284450399866107468081950321

Is there a number of digits below a million that I can come up with that would qualify moving this thread out of the Crackpot section?

[axn]

Originally Posted by a1call

Is there a number of digits below a million that I can come up with that would qualify moving this thread out of the Crackpot section?

You can start by finding a Top 5000 prime. Currently the entry criteria is 388341 digits (http://primes.utm.edu/primes/status.php).

[Batalov]

Yep, that will work.

[axn]

Originally Posted by axn

You can start by finding a Top 5000 prime. Currently the entry criteria is 388341 digits (http://primes.utm.edu/primes/status.php).

Originally Posted by Batalov

Yep, that will work.

A more aesthetically pleasing target is to beat GIMPS's 1st (http://primes.utm.edu/primes/page.php?id=5), which, at 420921 digits is a mere 10% bigger. This was the #1 prime in 1996, and is very much dear and near to this forum

[a1call]

Thank you for the reply axn.
The 1073 digit was checked in 18 minutes on a windows 10 desktop with this tool:

http://www.alpertron.com.ar/ECM.HTM

The 2947 digit is still running at more than 15 hours. A few more digits make a big difference and prove the above tool not appropriate for large primes.

Fortunately the Wolfram server can confirm both in seconds.

[R.D. Silverman]

Originally Posted by a1call

Thank you for the reply axn.
The 1073 digit was checked in 18 minutes on a windows 10 desktop with this tool:

http://www.alpertron.com.ar/ECM.HTM

The 2947 digit is still running at more than 15 hours. A few more digits make a big difference and prove the above tool not appropriate for large primes.

Fortunately the Wolfram server can confirm both in seconds.

??? Are you sure that the Wolfram server is yielding PROOF?

[danaj]

At 2947 digits, you'll probably want to use Primo (which means a Linux machine or VM). Pari's isprime will work as well, but Primo is probably noticeably faster and gives a progress indication. Pari/GP took 4.5 minutes on your 1073 digit number on my laptop. Using BPSW on the 2947 digit number takes under a second using Pari/GP or Perl/ntheory.

Wolfram uses a BPSW variant for PrimeQ, not a proof. You'd have to use ProvablePrimeQ for a proof. Wolfram Alpha doesn't support that command so I'm not sure if your tool does or not. It returns what it claims is an ECPP certificate that its checker can parse.