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. :loco: :hello: :beatdown: :cmd:

Bernhard

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

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.

[QUOTE=Dr Sardonicus;524657]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. [/QUOTE]

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

[QUOTE=axn;524659]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...[/QUOTE]D'oh! :gah: 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 [i]somewhat[/i] special. One result I did turn up is

[i]On the density of odd integers of the form (p-1)/2^k and related questions[/i], P. Erdos and A. M. Odlyzko, J. Number Theory, 11 (1979), pp. 257-263.
[quote][b]Abstract:[/b] It is shown that odd integers k such that k · 2[sup]n[/sup] + 1 is prime for some positive integer n have a positive lower density. More generally, for any primes p[sub]1[/sub], ... , p[sub]r[/sub], the integers k such that k is relatively prime to each of p[sub]1[/sub], ... , p[sub]r[/sub], and such that k · p[sub]1[/sub][sup]n1[/sup] p[sub]2[/sub][sup]n2[/sup]...p[sub]r[/sub][sup]nr[/sup] + 1 is prime for some n1, ... , nr, also have a positive lower density.[/quote]

From a practical stand point, having p prime is adding a hair-thin margin into probability of being able to able to [I]factor [/I]p-1. ([I]Factor[/I] 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: [URL="https://primes.utm.edu/primes/page.php?id=126708"]1[/URL], [URL="https://primes.utm.edu/primes/page.php?id=129884"]2[/URL], [URL="https://primes.utm.edu/primes/page.php?id=129880"]3[/URL] (see comments section in each; ...while fresh in my mind).

[QUOTE=axn;524659]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...[/QUOTE]

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

[QUOTE=chris2be8;524739]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?[/QUOTE]

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.

[QUOTE=axn;524744]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.[/QUOTE]

For general m, the probability is 1/eulerphi(m), and this follows trivially from the prime number theorem in arithmetic progession.

[QUOTE=axn;524744]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.[/QUOTE]

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

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 :loco::petrw1: :tom:

Bernhard

A peaceful and pleasant night for you,


if I regard only the primes p>=5 with p=x²+1 (x>1) and
the primes p with p | (x²+1 ) with p > x


can i derive any suggestion about the factorisation of p-1 in advance
(except divisible by 4 :-) )


Some nice words toward this topic would be nice, the day was ugly for me.


Greetings

Bernhard :loco::cmd: :hello:

[QUOTE=bhelmes;544844]A peaceful and pleasant night for you,


if I regard only the primes p>=5 with p=x²+1 (x>1) and
the primes p with p | (x²+1 ) with p > x


can i derive any suggestion about the factorisation of p-1 in advance
(except divisible by 4 :-) )[/QUOTE]
In general, not much. For [i]any[/i] p == 1 (mod 4), there are two positive integers x < p for which p divides x[sup]2[/sup] + 1.

There is one situation in which there is an easy algebraic factorization of p - 1. If p = a[sup]2[/sup] + b[sup]2[/sup], and b = k*a +/- 1 for some integer k, then

p - 1 = a*((k[sup]2[/sup] + 1)*a +/- 2*k).

This includes p = x[sup]2[/sup] + 1 (k = 0), x[sup]2[/sup] + (x+1)[sup]2[/sup] (k = 1), etc.

Unfortunately, such p are fairly thin on the ground...

[QUOTE=bhelmes;544844]

can i derive any suggestion about the factorisation of p-1 in advance
(except divisible by 4 :-) )

[/QUOTE]


if p=x²+1 then x | p-1


if p | (x²+1) ???


Can I calculate q=x²+1 with q=r*p and x and r known; then f | p-1 ; f ???


If someone knows a good answer would be very nice to get it.


Greetings
Bernhard :cmd::hello::gah:

A peaceful and pleasant night for you,


[QUOTE=bhelmes;544844]

can i derive any suggestion about the factorisation of p-1 in advance
(except divisible by 4 :-) )


[/QUOTE]

Yes, there is a mathematical possibility:


f(x)=x²+1
f(27)=10*73


Substitution with x=10k-3 (k=3) gives
f(k)=(10k-3)²+1
= 100k²-60k+10 | Division by 10
= 10k²-6k+1 | -1 since I need the factorisation of p-1
=k(10k-6)


Therefore k=3 is a factor of p-1 resp. 73-1


This is a good news and will give some results soon.




Greetings

Bernhard :cmd: :hello::uncwilly:

[QUOTE=bhelmes;545551]A peaceful and pleasant night for you,




Yes, there is a mathematical possibility:


f(x)=x²+1
f(27)=10*73


Substitution with x=10k-3 (k=3) gives
f(k)=(10k-3)²+1
= 100k²-60k+10 | Division by 10
= 10k²-6k+1 | -1 since I need the factorisation of p-1
=k(10k-6)


