mersenneforum.org a factorisation algorithm with help of quadratic polynomials
 Register FAQ Search Today's Posts Mark Forums Read

2021-03-17, 11:38   #12
Dr Sardonicus

Feb 2017
Nowhere

26·7·13 Posts

Quote:
 Originally Posted by bhelmes Mp67 less than a second Mp101: 1 sec M1 A :31 B :4 C :4 D :1 M278557 A :51109652505043588650876826875 B :2347607336006370217211437694510 C :2347607336006370217211437694510 D :191163035652478580518938993307 ERG :7432339208719
Quote:
 Originally Posted by LarsNet Where can you look up the numbers, llke M278557, so i can test as well. ( New here, still learning )
Unfortunately, the OP's notation is very confusing. In the above, M278557 is Mod(M1, 2^101 - 1)^278557 rather than what in standard notation is the Mersenne number M278557.

I also don't know what "ERG" stands for, but it appears to indicate a factor of the number under consideration.

And unfortunately, the OP didn't indicate what polynomial and what prime he used to construct M1 for either 2^67 - 1 ("Mp67") or 2^101 - 1 ("Mp101").

2021-03-17, 11:55   #13
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

3·73 Posts

Quote:
 Originally Posted by Dr Sardonicus I also don't know what "ERG" stands for, but it appears to indicate a factor of the number under consideration.
Most likely the same as "RES", because the German word for "result" is "Ergebnis".

2021-03-17, 13:34   #14
Dr Sardonicus

Feb 2017
Nowhere

26×7×13 Posts

Quote:
Originally Posted by kruoli
Quote:
 Originally Posted by Dr Sardonicus I also don't know what "ERG" stands for, but it appears to indicate a factor of the number under consideration.
Most likely the same as "RES", because the German word for "result" is "Ergebnis".
OK, that make sense.

But there's something else I don't understand. The OP's PDF starts with a polynomial, and uses a linear substitution to produce values divisible by a given prime p, then divides out a factor of p. Fair enough.

But for the polynomial 2*x^2 - 1, the matrix M1 does not in any way represent the transformed polynomial.

For example, with 2*x^2 - 1 and p = 31, substituting 31*x + 4 for x gives 2*31^2 *x^2 + 2*2*31*4*x + 2*4^2 - 1. Dividing by 31 gives 2*31*x^2 + 2*2*4*x + 1. Now "homogenizing" these polynomials gives the binary quadratic forms

2*x^2 - y^2 and 62*x^2 + 16*x*y + y^2, which both have discriminant 8, and have the usual matrix representations M = [2,0;0,-1] and [62,8;8,1] respectively; matrix multiplication gives

[x,y]*[2,0;0,-1]*[x;y] = x^2 - 2*y^2 and [x,y]*[62,8;8,1]*[x;y] = 62*x^2 + 16*x*y + y^2.

However, the OP uses the matrix M1 = [31,4;4,1] obtained by dividing the lead coefficient of 2*31*x^2 + 2*2*4*x + 1 by 2 and the coefficient of x by 4. M1 represents the binary quadratic form

31*x^2 + 8*x*y + y^2

which has discriminant -15, and corresponds to the 1-variable polynomial 31*x^2 + 8*x + 1, which bears no obvious relation to the polynomial 2*x^2 - 1.

Last fiddled with by Dr Sardonicus on 2021-03-17 at 13:38 Reason: xinfig posty

 2021-03-17, 21:13 #15 bhelmes     Mar 2016 3·7·19 Posts Oh, I think I have made an error in the programming part, sorry for that. Covid-19 is not good for my health and takes too long. I think I will make a small holiday time. Computer is working in the background. Have a pleasant time Bernhard
 2021-03-18, 14:37 #16 Dr Sardonicus     Feb 2017 Nowhere 16C016 Posts The fact that your procedure works as intended with the "wrong" input is suggestive. It suggests that it has nothing to do with the matrix "representing" your polynomial. But the matrix you constructed shares an important matrix property with the matrix you intended. It's a special kind of square matrix whose known properties make things clear.
2021-11-12, 16:36   #17
bhelmes

Mar 2016

3×7×19 Posts

A peaceful day for you,

Quote:
 You appear to have invented an algorithm which makes trial division seem blindingly fast in comparison.
