20160313, 06:26  #1 
"NOT A TROLL"
Mar 2016
California
197 Posts 
Prime Pages How to's
I have seen most primes on the Top 5000 are of the form k*2^n+1, however I want to find an "ordinary" prime. I came up with the idea of picking already large known primes and multiplying them together with another random number. I can run Pfgw so I can use arithmetic progressions (k) to find this prime. The only problem is when I submit this prime, how do I let the editors and others know I factored this number to 33.33%. Is there anwhere I should list the known factors in order to prove the number prime. Please let me know. Thanks.

20160313, 07:06  #2 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
10011110001001_{2} Posts 
Please explain what you mean by "I factored this number to 33.33%"

20160313, 07:19  #3 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
It means that log(known factors)/log(number) > 1/3

20160313, 09:49  #4  
"Nathan"
Jul 2008
Maryland, USA
2133_{8} Posts 
Quote:
Quote:
Quote:
What prime? Quote:
Quote:
Last fiddled with by NBtarheel_33 on 20160313 at 10:04 

20160313, 10:24  #5 
Jun 2003
2^{2}×3×433 Posts 
I don't know what actually OP means. But the basic idea is that you'll take a bunch of known primes and compute N=k*P1*P2..Pn+/1. By construction, we know the factorization of N1 (or N+1). If N is a PRP, we should be able to prove it relatively easily.
I don't where arithmetic progressions fit in this scheme. 
20160313, 12:34  #6  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
4270_{10} Posts 
Quote:
Still, OP seems to be basing his work on factorization, so what you wrote can (partially) apply. Last fiddled with by MiniGeek on 20160313 at 12:35 

20160313, 18:46  #7  
"NOT A TROLL"
Mar 2016
California
197 Posts 
Quote:
Last fiddled with by wblipp on 20160316 at 17:46 Reason: fix quote box 

20160313, 19:52  #8  
Sep 2002
Database er0rr
5·787 Posts 
Quote:
Last fiddled with by paulunderwood on 20160313 at 19:55 

20160313, 21:21  #9 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}×101 Posts 
As far as I can tell, the OP is suggesting doing one step of Maurer's or ShaweTaylor's method for generating random proven primes. Which is just applying Pocklington, Generalized Pocklington, BLS75 theorem 5, etc. Rather than struggle with the ambiguity of what is getting factored in his text, I'll just state this method.
For instance, using the simple BLS75 theorem 3, 1. Let P be some odd prime with a proof already available. 2. Let M be an arbitrary even number 1 < M < 4P. 3. Let N = P*M+1. Hence N1 = P*M. Verify 2P+1 > sqrt(N). This should be true from our selection in step 2, but we should always include a verification of necessary conditions to protect from programmers or postwriters getting something off by 1. 4. Run some sort of compositeness test on N (e.g. a little trial division plus a Fermat test). If composite, go to 2. 5. Find an a such that and . Search prime 'a' from 2 to 100 for instance. If we cannot find one, then go to 2. 6. By BLS75 theorem 3, N is prime (assuming P is prime). There are some decision points that are tunable. If the test in step 4 is stringent, e.g. BPSW, then the chance step 5 will fail approaches zero, so we should increase the number of 'a' values we examine. Alternately we could make the step 4 test cheap (e.g. divisibility or a single Fermat test) then assume some composites will go to step 5, so we shorten its search. We could improve this with BLS theorem 5 to allow M and hence N to be much larger (which is where the 33.33% comes in, though there are linear factors as well). The basic structure is pretty similar (choose an M, get an N value, do compositeness test, find 'a' values for proof). The same thing can be done with ECPP proofs, though more involved. In either case, we're reversing the steps to remove the difficult factoring part. But we end up with a proof of some semiarbitrary number, which is good enough for these sorts of records and useful for selecting random primes, but of course of completely different utility than a "is N prime" question. There are some nontrivial operations involved in this, and once N is large enough (e.g. 10k digits) step 4 starts taking appreciable time so we'd want to add some fast pretests or even sieving. I have no idea where arithmetic progressions come in. Last fiddled with by danaj on 20160313 at 21:27 Reason: links to Maurer/ST 
20160313, 22:24  #10  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·1,087 Posts 
Quote:
That way it will be registered under your name rather than others and kept track of here: http://factordb.com/certtop.php 

20160313, 22:30  #11  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×1,087 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime Pages Achievable Forms?  PawnProver44  Miscellaneous Math  1  20160408 11:27 
Prime pages question  jasong  jasong  7  20130309 12:10 
TPS prime pages password  Oddball  Twin Prime Search  5  20110320 04:50 
What's up with the Prime Pages?  Unregistered  Information & Answers  1  20070609 02:44 
How do I determine the xthhighest prime on prime pages?  jasong  Data  7  20050913 20:41 