mersenneforum.org Factoring for a publication
 Register FAQ Search Today's Posts Mark Forums Read

2021-06-16, 22:45   #320
swishzzz

Jan 2012

5×19 Posts

Quote:
 Originally Posted by firejuggler hmmm those seem very hard to break.. Pushing ECM further will be very, very long and gnfs/snfs at those size isn't possible.Is there any 'hack" that can be attempted there? a large pm1? pp1?
I'd focus mainly on the lines that are < 3000 digits (roughly SNFS 250 quartic difficulty), as from what I understand partial factorizations of these points don't really help, so these are the only ones we can reasonably break aside from getting lucky with ECM. Don't think there are any more shortcuts as we've found all the algebraic factors @Max0526?

2021-06-17, 11:19   #321
EdH

"Ed Hall"
Dec 2009

10000011010012 Posts

Quote:
 Originally Posted by EdH Line 162: All small composites are fully factored, the c358 has been ECM'd to t50, the c328 is close to t50 and the c327 is yet to be ECM'd at all.
Line 162: All the composites that are left have been ECM'd to t50.

I'm going to play elsewhere for a while, but I'll keep an eye on this thread. . .

2021-06-17, 11:25   #322
Max0526

"Max"
Jun 2016
Toronto

919 Posts

Quote:
 Originally Posted by swishzzz I'd focus mainly on the lines that are < 3000 digits (roughly SNFS 250 quartic difficulty), as from what I understand partial factorizations of these points don't really help, so these are the only ones we can reasonably break aside from getting lucky with ECM. Don't think there are any more shortcuts as we've found all the algebraic factors @Max0526?
Although swishzzz is right (no more shortcuts are known to us now), I really want to believe that there are two more:

If we uncover the explicit expression for a = a(z), we won't need to calculate the GCDs anymore, we will know what they are -- they will be algebraic factors of the 6th polynomial on the list (a^4 - 24*a^3 + 152*a^2 - 336*a + 196) in terms of z.
Doesn't seem to be an extra shortcut yet, but at least we will understand why the GCDs are always there (nobody explained them yet, including the authors), and only for the 6th polynomial.
And that expression for a(z) may become the first shortcut I still hope for. If we substitute a(z) into
Code:
2*a^4 - 30*a^3 + 169*a^2 - 420*a + 392,
a^4 - 12*a^3 + 62*a^2 - 168*a + 196,
a^4 - 6*a^3 + 17*a^2 - 84*a + 196
some/all of them might factor in terms of z and it would break some/all of c200-c400 composites, ideally right in half.
For that to happen, sharing factors with other points (existence of large GCDs) is not a requirement. It just happened so that the factors of the 6th polynomial are shared, some/all others polynomials may have algebraic factorizations in terms of z but not share any numerical factors.

2) There are two connected elliptic curves. The first one produces the first 4 original SNFS polys (for the values a1, a2, a3, a4) to factor any composite by SNFS if we decide to do so. The second one _may_ produce 4 more (for the values a5, a6, a7, a8) for a particular composite we need to factor. Sometimes that composite to factor is shared by the two elliptic curves (and we have 8 original SNFS polys before the spin), and sometimes it is not (only 4 SNFS polys then).
The discriminant of the second elliptic curve is much harder to factor completely as it has a polynomial of degree 32 as one of the algebraic factors:
Code:
    x - 15,
x - 12,
x,
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,
x^32 - 192*x^31 - 43776*x^30 - 18800640*x^29 + 5503500288*x^28 + 273683349504*x^27 - 195095809916928*x^26 + 30785353346101248*x^25
- 2825577105735545856*x^24 + 176684772621207158784*x^23 - 8406169261059541893120*x^22 + 310105904650770600493056*x^21 -
9168826131738256943775744*x^20 + 222352073452169017323945984*x^19 - 3034551308521081654597386240*x^18 + 31148118165121605968147251200*x^17 -
232887992784886624221872271226*x^16 + 1184706194482578639874124008896*x^15 - 3607984676528931780768752872704*x^14 + 6019337787648898873971179520000*x^13 -
25447638730256460469701181440000*x^12 + 189226164149072887551728025600000*x^11 - 270078906310708200738914304000000*x^10 - 3101246803458128590189859098718208*x^9 +
12219551782715019853536631583745024*x^8 + 23360825043808908586558290230722560*x^7 - 159269714549351610655354977558528000*x^6 - 138653758460372775633724442812416000*x^5 +
1006003450171503521204261823959040000*x^4 + 1072258009790390526408430768128000000*x^3 - 1640779783029762601620535197696000000*x^2 -
1295352901691353352177566433280000000*x + 1214391379708526603038950722542207369
Nobody studied the GCDs for the points on the second elliptic curve yet. The points there may or may not share large factors. If they do, it may not be in the fashion (x-1, y), (x, y), (x+1, y) as it is on the first elliptic curve.
If the GCDs on the second curve exist, they may help us factor our numbers more efficiently, i.e., become the source to derive the second shortcut I am hoping for.

