20190826, 19:57  #1 
Mar 2016
258_{10} Posts 
factorisation for p1, p is prime
A peaceful evening for everyone,
is the factorisation of p1, where p is prime, mathematical an easier problem than the factorisation of f*g, where f and g are unknown primes ? Thanks in advance, if you spend me some lines. Bernhard 
20190826, 20:55  #2 
Dec 2008
you know...around...
1057_{8} Posts 
At the very least it's easier in the sense that p1 is divisible by 2, making the remaining number a tad smaller...
Last fiddled with by mart_r on 20190826 at 20:56 
20190827, 13:41  #3 
Feb 2017
Nowhere
110100011100_{2} Posts 
Invoking the "Assumption of Ignorance" (i.e. not knowing any reason to assume specialness), numbers of the form p1, p prime, p > 2, should behave generally like runofthemill even numbers. One check on this is that, by the PNT for arithmetic progressions, on average half of them are divisible by 4, a quarter are divisible by 8, and so on for higher powers of 2. I believe other confirmatory results are known, e.g. about the number of prime factors, but I'm too lazy to look up the details.

20190827, 13:59  #4 
Jun 2003
2^{6}·73 Posts 
This is incorrect. An arbitrary even number will be divisible by a prime q with probability 1/q. However it will divide p1 with probability 1/(q1)  because one of the nonzeroresidue class (mod q) is taken up by p, so p1 will fall into the zero residue class (mod q) with probability 1/(q1). This is especially noticeable for divisibility by the small primes 3,5,7,etc...

20190827, 16:11  #5  
Feb 2017
Nowhere
2^{2}×839 Posts 
Quote:
The significantly greater probability of small odd prime factors obviously makes p1 numbers at least somewhat special. One result I did turn up is On the density of odd integers of the form (p1)/2^k and related questions, P. Erdos and A. M. Odlyzko, J. Number Theory, 11 (1979), pp. 257263. Quote:


20190827, 18:08  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{7}·71 Posts 
From a practical stand point, having p prime is adding a hairthin margin into probability of being able to able to factor p1. (Factor in the sense of factoring if not fully then just to 27% factored. Not to be confused with colloquial meaning "this is factored (read: this is composite)" = "it has a factor". Because of course it has a factor,  2.)
In order to engineer a provable prime p via factoring p1 to >27%, one has to generate hundreds of candidates and then shotgun the algebraic factors  and one gets lucky no more than 1% of the time even in an artificially crafted niche. Examples: 1, 2, 3 (see comments section in each; ...while fresh in my mind). 
20190828, 15:49  #7  
Sep 2009
2·3·311 Posts 
Quote:
Chris 

20190828, 17:14  #8  
Jun 2003
2^{6}·73 Posts 
Quote:
For divisibility by 2, same thing applies  see Dr S's post. 

20190828, 19:54  #9 
"Robert Gerbicz"
Oct 2005
Hungary
3·461 Posts 
For general m, the probability is 1/eulerphi(m), and this follows trivially from the prime number theorem in arithmetic progession.

20190830, 15:48  #10  
Sep 2009
2×3×311 Posts 
Quote:
So in practice proving a prime by factoring P1 or P+1 is only practical if the prime has a special form that makes it relatively easy to factor them. Chris 

20190917, 14:20  #11 
Mar 2016
2×3×43 Posts 
A peaceful day for you,
Let f(n)=2n²1, n elem. of N i am looking for pf(n) with p prime and t(p1) with t is prime and t > 56 bits can i make a better estimation than f(n) > 2*t => n > 28 bits = 268.435.456 Greetings Bernhard 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
biquadratic complex function and possible factorisation  bhelmes  Math  1  20180808 20:19 
factorisation  devarajkandadai  Factoring  7  20130706 03:44 
Records for complete factorisation  BrianE  Math  25  20091216 21:40 
Being coy about a factorisation  fivemack  Math  7  20071117 01:27 
Kraitchik's factorisation method  Robertcop  Math  2  20060206 21:03 