mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-05-07, 21:47   #12
bhelmes
 
bhelmes's Avatar
 
Mar 2016

10216 Posts
Default

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
bhelmes is offline   Reply With Quote
Old 2020-05-08, 13:02   #13
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1101000111002 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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...
Dr Sardonicus is offline   Reply With Quote
Old 2020-05-09, 18:56   #14
bhelmes
 
bhelmes's Avatar
 
Mar 2016

1000000102 Posts
Default

Quote:
Originally Posted by bhelmes View Post

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
bhelmes is offline   Reply With Quote
Old 2020-05-16, 20:04   #15
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2·3·43 Posts
Default

A peaceful and pleasant night for you,


Quote:
Originally Posted by bhelmes View Post

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
bhelmes is offline   Reply With Quote
Old 2020-05-18, 12:42   #16
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2020-05-20, 20:07   #17
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2×3×43 Posts
Default

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
bhelmes is offline   Reply With Quote
Old 2020-05-20, 20:33   #18
mgb
 
"Michael"
Aug 2006
Usually at home

24×5 Posts
Default

See 'Safe Primes' and Sophie Germain primes: https://en.wikipedia.org/wiki/Safe_prime
mgb is offline   Reply With Quote
Old 2020-05-21, 02:21   #19
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
You already *said this* above.


Quote:

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.



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
R.D. Silverman is offline   Reply With Quote
Old 2020-05-21, 05:57   #20
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×17×127 Posts
Default

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 View Post
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
LaurV is offline   Reply With Quote
Old 2020-05-21, 08:58   #21
bhelmes
 
bhelmes's Avatar
 
Mar 2016

25810 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
bhelmes is offline   Reply With Quote
Old 2020-05-21, 15:47   #22
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×17×127 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
LaurV 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 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

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.