Therefore k=3 is a factor of p-1 resp. 73-1


This is a good news and will give some results soon.


:[/QUOTE]

Did you pull this linear transform from nowhere? Please explain, [b]as a function of
N[/b], what transform one does when factoring f(N). Please explain your algorithm to
find the transform without knowing the factorization of N.

Note also that knowing 3 | (p-1) for p|N does not help very much in practice.

Finally, please explain the "good news". Stop giving yourself accolades.

In point of fact, it is not "good news". It is just blind numerology.

One day you may actually learn to listen to people who are experts. Such as post #13
[url]https://www.mersenneforum.org/showpost.php?p=544877&postcount=13[/url]
by Dr. Sardonicus. Failure to listen to/respect experts while asking for their advice is
the sign of a fool. You [b]never[/b] learn from what others try to teach you --> you are
unteachable. And I can't think of a worse insult.

A peaceful and pleasant night for you,

Perhaps I should explain the algorithm and the solution a little bit better.


I have the factorisation of
f(n)=n²+1=r*p where r element of N and p is prime


I can assume that p is really a prime because of the construction
of the quadratic sieve, detailled described under
[url]http://devalco.de/quadr_Sieb_x%5E2+1.php[/url]


So, I want to find a non trival factor of p-1 [4| (p-1) ]


From the point of the finishing I would like to have p-1 = k(k+a)


That means p=k(k+a)+1


I make a linear substitution in order to split the r from the quadratic equation, that means I substitute
n=k*r+s where s=n mod r and s²+1 = 0 mod r



Substitution gives f(k)=(kr+s)²+1
<=> k²r²+2krs+s²+1


s²+1 = r This is the trick


after division by r I get
p=k²r+2ks+1 |-1

p-1=k²r+2ks
p-1=k (kr+2s) Goal reached


Therefore I can state that k | p-1


Perhaps someone understand this prove
and perhaps someone will see the improvement.


It is much better to know the factor k | p-1 in advance

especially if you want to check, if 2^[(p-1)/k] = 1 mod p


@Silverman: This is not numerology, but a nice piece of math.


Have a pleasant night :missingteeth: :tom::motorhome:

Bernhard

See 'Safe Primes' and Sophie Germain primes: [url]https://en.wikipedia.org/wiki/Safe_prime[/url]

[QUOTE=bhelmes;546023]A peaceful and pleasant night for you,

Perhaps I should explain the algorithm and the solution a little bit better.


I have the factorisation of
f(n)=n²+1=r*p where r element of N and p is prime
[/QUOTE]

The purpose of finding a factor of p-1 is to help factor f(n) [i]without knowing p![/i].
Once you know p you don't [b]need[/b] to find a factor of p-1.

Or if you do then just factor p-1.




[QUOTE]
I can assume that p is really a prime because of the construction
of the quadratic sieve, detailled described under
[url]http://devalco.de/quadr_Sieb_x%5E2+1.php[/url]
[/QUOTE]

And? Once you [b]find[/b] a prime factor p of f(n) all you need do is then find
a prime factor of p-1. After all, p is now known. All the rest of the drivel given
below is [b][i]pointless[/i][/b]


[QUOTE]
So, I want to find a non trival factor of p-1 [4| (p-1) ]


From the point of the finishing I would like to have p-1 = k(k+a)





That means p=k(k+a)+1
[/QUOTE]

Profound. All you have said is that k is a factor of p-1 and you want to find it.

<bunch of irrelevant drivel deleted,.....>


[QUOTE]
Therefore I can state that k | p-1
[/QUOTE]

You already *said this* above.


[QUOTE]

It is much better to know the factor k | p-1 in advance
[/QUOTE]

Advance of what??? Advance of factoring f(n)???
Yes, it would indeed elp the P-1 factoring algorithm. But once again you failed to
read Dr. Sardonicus' post that I referred to.



[QUOTE]

@Silverman: This is not numerology, but a nice piece of math.
[/QUOTE]


Once again you are giving yourself accolades for something that is just plain silly.

Is your ego so weak that you have to tell the world that what you are doing is great?

There is no way to know ( other than the factor of 4) a factor of p-1 prior to factoring
f(n). Your silliness starts by finding p! The problem is to find a factor of p-1
without knowing p. Once you know p then just factor p-1!! You start off by assuming
that you already know what you are looking for.


I'll say it again. You just don't listen.

Will someone move this to misc.math?

It looks like his goal is to factor p-1, not to factor n or f(n). More exactly, he tries to factor a factor of p-1 (call it x). For this he first "inflates" x to p, then p to f(n), and tries to do some "tricks" there. Unfortunately that will not work, as already pointed by the other posters.

