mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-06-11, 22:25   #221
Max0526
 
"Max"
Jun 2016
Toronto

19·47 Posts
Default Thank you!

After a week of hard work and 220 posts in this thread, we have 95 lines done!
82 of these lines were never calculated before (after completing 85 much easier lines producing 85*2=170 points on the plot, 13 plot points remained not shown on the Figure 3 of the preprint).
You have completed 95-13=82 much harder lines! And more are coming.
The full plot now has (85+82)*2=334 plot points. I was dreaming about ~250 a week ago.

Thank you all a lot for this factoring effort!

Please don't hesitate to send me a PM with the donation suggestions for any of the upcoming projects.
On top of that, as a result of this project, I'll probably write and share a version of the non-standard SNFS spinner for everybody's future use.
If someone wants to rewrite my Maple/msieve/cownoise GNFS spin procedure into one piece of Python/Magma/SageMath/PARI/GP/etc code, please let me know.

And these huge GCD factors and swishzzz's Python script are pure genius! I bet we'll get more record level rank 6 Z2xZ6 elliptic curves just because of that p26 that was already posted before, and was noticed after midnight.
Quote:
Originally Posted by swishzzz View Post
I just found this 26 digit prime factor 48302990143744527119714651 of the c184 (http://factordb.com/index.php?id=1100000002599666930) in (10, -4), but when I reported it the factor was apparently already found as a divisor of one of the composites in (9, -4). I don't think this is a coincidence? Is there some way to identify large factors of the discriminant for point (m, n) which also divides the discriminant for point (m+1, n)?
We may be lucky to discover something similar on two other plots (Figures 1 and 2) and the connected (hyper)elliptic curves and projective closures. I am still trying, the script helps a lot so far.

I am still planning to add more factorable lines to the sheet, just need some sleep and rest.
Max0526 is offline   Reply With Quote
Old 2021-06-11, 22:37   #222
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

72×131 Posts
Default

Code:
x^4 - 96*x^3 + 2232*x^2 - 17280*x + 32400
x^4 - 24*x^3 + 288*x^2 - 4320*x + 32400
x^4 + 192*x^3 - 5544*x^2 + 34560*x + 32400
I can't help noticing that those polynomials have increasing powers of six in the coefficients, so for each of them f(6x)/6^4 has smaller coefficients (constant term becomes 25). That feels as if it makes the rational sides a bit smaller, though probably only by removing by construction factors of 2 and 3 that will come out instantly in the sieving.
fivemack is offline   Reply With Quote
Old 2021-06-12, 01:06   #223
Max0526
 
"Max"
Jun 2016
Toronto

89310 Posts
Default

Quote:
Originally Posted by fivemack View Post
Code:
x^4 - 96*x^3 + 2232*x^2 - 17280*x + 32400
x^4 - 24*x^3 + 288*x^2 - 4320*x + 32400
x^4 + 192*x^3 - 5544*x^2 + 34560*x + 32400
I can't help noticing that those polynomials have increasing powers of six in the coefficients, so for each of them f(6x)/6^4 has smaller coefficients (constant term becomes 25). That feels as if it makes the rational sides a bit smaller, though probably only by removing by construction factors of 2 and 3 that will come out instantly in the sieving.
I will try it right now on the spinner that I have coded some time ago already.
With GNFS polys, I can predict how high the E score will be just by looking at the log(|c1*c2*...*c6*Y1*Y0|), or simply the length of the string listing all signless coefficients -- in general, the lower the log/length, the higher the E score.
With SNFS polys, especially when some of the Ci=0, the log measure is useless, it will most probably return negative infinity. Then you are stuck with the sum |c1|+|c2|+...+|c6|. You can't even include |Y0|+|Y1| into it as they are huge and will definitely sway your estimate.
Which is why I need Shi Bai's paper to implement the proper calculation of the E score with the pre-calculated value of skew, take 10 best and run them through cownoise to optimize the skew and E.
If swishzzz steps in with his impressive Python skills, the last step could be automated as well. His script will send any number of polys we want (not just our best 10) to cownoise, receive the cownoise rating, and output the best.
Max0526 is offline   Reply With Quote
Old 2021-06-12, 02:06   #224
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·3·293 Posts
Default

Quote:
Originally Posted by Max0526 View Post
Which is why I need Shi Bai's paper to implement the proper calculation of the E score with the pre-calculated value of skew, take 10 best and run them through cownoise to optimize the skew and E.
If swishzzz steps in with his impressive Python skills, the last step could be automated as well. His script will send any number of polys we want (not just our best 10) to cownoise, receive the cownoise rating, and output the best.
If it helps at all, I am pretty close to finishing a skew optimizer for yafu as well, after learning about the possibility in this thread. yafu calls msieve internally to evaluate polynomials, and msieve of course is awesome and does all the murphy math. So hopefully pretty soon yafu could be another tool for evaluating/optimizing different polys.

This thread led me to improve yafu's ability to work with snfs polynomials, so I thank you for that opportunity.
bsquared is offline   Reply With Quote
Old 2021-06-12, 02:09   #225
Max0526
 
"Max"
Jun 2016
Toronto

19·47 Posts
Default L^2-norm in Shi Bai's paper

Found the paper: https://hal.inria.fr/hal-01089507/fi...t-20140905.pdf
I was wrong. How could I forget? The whole point of writing that paper was to introduce the L^2-norm as an alternative (and better) predictor of how good the GNFS poly is after the size and root optimization.
Formula (2.2) on page 2, where d is a poly degree (d = 4 for us now), s is the skew (could be taken as a standard estimate from c0 and c4 for each poly during the spin). We can drop (1/2)log and pi/7168, and set c5=c6=0.
Nine simple terms before simplification (it will simplify when s is given explicitly, and all ci~=ci*s^(i-2) are set).
The lower the L^2-norm, the better the poly.
Will code and report the results during the weekend.
Max0526 is offline   Reply With Quote
Old 2021-06-12, 02:33   #226
Max0526
 
"Max"
Jun 2016
Toronto

19·47 Posts
Default

Quote:
Originally Posted by bsquared View Post
If it helps at all, I am pretty close to finishing a skew optimizer for yafu as well, after learning about the possibility in this thread. yafu calls msieve internally to evaluate polynomials, and msieve of course is awesome and does all the murphy math. So hopefully pretty soon yafu could be another tool for evaluating/optimizing different polys.

This thread led me to improve yafu's ability to work with snfs polynomials, so I thank you for that opportunity.
Joint project then! We'll pick some composites, create 4 (or 8 if possible) first SNFS polys and try to spin them into something better.
Anybody who has input on the topic or preferences for the numbers/polys to spin, please share in this thread.
Now I need to ask swishzzz nicely to rewrite my final product (a page of Maple code) into something free and readily available to everybody.
If not, I start thinking about Magma Calculator. The code and the output are short and fast, should be no problem. Maybe fivemack will help there.
Max0526 is offline   Reply With Quote
Old 2021-06-12, 03:25   #227
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

963110 Posts
Default

Quote:
Originally Posted by Max0526 View Post
Please don't hesitate to send me a PM with the donation suggestions for any of the upcoming projects.
If I will ever meet you in real life, which is slim chance, but who knows? the world is small, and I have met in the past some forum members (and their families) which I wouldn't dream of, considering my geographic locations, well, if, then you will have to donate me a beer.
Edit, PS: till then, you can donate me a poly for aliquot 814848 C156, this is freaking unlucky, it takes my yafu about 16 hours to get a poly, in theory, but after about 24 hours, 10 of 18 cores are still searching and I can't stop it because there is no way to resume. In this munsoonic season here the electricity stops few times per week for few minutes (or more, depending on the damage caused by rain, lightning, etc) and I am already at the forth or fifth tentative, which means I already spent over 5 days for this f'king poly and I still have no result. Sorry for hacking the thread, you don't need to answer here, if you decide to spin a poly for me than send me a PM. If not, no problem. My GPUs are now busy doing P-1 in 35M, and anyhow, I never managed to run poly selection on GPU.

Last fiddled with by LaurV on 2021-06-12 at 03:35
LaurV is offline   Reply With Quote
Old 2021-06-12, 03:39   #228
Max0526
 
"Max"
Jun 2016
Toronto

19×47 Posts
Default Anyone is good at patterns?

Quote:
Originally Posted by fivemack View Post
Code:
x^4 - 96*x^3 + 2232*x^2 - 17280*x + 32400
x^4 - 24*x^3 + 288*x^2 - 4320*x + 32400
x^4 + 192*x^3 - 5544*x^2 + 34560*x + 32400
I can't help noticing that those polynomials have increasing powers of six in the coefficients, so for each of them f(6x)/6^4 has smaller coefficients (constant term becomes 25). That feels as if it makes the rational sides a bit smaller, though probably only by removing by construction factors of 2 and 3 that will come out instantly in the sieving.
These are copy-pasted polys from the shared Magma script. What do you (anybody, not just fivemack) notice here?
Let's compare what we see please.
The level of math is pretty high to write a paper like that, I definitely miss something (most probably a lot), and have too many question so far.
Code:
polinomi:=[
    x - 4,
    2*x - 7,
    x,
    x^2 - 12*x + 28,
    x^2 - 6*x + 7,
    x^4 - 24*x^3 + 152*x^2 - 336*x + 196,
    2*x^4 - 30*x^3 + 169*x^2 - 420*x + 196*2,
    x^4 - 12*x^3 + 62*x^2 - 168*x + 196,
    x^4 - 6*x^3 + 17*x^2 - 84*x + 196
];
One question that still puzzles me most.
We know that two GCDs for pairs of point (n-1,m), (n,m) and (n,m), (n+1,m) always split the number generated by x^4 - 24*x^3 + 152*x^2 - 336*x + 196, where x=a.
This means that the value of a produced by the Magma script always has the form of a = a(z) for some z that depends on point co-ordinates (n,m), and if we sub a(z) into a^4 - 24*a^3 + 152*a^2 - 336*a + 196, we would always be able to factor it in terms of z, most probably very close to (a^2+...)(a^2+...), as the factors are always roughly the same size.

Question. What is the explicit formula for a(z)? (I know it's out there somewhere). Can it be obtained somehow?
My ballpark suggestion is that a(z) is not more complex than
Code:
a(z)=\frac{k_1z^2+k_2z+k_3}{z^2+k_4z+k_5}
Can we find k1, k2, ..., k5? All of them are most probably comparatively small constants (+-200 tops). What would they be to factor a^4 - 24*a^3 + 152*a^2 - 336*a + 196? Can we find a smarter approach than running 400^5 through the loops?
Any ideas are welcome here.
Max0526 is offline   Reply With Quote
Old 2021-06-12, 04:42   #229
Max0526
 
"Max"
Jun 2016
Toronto

89310 Posts
Default

Quote:
Originally Posted by LaurV View Post
you can donate me a poly for aliquot 814848 C156
I sent you a PM with a c156 poly.
Max0526 is offline   Reply With Quote
Old 2021-06-12, 05:38   #230
bur
 
bur's Avatar
 
Aug 2020

22×3×52 Posts
Default

Quick update to the c165:


Initial relations wanted was 17032060, after filtering cado decided it needs 17820319. ETA is about 3-4 hours. I hope this won't repeat too often... :D


There were about 10e6 unique relations if that's any indication.
bur is offline   Reply With Quote
Old 2021-06-12, 05:50   #231
Max0526
 
"Max"
Jun 2016
Toronto

37D16 Posts
Default

Quote:
Originally Posted by bur View Post
Quick update to the c165:


Initial relations wanted was 17032060, after filtering cado decided it needs 17820319. ETA is about 3-4 hours. I hope this won't repeat too often... :D


There were about 10e6 unique relations if that's any indication.
CADO often underestimates on bigger composites. Just let it finish, whatever time it takes.
If it fails at the last stages, please post the error message in the thread.
Some of us have experience resolving at least some of the common problems.
Max0526 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factoring 2ⁿ-2 equivalent to factoring 2ⁿ-1(I think) baih Miscellaneous Math 9 2020-09-21 07:11
OpenCL GPU P-1 Factoring and ECM Factoring xx005fs GPU Computing 3 2018-10-27 14:49

All times are UTC. The time now is 08:03.


Sat Jul 24 08:03:53 UTC 2021 up 1 day, 2:32, 1 user, load averages: 1.77, 1.61, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.