And another way to approach the second shortcut might be to ask: What is the expression for a = a(z), e.g., it may or may not be in the form
$a(z)=\frac{k_1z^2+k_2z+k_3}{z^2+k_4z+k_5}$
that factors any or all polynomials below in terms of z?
Code:
a^4 - 96*a^3 + 2232*a^2 - 17280*a + 32400,
a^4 - 24*a^3 + 288*a^2 - 4320*a + 32400,
a^4 + 192*a^3 - 5544*a^2 + 34560*a + 32400
It is also very important to remember that the numerical values for a on both elliptic curves are absolutely not random, they are strictly defined by the two generators of the elliptic curve and the plot point coordinates (n, m) [or (x, y) if you prefer].

Last fiddled with by Max0526 on 2021-06-17 at 12:06

 2021-06-17, 12:38 #323 charybdis     Apr 2020 25316 Posts Running t50 on (6,-8) c179/snfs-229, will continue with t55 if no factors turn up.
2021-06-17, 13:54   #324
bsquared

"Ben"
Feb 2007

358610 Posts

Quote:
 Originally Posted by bsquared Ok, I've done some test sieving and this looks doable with 14e. I was hoping to avoid 15e anyway for memory usage reasons.
Sieved 60-180MQ to find 260M raw relations, 222M unique. This produced an 11.9M matrix. Factors found on the first dependency:

Code:
P113 = 48859177299728793320715246065704744864214534488213548350308376738773226206199630803249626926079041962889965804681
P85 = 9056240418333107480731935683874341644262594549554962412771888829244066167328930970849

2021-06-17, 14:20   #325
Max0526

"Max"
Jun 2016
Toronto

919 Posts

Quote:
 Originally Posted by bsquared Sieved 60-180MQ to find 260M raw relations, 222M unique. This produced an 11.9M matrix. Factors found on the first dependency: Code: P113 = 48859177299728793320715246065704744864214534488213548350308376738773226206199630803249626926079041962889965804681 P85 = 9056240418333107480731935683874341644262594549554962412771888829244066167328930970849
Amazing, bsquared!
Do you need a set of spun polys for c203?
We have 8 SNFS polys to start with, so I have more spin options.
I should be able to make it SNFS 220, although right now it's SNFS 222/225.

2021-06-17, 14:23   #326
bsquared

"Ben"
Feb 2007

2·11·163 Posts

Quote:
 Originally Posted by Max0526 Amazing, bsquared! Do you need a set of spun polys for c203? We have 8 SNFS polys to start with, so I have more spin options. I should be able to make it SNFS 220, although right now it's SNFS 222/225. Please let me know.
Yes please, let's get the line finished. After that I think I will return to more ecm work (probably at a smaller scale).

2021-06-17, 15:33   #327
Max0526

"Max"
Jun 2016
Toronto

919 Posts

Quote:
 Originally Posted by bur Code: 763374743763081217914694138634486780344024237091539368674972788624046972741046710708718787293421106975357383724033172253608940141301420411687874833865804305796864727 = 187617592229624763212334360684243158531010549296799633618128462377 * 4068780196415635313930042276676522917113246118987972266171210051365033359610138025637240809271735551 Both factors are not unique but to the power of 3 for the C2372, would it be worthwhile to test all previously known factors if they occur more than once? http://factordb.com/index.php?id=1100000002599665468
An interesting fact for today:
If a composite that we are trying to factor is cubed, then it is (most probably) not shared with the related second elliptic curve, and only 4 original SNFS polys are available (for a1-a4) before we try to spin.
If a composite is not cubed, then it is shared with the second elliptic curve, and 8 original SNFS polys are available (for a1-a8).
Again, bur, you had one tough composite to factor!

