factorisation for p-1, p is prime

[bhelmes]

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

[Dr Sardonicus]

Originally Posted by bhelmes

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

In general, not much. For any p == 1 (mod 4), there are two positive integers x < p for which p divides x² + 1.

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

p - 1 = a*((k² + 1)*a +/- 2*k).

This includes p = x² + 1 (k = 0), x² + (x+1)² (k = 1), etc.

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

[bhelmes]

Originally Posted by bhelmes

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

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

[bhelmes]

A peaceful and pleasant night for you,

Originally Posted by bhelmes

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

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

[R.D. Silverman]

Originally Posted by bhelmes

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.


:

Did you pull this linear transform from nowhere? Please explain, as a function of
N, 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
https://www.mersenneforum.org/showpo...7&postcount=13
by Dr. Sardonicus. Failure to listen to/respect experts while asking for their advice is
the sign of a fool. You never learn from what others try to teach you --> you are
unteachable. And I can't think of a worse insult.

[bhelmes]

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
http://devalco.de/quadr_Sieb_x%5E2+1.php


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

Bernhard

[mgb]

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

[R.D. Silverman]

Originally Posted by bhelmes

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

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

Or if you do then just factor p-1.

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

And? Once you find 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 pointless

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

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

Therefore I can state that k | p-1

You already *said this* above.

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

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.

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

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?

[LaurV]

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.

Originally Posted by bhelmes

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

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.

[bhelmes]

Originally Posted by LaurV

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.

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

Bernhard

[LaurV]

Originally Posted by bhelmes

LaurV with some jokes

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.