mersenneforum.org factorisation for p-1, p is prime
 Register FAQ Search Today's Posts Mark Forums Read

 2020-05-07, 21:47 #12 bhelmes     Mar 2016 10216 Posts 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
2020-05-08, 13:02   #13
Dr Sardonicus

Feb 2017
Nowhere

1101000111002 Posts

Quote:
 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 x2 + 1.

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

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

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

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

2020-05-09, 18:56   #14
bhelmes

Mar 2016

1000000102 Posts

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

Last fiddled with by bhelmes on 2020-05-09 at 19:02

2020-05-16, 20:04   #15
bhelmes

Mar 2016

2·3·43 Posts

A peaceful and pleasant night for you,

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

2020-05-18, 12:42   #16
R.D. Silverman

Nov 2003

22×5×373 Posts

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

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.

 2020-05-20, 20:07 #17 bhelmes     Mar 2016 2×3×43 Posts 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
 2020-05-20, 20:33 #18 mgb   "Michael" Aug 2006 Usually at home 24×5 Posts See 'Safe Primes' and Sophie Germain primes: https://en.wikipedia.org/wiki/Safe_prime
2020-05-21, 02:21   #19
R.D. Silverman

Nov 2003

22·5·373 Posts

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

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

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
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:
 It is much better to know the factor k | p-1 in advance
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.

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?

Last fiddled with by R.D. Silverman on 2020-05-21 at 02:22 Reason: add request

2020-05-21, 05:57   #20
LaurV
Romulan Interpreter

Jun 2011
Thailand

22×17×127 Posts

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

Last fiddled with by LaurV on 2020-05-21 at 05:59

2020-05-21, 08:58   #21
bhelmes

Mar 2016

25810 Posts

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

Last fiddled with by bhelmes on 2020-05-21 at 09:50

2020-05-21, 15:47   #22
LaurV
Romulan Interpreter

Jun 2011
Thailand

22×17×127 Posts

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

 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 14:31.

Sat Aug 15 14:31:12 UTC 2020 up 2 days, 11:06, 1 user, load averages: 1.75, 1.77, 1.79