The time function, I used, was wrong. I have changed that bug and can prove that the test is not a p-1 or p+1 test with help of the chinese remainder theorem (https://en.wikipedia.org/wiki/Chines...nder_theorem):

I make a linear substitution n=p+no (where p=2(p+n0)²-1) for the polynomial f(n)=2n²-1 and divide it by p and transform it to a matrix
(2p 2n0)
(2n0 1)

which I use for exponentation with primes < 10^8

This seems to be like two congruences with
f(n)=1 mod p and
f(n)=0 mod f where f is a factor of the factored number

The solution is depending of a+b where a is depending of the first congruence and b of the second congruence.
Therefore the solution is not a p-1 or p+1 test, but "flexible" cause of the choosing p.
This is a huge progress, or ?

I add the factor of M137 with runtime (computer is a AMD FX(tm)-8300 Octa-Core Processor):

Mp : 137 factor : 32032215596496435569<20>
Matrix :
14, 4
4, 1
Prime exponent = 27978309
elapsed time: 1106.18s

Mp : 137 factor : 32032215596496435569<20>
Matrix :
194, 14
14, 1
Prime exponent = 27978707
elapsed time: 1122.35s

Mp : 137 factor : 32032215596496435569<20>
Matrix :
254, 16
16, 1
Prime exponent = 27979159
elapsed time: 1150.24s

By the way, the second stage (B2) is still missing in my program.

Any suggestion how to perform the second stage (similar to eliptic curves)
and how to balance B1 and B2 ?

Last fiddled with by bhelmes on 2021-11-12 at 16:57

2021-12-21, 00:57   #18
bhelmes

Mar 2016

3×7×19 Posts

Quote:
 Originally Posted by bhelmes The solution is depending of a+b where a is depending of the first congruence and b of the second congruence. Therefore the solution is not a p-1 or p+1 test, but "flexible" cause of the choosing p.
There was a serious bug in my program and the main question for me is:
Is it a p-1 test or is it "flexible" and depends on the choosen matrix.

If someone has enough Algebra knowledge it would be nice to get a short answer.

 2021-12-21, 16:40 #19 jwaltos     Apr 2012 Oh oh. 22·5·23 Posts You may be setting yourself up for failure and "less than" benevolent comments. As a simple and cursory check look at the "Implementation" section of https://en.wikipedia.org/wiki/Pollar...92_1_algorithm Ask yourself, where are you situated in relation to "anyone else" who has looked at what you're looking at seriously. You will be outclassed in resources such as equipment, theory, time and a few other things but only you think the way you do so if you believe you have a good idea then work it to perfection and try not to present prototypes. There are always consequences so try to anticipate those as well. Do your homework and study relative to your abilities. An easy check would be to look at arXiv papers on any subject that interests you..or better yet..look at Quanta articles. I have a couple of recent books ..The Wall of Fire and Prime Number Conspiracy which I found to be engaging and ties together a number of peer reviewed papers I've read. I'll add one more, Nahin's "Dr. Euler's Fabulous Formula" and read the top paragraph on p.221 for instance. Whatever you present .. and I try to do the same..is to make it flawless regardless of the simplicity/complexity. My communication skills are generally poor and whatever spoor (pun and double entendre) I leave is targeted toward a particular audience keeping in mind all the eyes and bots that review this forum. A word of encouragement, you are in the right ballpark from my perspective but you really need to latch your imagination onto mathematical facts and proofs, try to do some proofs on your own as a self test (ie. Laplace Transform). As a final thought, watch the initial season (or more) of Ted Lasso..cheers. Last fiddled with by jwaltos on 2021-12-21 at 17:05 Reason: corrections
2022-01-26, 02:12   #20
bhelmes

Mar 2016

6178 Posts

Quote:
 Originally Posted by bhelmes Is it a p-1 test or is it "flexible" and depends on the choosen matrix.

The special linear group, SL(n, F), is the group of all matrices with determinant 1.

When F is R or C, SL(n, F) is a Lie subgroup of GL(n, F) of dimension n^2 − 1.

https://en.wikipedia.org/wiki/Genera...l_linear_group

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Number Theory Discussion Group 2 2021-01-24 10:14 bhelmes Math 21 2020-03-19 22:14 bhelmes Computer Science & Computational Number Theory 2 2019-08-24 15:00 bhelmes Computer Science & Computational Number Theory 3 2017-05-27 01:33 R1zZ1 Factoring 36 2007-11-02 15:59

All times are UTC. The time now is 05:19.

Sun Jun 26 05:19:27 UTC 2022 up 73 days, 3:20, 1 user, load averages: 1.55, 1.20, 1.03