mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-08-26, 19:57   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

22×67 Posts
Default 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
bhelmes is offline   Reply With Quote
Old 2019-08-26, 20:55   #2
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

10001111012 Posts
Default

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
mart_r is offline   Reply With Quote
Old 2019-08-27, 13:41   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

66028 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2019-08-27, 13:59   #4
axn
 
axn's Avatar
 
Jun 2003

10010010101012 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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...
axn is offline   Reply With Quote
Old 2019-08-27, 16:11   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·7·13·19 Posts
Default

Quote:
Originally Posted by axn View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2019-08-27, 18:08   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23A416 Posts
Default

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).
Batalov is offline   Reply With Quote
Old 2019-08-28, 15:49   #7
chris2be8
 
chris2be8's Avatar
 
Sep 2009

76216 Posts
Default

Quote:
Originally Posted by axn View Post
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
chris2be8 is offline   Reply With Quote
Old 2019-08-28, 17:14   #8
axn
 
axn's Avatar
 
Jun 2003

111258 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
axn is offline   Reply With Quote
Old 2019-08-28, 19:54   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

25618 Posts
Default

Quote:
Originally Posted by axn View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2019-08-30, 15:48   #10
chris2be8
 
chris2be8's Avatar
 
Sep 2009

76216 Posts
Default

Quote:
Originally Posted by axn View Post
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
chris2be8 is offline   Reply With Quote
Old 2019-09-17, 14:20   #11
bhelmes
 
bhelmes's Avatar
 
Mar 2016

10C16 Posts
Default

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
bhelmes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
biquadratic complex function and possible factorisation bhelmes Math 1 2018-08-08 20:19
factorisation devarajkandadai Factoring 7 2013-07-06 03:44
Records for complete factorisation Brian-E Math 25 2009-12-16 21:40
Being coy about a factorisation fivemack Math 7 2007-11-17 01:27
Kraitchik's factorisation method Robertcop Math 2 2006-02-06 21:03

All times are UTC. The time now is 08:59.

Sun Sep 20 08:59:44 UTC 2020 up 10 days, 6:10, 0 users, load averages: 0.86, 1.32, 1.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.