[QUOTE=bhelmes;546023]I make a linear substitution in order to split the r from the quadratic equation, that means I substitute n=k*r+s where s=n mod r and s²+1 = 0 mod r
[/QUOTE]
No, you can't. You don't know k. If you know k, then your p-1=k(k+a) is already factored. Take a large odd number x of 20 digits which has no small factors, and try.

Find a prime p of the form mx+1 with natural m.

Find a natural r such as y=rp=square+1 (this is what you call f(n))

Then you are in the right conditions to apply your algorithm. What is the substitution, beside of the trivial one (as you know p-1=mx). Remember, you need to factor x.

[QUOTE=LaurV;546073]
No, you can't. You don't know k. If you know k, then your p-1=k(k+a) is already factored. Take a large odd number x of 20 digits which has no small factors, and try.
[/QUOTE]


A peaceful day for you, LaurV


who should type a 20 digits example ?

I will give a second example which is working:


f(n)=n²+1
f(92)=5*1693
k=trunc (92/5)=18
1692/18=94



In the worst case k is equal 1, but there are a lot of numbers

where k is a proper factor.


@Silverman: You seem to be generous with some insults, LaurV with some jokes and me with some accolades.
Sounds like chocolade and was a new word I have learned.



Enjoy the day :geek: :cool: :loco:

Bernhard

[QUOTE=bhelmes;546080]LaurV with some jokes[/QUOTE]
There was no joke on my side. I only tried to help. If you understood it as a joke, then either my understanding, or my explanation, or both, suck.

[quote=bhelmes;544844]if I regard only the primes p>=5 with p=x²+1 (x>1) and
the primes p with [b]p | (x²+1 ) with p > x[/b]


can i derive any suggestion about the factorisation of p-1 in advance
(except divisible by 4 :-) )[/quote]

[quote=bhelmes;544969]if p=x²+1 then x | p-1


if p | (x²+1) ???


Can I calculate q=x²+1 with q=r*p [b]and x and r known[/b]; then f | p-1 ; f ???[/quote]

[quote=bhelmes;546023]I have the factorisation of
f(n)=n²+1=r*p where r element of N and p is prime[/quote]

It might help if you wouldn't keep trying to change the question.

In the first above-quoted post, you're asking whether knowing the x < p for which p divides x[sup]2[/sup] + 1 is of any help in factoring p-1. The answer is "No."

In the second above-quoted post, your hypothesis "x [i]and[/i] r known" is nonsensical.

In the third above-quoted post, are assuming that [i]n[/i] is given (this variable was named x in previous posts; so in addition to changing the question, you are also gratuitously changing your notation). And, apparently, you are [i]now[/i] asking whether, knowing n and a prime factor p of n[sup]2[/sup] + 1, helps factor p - 1.

Again, the answer is "No." What you [i]do[/i] know is that n (mod p) is one of the square roots of -1 (mod p); -n (mod p) is the other square root of -1 (mod p).

