 mersenneforum.org factorisation for p-1, p is prime
 Register FAQ Search Today's Posts Mark Forums Read  2019-08-26, 19:57 #1 bhelmes   Mar 2016 33×11 Posts factorisation for p-1, p is prime A peaceful evening for everyone, is the factorisation of p-1, 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   2019-08-26, 20:55 #2 mart_r   Dec 2008 you know...around... 7·89 Posts At the very least it's easier in the sense that p-1 is divisible by 2, making the remaining number a tad smaller... Last fiddled with by mart_r on 2019-08-26 at 20:56   2019-08-27, 13:41 #3 Dr Sardonicus   Feb 2017 Nowhere 22×1,049 Posts Invoking the "Assumption of Ignorance" (i.e. not knowing any reason to assume specialness), numbers of the form p-1, p prime, p > 2, should behave generally like run-of-the-mill 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.   2019-08-27, 13:59   #4
axn

Jun 2003

2×52×97 Posts Quote:
 Originally Posted by Dr Sardonicus Invoking the "Assumption of Ignorance" (i.e. not knowing any reason to assume specialness), numbers of the form p-1, p prime, p > 2, should behave generally like run-of-the-mill even numbers.
This is incorrect. An arbitrary even number will be divisible by a prime q with probability 1/q. However it will divide p-1 with probability 1/(q-1) -- because one of the nonzero-residue class (mod q) is taken up by p, so p-1 will fall into the zero residue class (mod q) with probability 1/(q-1). This is especially noticeable for divisibility by the small primes 3,5,7,etc...   2019-08-27, 16:11   #5
Dr Sardonicus

Feb 2017
Nowhere

22×1,049 Posts Quote:
 Originally Posted by axn This is incorrect. An arbitrary even number will be divisible by a prime q with probability 1/q. However it will divide p-1 with probability 1/(q-1) -- because one of the nonzero-residue class (mod q) is taken up by p, so p-1 will fall into the zero residue class (mod q) with probability 1/(q-1). This is especially noticeable for divisibility by the small primes 3,5,7,etc...
D'oh! I stand corrected. The Assumption of Ignorance is unwarranted in this case.

The significantly greater probability of small odd prime factors obviously makes p-1 numbers at least somewhat special. One result I did turn up is

On the density of odd integers of the form (p-1)/2^k and related questions, P. Erdos and A. M. Odlyzko, J. Number Theory, 11 (1979), pp. 257-263.
Quote:
 Abstract: It is shown that odd integers k such that k · 2n + 1 is prime for some positive integer n have a positive lower density. More generally, for any primes p1, ... , pr, the integers k such that k is relatively prime to each of p1, ... , pr, and such that k · p1n1 p2n2...prnr + 1 is prime for some n1, ... , nr, also have a positive lower density.   2019-08-27, 18:08 #6 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·11·281 Posts From a practical stand point, having p prime is adding a hair-thin margin into probability of being able to able to factor p-1. (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 p-1 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).   2019-08-28, 15:49   #7
chris2be8

Sep 2009

111110000112 Posts Quote:
 Originally Posted by axn An arbitrary even number will be divisible by a prime q with probability 1/q. However it will divide p-1 with probability 1/(q-1) -- because one of the nonzero-residue class (mod q) is taken up by p, so p-1 will fall into the zero residue class (mod q) with probability 1/(q-1). This is especially noticeable for divisibility by the small primes 3,5,7,etc...
How does this work for divisibilty by small primes to a power? Eg how likely is p-1 to be divisible by 9 for a random large prime p? And does this apply to divisibility by powers of 2?

Chris   2019-08-28, 17:14   #8
axn

Jun 2003

2·52·97 Posts Quote:
 Originally Posted by chris2be8 How does this work for divisibilty by small primes to a power? Eg how likely is p-1 to be divisible by 9 for a random large prime p? And does this apply to divisibility by powers of 2?
Only the first instance gets 1/(q-1). For each additional instance, you will get an additional 1/q. So the probability of being divisible by 9 is 1/2*1/3 = 1/6

For divisibility by 2, same thing applies -- see Dr S's post.   2019-08-28, 19:54   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

59516 Posts Quote:
 Originally Posted by axn Only the first instance gets 1/(q-1). For each additional instance, you will get an additional 1/q. So the probability of being divisible by 9 is 1/2*1/3 = 1/6 For divisibility by 2, same thing applies -- see Dr S's post.
For general m, the probability is 1/eulerphi(m), and this follows trivially from the prime number theorem in arithmetic progession.   2019-08-30, 15:48   #10
chris2be8

Sep 2009

1,987 Posts Quote:
 Originally Posted by axn Only the first instance gets 1/(q-1). For each additional instance, you will get an additional 1/q. So the probability of being divisible by 9 is 1/2*1/3 = 1/6 For divisibility by 2, same thing applies -- see Dr S's post.
Thanks for that. I assume factoring P+1 works similarly. Larger offsets would make it a bit more complex, but those are less likely to be useful.

So in practice proving a prime by factoring P-1 or P+1 is only practical if the prime has a special form that makes it relatively easy to factor them.

Chris   2019-09-17, 14:20 #11 bhelmes   Mar 2016 33×11 Posts A peaceful day for you, Let f(n)=2n²-1, n elem. of N i am looking for p|f(n) with p prime and t|(p-1) 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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Math 1 2018-08-08 20:19 devarajkandadai Factoring 7 2013-07-06 03:44 Brian-E Math 25 2009-12-16 21:40 fivemack Math 7 2007-11-17 01:27 Robertcop Math 2 2006-02-06 21:03

All times are UTC. The time now is 09:46.

Thu Jan 28 09:46:39 UTC 2021 up 56 days, 5:57, 0 users, load averages: 3.33, 3.04, 2.63