mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-06-16, 22:45   #320
swishzzz
 
Jan 2012
Toronto, Canada

5·19 Posts
Default

Quote:
Originally Posted by firejuggler View Post
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?
swishzzz is offline   Reply With Quote
Old 2021-06-17, 11:19   #321
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3×372 Posts
Default

Quote:
Originally Posted by EdH View Post
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. . .
EdH is offline   Reply With Quote
Old 2021-06-17, 11:25   #322
Max0526
 
"Max"
Jun 2016
Toronto

2×3×151 Posts
Default

Quote:
Originally Posted by swishzzz View Post
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
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
Max0526 is offline   Reply With Quote
Old 2021-06-17, 12:38   #323
charybdis
 
charybdis's Avatar
 
Apr 2020

2·269 Posts
Default

Running t50 on (6,-8) c179/snfs-229, will continue with t55 if no factors turn up.
charybdis is offline   Reply With Quote
Old 2021-06-17, 13:54   #324
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×1,193 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
bsquared is offline   Reply With Quote
Old 2021-06-17, 14:20   #325
Max0526
 
"Max"
Jun 2016
Toronto

2×3×151 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
Please let me know.
Max0526 is offline   Reply With Quote
Old 2021-06-17, 14:23   #326
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×1,193 Posts
Default

Quote:
Originally Posted by Max0526 View Post
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).
bsquared is offline   Reply With Quote
Old 2021-06-17, 15:33   #327
Max0526
 
"Max"
Jun 2016
Toronto

38A16 Posts
Default

Quote:
Originally Posted by bur View Post
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!
Max0526 is offline   Reply With Quote
Old 2021-06-17, 16:00   #328
Max0526
 
"Max"
Jun 2016
Toronto

2×3×151 Posts
Default

Quote:
Originally Posted by Max0526 View Post
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
Max0526 is offline   Reply With Quote
Old 2021-06-17, 21:26   #329
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

236910 Posts
Default

Quote:
Originally Posted by Max0526 View Post
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
wblipp is offline   Reply With Quote
Old 2021-06-17, 21:37   #330
Max0526
 
"Max"
Jun 2016
Toronto

2·3·151 Posts
Default

Quote:
Originally Posted by wblipp View Post
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
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 01:44.


Sat Nov 27 01:44:12 UTC 2021 up 126 days, 20:13, 0 users, load averages: 1.63, 1.37, 1.21

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.