Knowing the square roots of -1 (mod p) can help find a and b such that p = a[sup]2[/sup] + b[sup]2[/sup]. You could then check whether the condition I mentioned in [url=https://www.mersenneforum.org/showpost.php?p=544877&postcount=13]this post[/url] is satisfied; and, [i]if[/i] you're [i]very[/i] lucky and it [i]is[/i] satisfied, obtain a (hopefully non-trivial) factorization of p-1. But as I pointed out, the primes p for which the condition is satisfied are thin on the ground. And unfortunately, they appear to be [i]thinner[/i] on the ground than primes p == 1 (mod 4) for which (p-1)/4 is actually [i]prime[/i]. I'm guessing that p == 1 (mod 4), p <= X for which (p-1)/4 is prime have an asymptotic of order X/log[sup]2[/sup](X). The ones satisfying the condition I mentioned before, I have no idea, except numerical data indicate a smaller asymptotic.

Perhaps someone who knows the subject better than I could indicate what is known for the proportion of primes p == 1 (mod 4) for which the largest prime factor of p-1 is greater than p[sup]c[/sup] where 0 < c < 1.

A peaceful evening for you,

perhaps my mathematical skill is not the best in explaining,
but i am sure that the math behind it is right.

Therefore I try again to explain it and will give an example
which deals although for 20 digit numbers :cool::

Let f(n)=2n²-1

f(n0)=f(2)=7

Substitution with n=7k+2

f(7k+2)=2(7k+2)²-1= 98k²+56k+7 | :7
f(7k+2)/7 = 14k²+8k+1 | -1 because I am looking for the factorization of f(n)-1

f(7k+2)/7-1 = 14k²+8k = 2k*(7k+4)

Therefore I can predict the factorization of f(7k+2)/7-1

k=3 f(7*3+2)/7 - 1 = 150 3|150
k=5 f(7*5+2)/7 - 1 = 390 5|390
k=7 f(7*7+2)/7 - 1 = 742 7|742
and so on.

That is not a factorization but a prediction which is helpful.

I think this explication is mathematical o.k.:
making a substitution for x0, subtraction one and finishing.

@LaurV I think you will understand why this is a progress, or :brian-e:

Enjoy the evening. :cmd:
Bernhard

[QUOTE=bhelmes;551121]
@LaurV I think you will understand why this is a progress, or :brian-e:
[/QUOTE]
Well, honestly, I have a bit of an issue understanding how you pick your substitution. I think that sieving was better :smile: With the current concept it seems to me that you moved the dead cat from factoring to picking the substitution (which is kinda random. Or :shock:)

[QUOTE=LaurV;551156]Well, honestly, I have a bit of an issue understanding how you pick your substitution. [/QUOTE]

In general :

let f(n)=2n²-1

f(n0)=r

then the substitution is n=f(n0)*k+n0 with the following division by f(n0)


I think I will combine the sieving algorithm with the prediction by adding a value for the k for every prime.

Well... come up with one previously-unknown ~80 bits factor and all naysayers will keep quite for a while... :razz:
But for that, you will need n to be as large as 40 to 45 bits (unless extremely lucky), which may take like few months or a year so (wild ass guess here), even slower than a PRP test.

A peaceful day for you, LaurV



[QUOTE=LaurV;551417]Well... come up with one previously-unknown ~80 bits factor and all naysayers will keep quite for a while... :razz:
But for that, you will need n to be as large as 40 to 45 bits (unless extremely lucky), which may take like few months or a year so (wild ass guess here), even slower than a PRP test.[/QUOTE]


I think I will use the function f(n)=2n²-1 from n=1 up to 2^40,
will calculating the factors / primes f(m) with f>m and will storing the m for each f, will make a jump to n=2^46 and a sieve up to 2^46+2^40.
You can use the chinese remainder lemma for using the prediction.
(Any idea what I try to achieve ?)



All in all, will finish work before Christmas,
today it is hot in Germany and not the best time for programming.



What about a mathemtical prediction about the density /

distribution of mersenne factors concerning f(n)=2n²-1 ?


Greetings
Bernhard

[QUOTE=bhelmes;553033]
What about a mathemtical prediction about the density /
distribution of mersenne factors concerning f(n)=2n²-1 ?

[/QUOTE]


I have some datas up to 2^40 for the primesieving for the polynomial

f(n)=2n²-1;
[url]http://devalco.de/quadr_Sieb_2x%5E2-1.php#4a[/url]


I think the density of "non reducible primes" (p=f(n))
is an upper limit for the density of Mersenne primes.


Hence a complete factorisation for f(n) from 1 up to 2^40 should give 6,8439 % of "non coverage"



I am not very skilled in these questions.


May be someone has a better approximation.


Greetings :cmd: :gah: :petrw1:

Bernhard

A peaceful and pleasant night for you,


I have primes p ~ 120 bits big,

I want to factorize p-1,
I do a f=gcd (8*9*25*7*11*13*17*19*23*29*31*37*41, p-1) and
check wether 2^[(p-1)/f]=1 mod p
If this is true I check if g=(p-1)/f is prime,
otherwise I try to make a factorisation of g with ecm


I tried with 5 steps:
[CODE]
switch (count_try)
{
case 0 : g1=ecm_factor (res, input, 3000, 0); break;
case 1 : g1=ecm_factor (res, input, 4000, 0); break;
case 2 : g1=ecm_factor (res, input, 5000, 0); break;
case 3 : g1=ecm_factor (res, input, 6000, 0); break;
case 4 : g1=ecm_factor (res, input, 7000, 0); break;
}
[/CODE]Can I improve the B1 limits ?

(Actual I get 1/25 non factorized candidates)

The program is nearly ready for a longer search.

Thanks if you spend me some lines :loco::brian-e: :truck:

Bernhard

A peaceful day,


this is the end of a wonderful programming episode:
Running of the program was only one day,
I used 59 GByte Ram for storing the sieving primes,
used ecm-library and a parallisation on 12 cores
and sieved a segment for n=2^62 for the function f(n)=2n²-1


The wonderful results can be found here:
M* is the Mersenne number, factor of Mp, n, ratio
[URL]http://devalco.de/results_62.html[/URL]


The ratio = (factor-1) / Mp is unfortunately low. :cry: :cmd:



If someone knows a good sentence in order to close the thread,
be free and transmit it. :tom: :tom: :tom:

Those are all [U][B]trivial[/B][/U] factors, mostly SG factors (p is 4k+3 and 2p+1 is prime) which can be found with no effort**, or they have a very small k (like q=2kp+1, with k=1, 3, 4, 5), and none of the mersenne numbers attached to them are in the GIMPS 1G range of interest (not even under 2^32, or under 10G range of interest for mersenne.ca).

--------
if(p%4=3 and isprime(p) and isprime(q=2*p+1), print(p,q))