factorisation for p-1, p is prime

[bhelmes]

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

[mart_r]

At the very least it's easier in the sense that p-1 is divisible by 2, making the remaining number a tad smaller...

[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. 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.

[axn]

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...

[Dr Sardonicus]

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.

Abstract: It is shown that odd integers k such that k · 2ⁿ + 1 is prime for some positive integer n have a positive lower density. More generally, for any primes p₁, ... , p_r, the integers k such that k is relatively prime to each of p₁, ... , p_r, and such that k · p₁ⁿ¹ p₂ⁿ²...p_r^nr + 1 is prime for some n1, ... , nr, also have a positive lower density.

[Batalov]

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).

[chris2be8]

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

[axn]

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.

[R. Gerbicz]

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.

[chris2be8]

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

[bhelmes]

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