Factoring for a publication

[swishzzz]

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?

[EdH]

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

[Max0526]

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:

1) Please read this: https://mersenneforum.org/showpost.p...&postcount=228
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

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:

    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

that factors any or all polynomials below in terms of z?

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

[charybdis]

Running t50 on (6,-8) c179/snfs-229, will continue with t55 if no factors turn up.

[bsquared]

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:

P113 = 48859177299728793320715246065704744864214534488213548350308376738773226206199630803249626926079041962889965804681
P85 = 9056240418333107480731935683874341644262594549554962412771888829244066167328930970849

[Max0526]

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:

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.
Please let me know.

[bsquared]

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

[Max0526]

Originally Posted by bur

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!

[Max0526]

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

that factors any or all polynomials below in terms of z?

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:

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:

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 and for (8, -6):

1) on our elliptic curve , what are the constant values to produce rational solution(s) for z?

2) on a connected elliptic curve , what are the constant values to produce rational solution(s) for z?

[wblipp]

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:

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

[Max0526]

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!