2021-06-17, 16:00   #328
Max0526

"Max"
Jun 2016
Toronto

91910 Posts

Quote:
 Originally Posted by Max0526 Nobody studied the GCDs for the points on the second elliptic curve yet. The points there may or may not share large factors. If they do, it may not be in the fashion (x-1, y), (x, y), (x+1, y) as it is on the first elliptic curve. If the GCDs on the second curve exist, they may help us factor our numbers more efficiently, i.e., become the source to derive the second shortcut I am hoping for. And another way to approach the second shortcut might be to ask: What is the expression for a = a(z), e.g., it may or may not be in the form $a(z)=\frac{k_1z^2+k_2z+k_3}{z^2+k_4z+k_5}$ that factors any or all polynomials below in terms of z? Code: a^4 - 96*a^3 + 2232*a^2 - 17280*a + 32400, a^4 - 24*a^3 + 288*a^2 - 4320*a + 32400, a^4 + 192*a^3 - 5544*a^2 + 34560*a + 32400 It is also very important to remember that the numerical values for a on both elliptic curves are absolutely not random, they are strictly defined by the two generators of the elliptic curve and the plot point coordinates (n, m) [or (x, y) if you prefer].
Well, I looked at the GCDs on the second curve. Unfortunately, they give us no new information about our composites.
But my question about a = a(z) still stays: What could a(z) be to factor at least one of the following polynomials in terms of z?

First/our elliptic curve:
Code:
a^2 - 12*a + 28,
a^2 - 6*a + 7,
a^4 - 24*a^3 + 152*a^2 - 336*a + 196,
2*a^4 - 30*a^3 + 169*a^2 - 420*a + 392,
a^4 - 12*a^3 + 62*a^2 - 168*a + 196,
a^4 - 6*a^3 + 17*a^2 - 84*a + 196
Second/connected elliptic curve:
Code:
a^4 - 96*a^3 + 2232*a^2 - 17280*a + 32400,
a^4 - 24*a^3 + 288*a^2 - 4320*a + 32400,
a^4 + 192*a^3 - 5544*a^2 + 34560*a + 32400
Or approaching the same question from a different perspective:

given, e.g., that $a(z)=\frac{k_1z^2+k_2z+k_3}{z^2+k_4z+k_5}$ and for (8, -6):

1) on our elliptic curve $a = a_1 = \frac{152522491604374689386753539917927758022599341586165}{84416361570423310103196284324834263821616828170726}$, what are the constant values $k_1-k_5$ to produce rational solution(s) for z?

2) on a connected elliptic curve $a = a_5 = \frac{622543102197492153444365224810446476802484223491756}{37709095648854857100855573096805182984297422731765}$, what are the constant values $k_1-k_5$ to produce rational solution(s) for z?

Last fiddled with by Max0526 on 2021-06-17 at 16:22

2021-06-17, 21:26   #329
wblipp

"William"
May 2003
New Haven

45018 Posts

Quote:
 Originally Posted by Max0526 What could a(z) be to factor at least one of the following polynomials in terms of z? First/our elliptic curve: Code: a^2 - 12*a + 28
I'm skimming, so this might not be what you want. But in a few minutes PARI/GP showed many quadratic polynomials that factor this, including

a(z) = z^2 -z -2
a(z) = 7z^2 -5z +4

2021-06-17, 21:37   #330
Max0526

"Max"
Jun 2016
Toronto

919 Posts

Quote:
 Originally Posted by wblipp I'm skimming, so this might not be what you want. But in a few minutes PARI/GP showed many quadratic polynomials that factor this, including a(z) = z^2 -z -2 a(z) = 7z^2 -5z +4
Thank you, wblipp!
The problem here is that we want:
1) create a formula for a=a(z) that factors at least one of our polynomials above in terms of z;
_and_
2) some _rational_ z in that formula to produce our given rational a1 or a5.
This rational z requirement slims our choices down almost to zero.
I am still not giving up on finding that formula!

Last fiddled with by Max0526 on 2021-06-17 at 21:39

 Similar Threads Thread Thread Starter Forum Replies Last Post baih Miscellaneous Math 9 2020-09-21 07:11 xx005fs GPU Computing 3 2018-10-27 14:49

All times are UTC. The time now is 00:14.

Fri Jan 28 00:14:42 UTC 2022 up 188 days, 18:43, 2 users, load averages: 2.26, 1.68, 1.41