mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Factoring for a publication (https://www.mersenneforum.org/showthread.php?t=26875)

Max0526 2021-06-05 01:21

Factoring for a publication
 
Our respected colleagues have submitted a paper on elliptic curves: [url]https://web.math.pmf.unizg.hr/~duje/pdf/DKP-Z8Z2Z6.pdf[/url] (the uncorrected version on arXiv : [url]https://arxiv.org/abs/2105.06215[/url])
The authors experienced factoring bottleneck while building the three plots on p. 17-19: "The bottleneck of the root number computation is the factorization of the discriminant".
I volunteered to help and had a lot of success improving plot 2. Now I am working on adding points to plot 3.
I summarized my efforts so far and all the necessary information in the sheet: [url]https://tinyurl.com/x5fcvknc[/url]
[COLOR="Red"][FONT="Arial Black"]Mod untiny url[/FONT][/COLOR] [C]https://docs.google.com/spreadsheets/d/1G-FaJRjNMf9blg45skDnryMiZ1bHkHvMvirERPrz9Jc/edit#gid=0[/C]

Does anybody have spare cycles to help me and speed up the process?

The discriminants can be easily generated by Magma Calculator ([url]http://magma.maths.usyd.edu.au/calc/[/url]) by the script: [url]https://tinyurl.com/ytjr542p[/url]. [C]https://docs.google.com/document/d/16hnhZ6NlpQ8qFvieiDXthikh3nNakH8BHXgMG8eblBc/edit[/C]
The output also includes a number of SNFS cofactors.
The factors can be submitted directly to FactorDB (direct links are provided in the sheet), I am retrieving them from there to add to the Magma code to recreate the updated plot.

The general ideas are:
1) to extend an existing Figure 3 plot (p. 19), ideally keeping it roughly rectangular, and focusing on a half-plot for x >= 1, the left half-plot is built using the existing symmetry;
2) to reach ~250 plot points at the end (157 points now);
3) to use ECM, SIQS, etc. (yafu's sequence of test works really well so far) rather than NFS;
4) to factor everything up to SNFS 170;
5) to avoid GNFS (if the Magma code is not descriptive enough, I'll help you create some good SNFS poly(s) for a composite, the discriminants have many suitable cofactors to play with).

So far I finished the layout for stage 6 (x = 6 or y = 6 or y = -6), and spiral out clockwise in the consecutive stages.

You should be able to comment directly in the sheet. You are welcome to add any ideas to the thread or send me a PM.

Thank you so much in advance! Promise to always try spinning your GNFS polys. :-)

wombatman 2021-06-05 03:52

I can do the c97 in (1,-7), [STRIKE]the c94 in (7, -7)[/STRIKE], the c116 in (7, -4). Probably others depending on what's still available once I finish these.

Max0526 2021-06-05 04:25

[QUOTE=wombatman;579982]I can do the c97 in (1,-7), [STRIKE]the c94 in (7, -7)[/STRIKE], the c116 in (7, -4). Probably others depending on what's still available once I finish these.[/QUOTE]
Thank you! I updated the sheet.

LaurV 2021-06-05 04:52

I took the first non-green for a spin (line 28 in the excel sheet). The [U]three[/U] composites will be done today.
Edit: I said three :razz:

Max0526 2021-06-05 05:19

[QUOTE=LaurV;579984]I took the first non-green for a spin (line 28 in the excel sheet). The three composites will be done today.[/QUOTE]

Thank you! c90 is already done. I updated the sheet.

wombatman 2021-06-05 05:20

Doing the C111 in (7,7).

Max0526 2021-06-05 05:36

[QUOTE=wombatman;579986]Doing the C111 in (7,7).[/QUOTE]

Thank you! Updated.

LaurV 2021-06-05 06:33

Edit2: the 117 seems to be already a prime, so only 2 to factor for me. Almost done.
Edit3: ecm hit for 119. So the most difficult proved to be the c113 :lol:
C'mon man, give us some serious work to do.. :razz:

LaurV 2021-06-05 07:16

Took lines 61 and 62 in the excel sheet.

bur 2021-06-05 07:30

I'd gladly do some factoring, but admittedly I'm not 100% clear on what to do...


Do I just factor the numbers from your sheet? What about the magma script, is it used on the prime factors after factorization?


I could start with the C127 & C139 (5,-6).

LaurV 2021-06-05 08:02

Took lines 63 and 64 in the excel sheet.

fivemack 2021-06-05 08:09

I'll take the two (5,-6) ones to start with; this is a research direction I've been interested in since my PhD in early 2000s.

Could you also send me the SNFS polynomial for (3,-7) ?

I am also throwing a core-month of ECM at the (6,-7) cofactors

unconnected 2021-06-05 08:13

Taking (4,-7) and (2,-7). Not sure about GNFS on 15x, but ECM at least.

kar_bon 2021-06-05 08:32

Line 53: (4, -7):
c114: P29 * P40 * P46
c117: P28 * P35 * P55
c151: none found
c156: P24 * C133

fivemack 2021-06-05 08:42

C156 from (6,-7) completed by ECM (p27, p39)

Taken a P25 out of the C152 and a P30 out of the C187

PS: also two P36 out of the C187, which is complete

fivemack 2021-06-05 10:24

Taking the cofactors from (7,-7); initially a day of ECM on a dozen cores

xilman 2021-06-05 10:48

[QUOTE=Max0526;579980]
You should be able to comment directly in the sheet. You are welcome to add any ideas to the thread or send me a PM.

Thank you so much in advance! Promise to always try spinning your GNFS polys. :-)[/QUOTE]I'm willing to throw in some cycles but it is not clear how up to date is the booking list in the spreadsheet .

Could you create a post which contains the current state of play and to encourage contributors to keep it updated?

Thanks.

LaurV 2021-06-05 11:25

Took line 65. Everything else is done, gov'nor. Then I will wait until you wake up and update the chart (you are probably sleeping this time, or enjoying your weekend), before I be doing more work (if anything left...), because right now all these good people here confused me and I don't know what's taken and what's not :redface:

EdH 2021-06-05 12:46

Not sure I fully understand the ECM/SIQS first request.How would you know?

If "ready for NFS" means they are free, I can run SIQS against the composites in lines 60, 74 and 75.

RichD 2021-06-05 13:01

[QUOTE=EdH;580011]If "ready for NFS" means they are free, I can run SIQS against the composites in lines 60, 74 and 75.[/QUOTE]

I'm currently running line 74.

Max0526 2021-06-05 13:06

[QUOTE=EdH;580011]Not sure I fully understand the ECM/SIQS first request.How would you know?

If "ready for NFS" means they are free, I can run SIQS against the composites in lines 60, 74 and 75.[/QUOTE]

Yes, "ready for NFS" means they were free when I marked them.
RichD is currently on line 74 -- (8, -2).

Max0526 2021-06-05 13:08

[QUOTE=RichD;580014]I'm currently running line 74.[/QUOTE]
Line 74 booked for RichD in the sheet.

EdH 2021-06-05 13:12

OK! I've commented about running SIQS on lines 60 and 75. I will run those in a little while, if no one else has claimed them.

Max0526 2021-06-05 13:13

[QUOTE=bur;579995]I'd gladly do some factoring, but admittedly I'm not 100% clear on what to do...


Do I just factor the numbers from your sheet? What about the magma script, is it used on the prime factors after factorization?


I could start with the C127 & C139 (5,-6).[/QUOTE]

Yes, just factors the numbers from the sheet. The posted Magma script is for generating the initial records on factordb, and also for creating suitable SNFS polys.

That C127 is already factored by fivemack. I am writing a post on how to generate SNFS polys with the C139 as an example.

Max0526 2021-06-05 13:15

[QUOTE=EdH;580018]OK! I've commented about running SIQS on lines 60 and 75. I will run those in a little while, if no one else has claimed them.[/QUOTE]
Updated in the sheet, thank you!

fivemack 2021-06-05 13:18

(5,-6) finished - the C139 has a P26 by ecm

Max0526 2021-06-05 13:46

[QUOTE=fivemack;579998]I'll take the two (5,-6) ones to start with; this is a research direction I've been interested in since my PhD in early 2000s.

Could you also send me the SNFS polynomial for (3,-7) ?

I am also throwing a core-month of ECM at the (6,-7) cofactors[/QUOTE]

This is how to generate the SNFS polys from the attached Magma script, c126 / snfs144 from (3, -7) is used as an example.

Edit the script to say [3, -7][code]
m := [3, 7]; ////////////////////// edit the plot point here /////////////////////
[/code]
and uncomment the ouput for a[code]
a; " "; // uncomment this to get Y0 and Y1 for the SNFS poly, if necessary //
[/code]
Run the script in Magma Calculator ([url]http://magma.maths.usyd.edu.au/calc/[/url]).
Take the first value from the output (a-value) to produce Y0 and Y1 --> a = -Y0/Y1[code]
a = 2625497112988581533564774729619428753/581569296010330112388333512013248048
[/code]
[code]
Y0: -2625497112988581533564774729619428753
Y1: 581569296010330112388333512013248048
[/code]
Now look through the numerators at the bottom of the output and find the one that has c126 as a cofactor: [url]http://factordb.com/index.php?id=1100000002597811273[/url]
It was the second numerator from the top (ignore or comment all denominators in the output for now), generated by the second degree 4 poly on the list[code]
x^4 - 24*x^3 + 152*x^2 - 336*x + 196,
2*x^4 - 30*x^3 + 169*x^2 - 420*x + 196*2, <-- this poly
x^4 - 12*x^3 + 62*x^2 - 168*x + 196,
x^4 - 6*x^3 + 17*x^2 - 84*x + 196
[/code]
which creates the block for c0-c4[code]
c0: 392
c1: -420
c2: 169
c3: -30
c4: 2[/code]
Get these 7 lines (c0-c4, Y0, Y1) through the [url]http://cownoise.com/[/url] / Calculators / Optimal Skew to produce the values for the skew and E[code]
skew: 3.99192
# E = 2.36121084e-09
[/code]
Add the n-value (c126) at the top of the poly file. The first one is ready! (There will be a second one too, for a different a-value [Y0, Y1, rational side] but the same c0-c4 [algebraic side], will explain it in a bit, need to derive the formula first).
[code]
n: 665346346066322380069828663638962277265700573377334838072153685493190817971091678723311076185411447868488601711575118621654489
skew: 3.99192
c0: 392
c1: -420
c2: 169
c3: -30
c4: 2
Y0: -2625497112988581533564774729619428753
Y1: 581569296010330112388333512013248048
# E = 2.36121084e-09
[/code]

Max0526 2021-06-05 13:48

[QUOTE=fivemack;580021](5,-6) finished - the C139 has a P26 by ecm[/QUOTE]

Could you please post a P26 to FactorDB for this C139?
EDIT: Ignore it please, marked as done for fivemack.

EdH 2021-06-05 14:10

Line 60 is completed by SIQS and the db updated. What else may be needed?

Max0526 2021-06-05 14:11

[QUOTE=fivemack;579998]I'll take the two (5,-6) ones to start with; this is a research direction I've been interested in since my PhD in early 2000s.

Could you also send me the SNFS polynomial for (3,-7) ?

I am also throwing a core-month of ECM at the (6,-7) cofactors[/QUOTE]

The second SNFS poly is created by calculating[code]
a[SUB]2[/SUB] = 7*(a[SUB]1[/SUB]-4)/(2*a[SUB]1[/SUB]-7) = 299219928947261084011440681566436561/168572736272121754344459267878017310,
where a[SUB]1[/SUB] = 2625497112988581533564774729619428753/581569296010330112388333512013248048[/code] from the Magma script. It gives us[code]
n: 665346346066322380069828663638962277265700573377334838072153685493190817971091678723311076185411447868488601711575118621654489
skew: 3.01798 # different for a2
c0: 392
c1: -420
c2: 169
c3: -30
c4: 2
Y0: -299219928947261084011440681566436561 # for a2
Y1: 168572736272121754344459267878017310 # for a2
# E = 3.14999605e-09 # different and _better_ poly for a2 !!!
[/code]
There should be a[SUB]3[/SUB] and a[SUB]4[/SUB] values, but I didn't get to them yet. If/when I do, I'll post the additions.
Then there could be spin of course, and I am working on it too.

Max0526 2021-06-05 14:19

[QUOTE=EdH;580024]Line 60 is completed by SIQS and the db updated. What else may be needed?[/QUOTE]

I updated the sheet, thank you! Are you up for the c93 from here? [url]http://factordb.com/index.php?id=1100000002598197699[/url]

EdH 2021-06-05 14:23

[QUOTE=Max0526;580027]I updated the sheet, thank you! Are you up for the c93 from here? [URL]http://factordb.com/index.php?id=1100000002598197699[/URL][/QUOTE]
Sure! But, I might wait for the LA square root of a different project to complete. . .

Max0526 2021-06-05 14:40

[QUOTE=EdH;580028]Sure! But, I might wait for the LA square root of a different project to complete. . .[/QUOTE]

The c93 is done now.

EdH 2021-06-05 14:44

[QUOTE=Max0526;580030]The c93 is done now.[/QUOTE]
I just ran it, too. The c115 will be a while running it with SIQS

Max0526 2021-06-05 15:06

[QUOTE=EdH;580031]I just ran it, too. The c115 will be a while running it with SIQS[/QUOTE]

Please don't run it with SIQS, it would take too long.
If ECM is finished by say yafu, I will provide suitable SNFS polys (let me know). Or you can create them yourself:
1) [url]https://mersenneforum.org/showpost.php?p=580022&postcount=27[/url]
2) [url]https://mersenneforum.org/showpost.php?p=580025&postcount=30[/url]
SNFS will be faster. Worst case scenario, GNFS should also be faster than SIQS as SIQS/GNFS crossover is at 95 digits.

EdH 2021-06-05 15:14

[QUOTE=Max0526;580033]Please don't run it with SIQS, it would take too long.
If ECM is finished by say yafu, I will provide suitable SNFS polys (let me know). Or you can create them yourself:
1) [URL]https://mersenneforum.org/showpost.php?p=580022&postcount=27[/URL]
2) [URL]https://mersenneforum.org/showpost.php?p=580025&postcount=30[/URL]
SNFS will be faster. Worst case scenario, GNFS should also be faster than SIQS as SIQS/GNFS crossover is at 95 digits.[/QUOTE]
Part of my confusion from the first message, but I can run the c115 via SNFS. Do you require my poly, etc. for your records? I plan to follow my "How I. . ." procedure. It gives me a chance to test it to see if it still works.

Max0526 2021-06-05 15:21

[QUOTE=EdH;580035]Part of my confusion from the first message, but I can run the c115 via SNFS. Do you require my poly, etc. for your records? I plan to follow my "How I. . ." procedure. It gives me a chance to test it to see if it still works.[/QUOTE]

Thank you! Please do run it with SNFS. I am listing two SNFS polys for your reference, as clarification / another example / check for the provided instructions. Please let me know if something is off.[code]
(8, -3) c115/snfs125 -- poly 1
n: 1220320980954814707143144710823160347283886398771046495382862573956880261463684223833837644743260069843547863559837
# a = 33343340387506348582700073930446/8142876843657119169240758930211 (from Magma script)
Y0: -33343340387506348582700073930446
Y1: 8142876843657119169240758930211

# poly 2*x^4 - 30*x^3 + 169*x^2 - 420*x + 196*2
c0: 392
c1: -420
c2: 169
c3: -30
c4: 2

skew: 3.85629
# E = 2.17807714e-08

-------------

(8, -3) c115/snfs125 -- poly 2
n: 1220320980954814707143144710823160347283886398771046495382862573956880261463684223833837644743260069843547863559837
# a = 771833012877871905737038209602/1383791838487551854387833621345 (a2 from a1 by the formula)
Y0: -771833012877871905737038209602
Y1: 1383791838487551854387833621345

# poly 2*x^4 - 30*x^3 + 169*x^2 - 420*x + 196*2
c0: 392
c1: -420
c2: 169
c3: -30
c4: 2

skew: 2.72600
# E = 3.07701728e-08 <-- better poly[/code]

Max0526 2021-06-05 15:22

(2, -7) -- c128 / snfs135 -- for RichD
 
Two polys could be created fast:[code]
# (2, -7) c128 / snfs135 -- poly 1
n: 13545157433812263305932561285949223164675571885109318536636946492968268605841161606907230625598077190290088696584122133954102201
# a = 9427184341737733068556338763355754/2503345813299831306061017647267053
Y0: -9427184341737733068556338763355754
Y1: 2503345813299831306061017647267053

# poly 2*x^4 - 30*x^3 + 169*x^2 - 420*x + 196*2
c0: 392
c1: -420
c2: 169
c3: -30
c4: 2

skew: 3.74992
# E = 7.18436303e-09

----------

# (2, -7) c128 / snfs135 -- poly 2
n: 13545157433812263305932561285949223164675571885109318536636946492968268605841161606907230625598077190290088696584122133954102201
# a = -586198911461592155687731825712458/190135427196663856383650570834591
Y0: 586198911461592155687731825712458
Y1: 190135427196663856383650570834591

# poly 2*x^4 - 30*x^3 + 169*x^2 - 420*x + 196*2
c0: 392
c1: -420
c2: 169
c3: -30
c4: 2

skew: 3.57621
# E = 1.07002181e-08 <-- better poly
[/code]
Please let me know if something is off.

LaurV 2021-06-05 15:27

Taking line 67 (8, 8). The c164 may take a while, I will let it run in 18 cores over the weekend.

Max0526 2021-06-05 15:51

[QUOTE=LaurV;580038]Taking line 67 (8, 8). The c164 may take a while, I will let it run in 18 cores over the weekend.[/QUOTE]

Do you need 2 SNFS polys for c164? Thank you!

LaurV 2021-06-05 16:04

Any chance you spin a poly for the c164?
Edit : crosspost, it would be wonderful to get a poly, yeah! :lol:

Max0526 2021-06-05 16:13

(8, 7) -- c114 / snfs144 polys
 
[code]
(8, 7) c114 / snfs144 --> poly 1
n: 403053942750100765612835430129070990860672572154597091809648481800007541918692133541634956284146445458267224212474973192813107505122691955583276
# a = 5269395574285951421583034305968188034/1261226192083896254900402171166149841
Y0: -5269395574285951421583034305968188034
Y1: 1261226192083896254900402171166149841

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 3.90710
# E = 1.95237227e-09

-----------------------

(8, 7) c114 / snfs144 --> poly 2
n: 403053942750100765612835430129070990860672572154597091809648481800007541918692133541634956284146445458267224212474973192813107505122691955583276
# a = 224490805950366401981425621303588670/244315400569232722694750487681903883
Y0: -224490805950366401981425621303588670
Y1: 244315400569232722694750487681903883

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 2.39109
# E = 2.83222224e-09 <-- much better poly
[/code]
Please let me know if anything is off.

RichD 2021-06-05 16:34

Need poly for c131 on line 76 please.

Max0526 2021-06-05 17:21

[QUOTE=RichD;580044]Need poly for c131 on line 76 please.[/QUOTE]

[code](8, -4) c131 / snfs144 --> poly 1
n: 65588592210776870347413125029085274014037594414126884476730933544637031079031153548090071521389555715058367902976743141228853001561
# a = 2014715236628141843329312711994059321/279728276467239112968579776696719488
Y0: -2014715236628141843329312711994059321
Y1: 279728276467239112968579776696719488

# poly 2*x^4 - 30*x^3 + 169*x^2 - 420*x + 196*2
c0: 392
c1: -420
c2: 169
c3: -30
c4: 2

skew: 4.55314
# E = 2.49633965e-09 <-- better poly

-----------------------

(8, -4) c131 / snfs144 --> poly 2
n: 65588592210776870347413125029085274014037594414126884476730933544637031079031153548090071521389555715058367902976743141228853001561
# a = 6270614915314297740184955236450269583/2071332537985609895878566987111082226
Y0: -6270614915314297740184955236450269583
Y1: 2071332537985609895878566987111082226

# poly 2*x^4 - 30*x^3 + 169*x^2 - 420*x + 196*2
c0: 392
c1: -420
c2: 169
c3: -30
c4: 2

skew: 3.47809
# E = 1.89785838e-09[/code]

Max0526 2021-06-05 17:29

[QUOTE=LaurV;580041]Any chance you spin a poly for the c164?
Edit : crosspost, it would be wonderful to get a poly, yeah! :lol:[/QUOTE]
[code](8, 8) c164 / snfs170 --> poly 1
n: 27549552870024775309360384412644717396669398352814962054008616304874281405758638638960912648483669596008669328950259534837026658885477281773175396278146092059822187656639
# a = 3301440445505588929477052131630608105022609/442675858149281183384208121008685306143552
Y0: -3301440445505588929477052131630608105022609
Y1: 442675858149281183384208121008685306143552

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 4.78932
# E = 1.20623162e-10 <-- better poly

-----------------------

(8, 8) c164 / snfs170 --> poly 2
n: 27549552870024775309360384412644717396669398352814962054008616304874281405758638638960912648483669596008669328950259534837026658885477281773175396278146092059822187656639
# a = 10715159090359249371581537533171068163138807/3504149883966209575264647416200419067040354
Y0: -10715159090359249371581537533171068163138807
Y1: 3504149883966209575264647416200419067040354

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 3.46114
# E = 8.94678578e-11[/code]

unconnected 2021-06-05 17:33

I tried to generate poly file for c133 from (4, -7) but something went wrong:
[CODE]n: 2749457614794647262361879796428445127945722605794673602589457472453080969513005299239408449216604361609226167561990719027188445142241
skew: 3.43469
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1
Y0: -5554601221033173772912866296770856709982
Y1: 1863589942627684233365918164244430623163
[/CODE]
Got an error from factMsieve script:
[CODE]-> Warning: evaluated polynomial value -141148146159378749246764684024815706538491155185674289109980978257351523181783126120960791861967660218875168856495053062518077245875473744121445687183090267116 is negative or zero.
-> This is at least a little strange.
-> Error: evaluated polynomial value -141148146159378749246764684024815706538491155185674289109980978257351523181783126120960791861967660218875168856495053062518077245875473744121445687183090267116 is not a multiple of n!
[/CODE]Max, please help with the poly.

Max0526 2021-06-05 17:45

[QUOTE=unconnected;580049]I tried to generate poly file for c133 from (4, -7) but something went wrong:
[CODE]n: 2749457614794647262361879796428445127945722605794673602589457472453080969513005299239408449216604361609226167561990719027188445142241
skew: 3.43469
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1
Y0: -5554601221033173772912866296770856709982
Y1: 1863589942627684233365918164244430623163
[/CODE]
Got an error from factMsieve script:
[CODE]-> Warning: evaluated polynomial value -141148146159378749246764684024815706538491155185674289109980978257351523181783126120960791861967660218875168856495053062518077245875473744121445687183090267116 is negative or zero.
-> This is at least a little strange.
-> Error: evaluated polynomial value -141148146159378749246764684024815706538491155185674289109980978257351523181783126120960791861967660218875168856495053062518077245875473744121445687183090267116 is not a multiple of n!
[/CODE]Max, please help with the poly.[/QUOTE]
C133 is done: [url]http://factordb.com/index.php?id=1100000002597842602[/url]

EdH 2021-06-05 17:54

Ok, I'm at a loss! I ran CADO-NFS with the first poly and it crashed during the Square Root phase. So, I ran Msieve on the relations and it gave up, too:[code]Sat Jun 5 13:36:01 2021 lanczos halted after 3190 iterations (dim = 201552)
Sat Jun 5 13:36:01 2021 lanczos error: only trivial dependencies found[/code]I've started over from scratch with the second poly (which scored better, anyway).

LaurV 2021-06-05 17:58

[QUOTE=Max0526;580048][code](8, 8) c164 / snfs170

[/code][/QUOTE]
Thanks, the c113 is done, and c142 survived a [STRIKE]t45[/STRIKE]t47. It will take yafu about 3 hours and half in 18 cores to get a poly. So, you may as well post one for the c142 too. :smile:
The c164 is in ecm, about one hour or two to go.

EdH 2021-06-05 18:16

[QUOTE=EdH;580055]I've started over from scratch with the second poly (which scored better, anyway).[/QUOTE]That didn't work, either! Apparently, I'm experiencing a "degree 4" problem as referenced in the CADO-NFS README.

EdH 2021-06-05 20:09

[QUOTE=EdH;580060]That didn't work, either! Apparently, I'm experiencing a "degree 4" problem as referenced in the CADO-NFS README.[/QUOTE]
I couldn't get it done via SNFS, so I went back to ECM (B1=43000000):[code]# 195: N = 1220320980954814707143144710823160347283886398771046495382862573956880261463684223833837644743260069843547863559837
# 195: B1 = 43000000
# 195: #curves = 1960
# 019: curve 0 found factor 34840634210713925164876991440244213 using sigma -1:2498375964
# 066: curve 0 found factor 34840634210713925164876991440244213 using sigma -1:2520929826
# 196 curves done (10.0%)
Results: 1220320980954814707143144710823160347283886398771046495382862573956880261463684223833837644743260069843547863559837 = 35025796992511431933842456763296474140730986971108376518054629586885193816771849 * 34840634210713925164876991440244213[/code]

Brownfox 2021-06-05 21:18

I will factor the composites for (4, -8) : line 84

unconnected 2021-06-05 22:38

c123 from (2, -7) and c151 from (4, -7) are done.

Max0526 2021-06-06 01:34

[QUOTE=EdH;580068]I couldn't get it done via SNFS, so I went back to ECM (B1=43000000):[code]# 195: N = 1220320980954814707143144710823160347283886398771046495382862573956880261463684223833837644743260069843547863559837
# 195: B1 = 43000000
# 195: #curves = 1960
# 019: curve 0 found factor 34840634210713925164876991440244213 using sigma -1:2498375964
# 066: curve 0 found factor 34840634210713925164876991440244213 using sigma -1:2520929826
# 196 curves done (10.0%)
Results: 1220320980954814707143144710823160347283886398771046495382862573956880261463684223833837644743260069843547863559837 = 35025796992511431933842456763296474140730986971108376518054629586885193816771849 * 34840634210713925164876991440244213[/code][/QUOTE]


What a story! Thank you for not giving up!
I had the same problem with CADO while working on Figure 2 plot for the same paper. When SNFS 170 failed in the root phase, I transferred all the raw relations to msieve and it finished the job. Guess it was lucky.

Max0526 2021-06-06 02:02

[QUOTE=LaurV;580057]Thanks, the c113 is done, and c142 survived a [STRIKE]t45[/STRIKE]t47. It will take yafu about 3 hours and half in 18 cores to get a poly. So, you may as well post one for the c142 too. :smile:
The c164 is in ecm, about one hour or two to go.[/QUOTE]


[code]
(8, 8) c142 / snfs170 --> poly 1
n: 8634770279589004036827356194912393863312537850732467598999417776716562536604195298669883428901982312090588445191732185912646256178539679210299
# a = 3301440445505588929477052131630608105022609/442675858149281183384208121008685306143552
Y0: -3301440445505588929477052131630608105022609
Y1: 442675858149281183384208121008685306143552

# poly x^4 - 6*x^3 + 17*x^2 - 84*x + 196
c0: 196
c1: -84
c2: 17
c3: -6
c4: 1

skew: 4.62503
# E = 1.35994355e-10 <-- better poly

-----------------------

(8, 8) c142 / snfs170 --> poly 2
n: 8634770279589004036827356194912393863312537850732467598999417776716562536604195298669883428901982312090588445191732185912646256178539679210299
# a = 10715159090359249371581537533171068163138807/3504149883966209575264647416200419067040354
Y0: -10715159090359249371581537533171068163138807
Y1: 3504149883966209575264647416200419067040354

# poly x^4 - 6*x^3 + 17*x^2 - 84*x + 196
c0: 196
c1: -84
c2: 17
c3: -6
c4: 1

skew: 3.49196
# E = 1.00951550e-10[/code]

Max0526 2021-06-06 03:25

@Greg:

> Wait...these are SNFS 214's! Yikes.

> We could put these larger ones in the NFS@Home 14e queue if you want. They would likely take a few days to run.

Thank you so much! But please don't.
The goal was not to overload anybody with anything over SNFS 170 (roughly an overnight run).
I am also creating the next stage(s) with more (hopefully) smaller unfactored numbers. On the plot, a point is a point. We'll get more points by factoring smaller composites (I mean or not, because they all will be above SNFS 170, then we'll stop).
Thank you again for the offer!

LaurV 2021-06-06 05:05

[QUOTE=Max0526;580104][code]
(8, 8) c142 / snfs170 --> [/code][/QUOTE]
Thanks.Let's have a morning cofee and start some SNFS (people in Asia sleep from 3:30 AM to 11:30 AM local time, on Sunday :razz:)
Edit: did I say a coffee?

Max0526 2021-06-06 05:14

[QUOTE=LaurV;580108]Thanks.Let's have a morning cofee and start some SNFS (people in Asia sleep from 3:30 AM to 11:30 AM local time, on Sunday :razz:)
Edit: did I say a coffee?[/QUOTE]
I am heading to bed soon. Do you need any SNFS polys? Stage 9 is open too.

LaurV 2021-06-06 05:40

Nope, thanks. Let me digest what I have swallowed first :smile:
It will take a while.

Have a nice sleep, don't let the bedbugs byte... :razz:

bur 2021-06-06 06:50

Please post an SNFS poly for row 92.


Can all these numbers be factored via SNFS?

LaurV 2021-06-06 07:48

Stupid noob question: with those snfs polis, do I have to sieve rational side? :innocent: :noob:

(phew! I edited former poster's post by mistake, replacing his question with mine, noob-noob! luckily I had it in the history so I could restore it! sorry! and the answer for his question above is yes, if you read the paper, they come from simple function therefore a snfs poly can be generated for them, however sometimes the gnfs is faster, but here people with more knowledge/experience should weight in - or not)

bur 2021-06-06 08:32

Thanks, LaurV, I can technically do the "if you read the paper", but I doubt I'd come to the conclusion that they all have an SNFS poly...


And Max, can you please also post polys for the c134 and c141 of row 96? No ECM factors for B1=3e6.

Max0526 2021-06-06 13:37

[QUOTE=bur;580116]Please post an SNFS poly for row 92.


Can all these numbers be factored via SNFS?[/QUOTE]

[code]
(1, -8) c140 / snfs160 --> poly 1
n: 52241534590213705608428031799544177114898332495868045475031061652146772820386260197176363790731631003711544201169238012854931521936237993439
# a = 5043861836862596749419584668138860133250/4611493799370558561548601217536824836609
Y0: -5043861836862596749419584668138860133250
Y1: 4611493799370558561548601217536824836609

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 2.48522
# E = 3.71562975e-10 <-- a much better poly

-----------------------------------------------

(1, -8) c140 / snfs160 --> poly 2
n: 52241534590213705608428031799544177114898332495868045475031061652146772820386260197176363790731631003711544201169238012854931521936237993439
# a = 93814793524337462477423741414059074492302/22192732921868716432001039186480053589763
Y0: -93814793524337462477423741414059074492302
Y1: 22192732921868716432001039186480053589763

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 2.27523
# E = 1.93059110e-10
[/code]

Max0526 2021-06-06 13:59

[QUOTE=bur;580116]Can all these numbers be factored via SNFS?[/QUOTE]
Yes. SNFS polys exist for all of them.The first two can be generated from the provided Magma script by one of the following[code]
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
[/code]
for x = a, the a-value calculated for the point (n, m), where
[code]
a = -Y0/Y1
[/code]
so Y0 and Y1 are negative numerator and positive denominator of a.
Y0 and Y1 for the second poly are from[code]
x = a2 = 7*(a-4)/(2*a-7)
[/code]
There should be at least two more choices for the a-value (a3 and a4) and I am working on finding them.

RichD 2021-06-06 14:08

Need poly for c125 (formerly c133) on line 107 please.

Max0526 2021-06-06 14:50

[QUOTE=RichD;580137]Need poly for c125 (formerly c133) on line 107 please.[/QUOTE]
For c115 (still too late, you are at c85 now)[code](9, 6) c115 / snfs142 --> poly 1
n: 2476073339693920364405250670894668031382710719787406737999834438076501498030678451389257050576150840860729252229301
# a = -193151928107839247748344636994786946/2304166573499266061307561870253195
Y0: 193151928107839247748344636994786946
Y1: 2304166573499266061307561870253195

# poly x^4 - 6*x^3 + 17*x^2 - 84*x + 196
c0: 196
c1: -84
c2: 17
c3: -6
c4: 1

skew: 5.55527
# E = 4.25843616e-09 <-- much better poly

-------------------------

(9, 6) c115 / snfs142 --> poly 2
n: 2476073339693920364405250670894668031382710719787406737999834438076501498030678451389257050576150840860729252229301
# a = 1416580160812854183955024191330598082/402433022230173357925842207081346257
Y0: -1416580160812854183955024191330598082
Y1: 402433022230173357925842207081346257

# poly x^4 - 6*x^3 + 17*x^2 - 84*x + 196
c0: 196
c1: -84
c2: 17
c3: -6
c4: 1

skew: 3.66510
# E = 2.82584039e-09[/code]

Max0526 2021-06-06 15:03

[QUOTE=RichD;580137]Need poly for c125 (formerly c133) on line 107 please.[/QUOTE]
[code]
(9, 6) c125 / snfs142 --> poly 1
n: 33686217476140019958989433779508350063727869238075948049679241969708104956801555447665897320946173678832895308681936166779529
# a = 1416580160812854183955024191330598082/402433022230173357925842207081346257
Y0: -1416580160812854183955024191330598082
Y1: 402433022230173357925842207081346257

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 3.65424
# E = 2.49624291e-09

--------------------------

(9, 6) c125 / snfs142 --> poly 2
n: 33686217476140019958989433779508350063727869238075948049679241969708104956801555447665897320946173678832895308681936166779529
# a = -193151928107839247748344636994786946/2304166573499266061307561870253195
Y0: -193151928107839247748344636994786946
Y1: 2304166573499266061307561870253195

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 5.95182
# E = 3.76440448e-09 <-- much better poly
[/code]

Max0526 2021-06-06 15:17

[QUOTE=bur;580119]Thanks, LaurV, I can technically do the "if you read the paper", but I doubt I'd come to the conclusion that they all have an SNFS poly...


And Max, can you please also post polys for the c134 and c141 of row 96? No ECM factors for B1=3e6.[/QUOTE]
[code](1, 9) c134 / snfs156 --> poly 1
n: 27476636407209102073171754682944653197485089860122647779458493821437107309563001456010628758601716610622138673159198259120402722460639
# a = 3538444972310855755685041933236037284727/859467359201487024741946150393544176034
Y0: -3538444972310855755685041933236037284727
Y1: 859467359201487024741946150393544176034

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 3.88658
# E = 5.10028973e-10

-----------------------

(1, 9) c134 / snfs156 --> poly 2
n: 27476636407209102073171754682944653197485089860122647779458493821437107309563001456010628758601716610622138673159198259120402722460639
# a = 100575535504907656717257331661860580591/151516918601614619739494401959609333888
Y0: -100575535504907656717257331661860580591
Y1: 151516918601614619739494401959609333888

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 2.32742
# E = 7.53614593e-10 <-- a much better poly[/code]

Stargate38 2021-06-06 15:33

Can someone please post the full list of numbers, along with reservations? I would like to try one of the smaller ones (SNFS difficulty <140), if there are any unreserved.

Max0526 2021-06-06 15:34

[QUOTE=bur;580119]Thanks, LaurV, I can technically do the "if you read the paper", but I doubt I'd come to the conclusion that they all have an SNFS poly...


And Max, can you please also post polys for the c134 and c141 of row 96? No ECM factors for B1=3e6.[/QUOTE]
[code](1, 9) c141 / snfs157 --> poly 1
n: 463087898488583587668376672731484580385423161897996658292409299712490387371173515755590929024428043985597552674657809564443764054046096674217
# a = 3538444972310855755685041933236037284727/859467359201487024741946150393544176034
Y0: -3538444972310855755685041933236037284727
Y1: 859467359201487024741946150393544176034

# poly x^4 - 12*x^3 + 62*x^2 - 168*x + 196
c0: 196
c1: -168
c2: 62
c3: -12
c4: 1

skew: 3.87114
# E = 5.06730144e-10

-------------------------

(1, 9) c141 / snfs157 --> poly 2
n: 463087898488583587668376672731484580385423161897996658292409299712490387371173515755590929024428043985597552674657809564443764054046096674217
# a = 100575535504907656717257331661860580591/151516918601614619739494401959609333888
Y0: -100575535504907656717257331661860580591
Y1: 151516918601614619739494401959609333888

# poly x^4 - 12*x^3 + 62*x^2 - 168*x + 196
c0: 196
c1: -168
c2: 62
c3: -12
c4: 1

skew: 2.58489
# E = 7.39637681e-10 <-- a much better poly[/code]

swishzzz 2021-06-06 15:42

Reserving t45 ecm for the 3 composites in line 84 (8, -7). What are the snfs difficulties for these?

RichD 2021-06-06 16:00

[QUOTE=Max0526;580142][code]
(9, 6) c125 / snfs142 --> poly 1
n: 33686217476140019958989433779508350063727869238075948049679241969708104956801555447665897320946173678832895308681936166779529
# a = 1416580160812854183955024191330598082/402433022230173357925842207081346257
Y0: -1416580160812854183955024191330598082
Y1: 402433022230173357925842207081346257

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 3.65424
# E = 2.49624291e-09

--------------------------

(9, 6) c125 / snfs142 --> poly 2
n: 33686217476140019958989433779508350063727869238075948049679241969708104956801555447665897320946173678832895308681936166779529
# a = -193151928107839247748344636994786946/2304166573499266061307561870253195
Y0: -193151928107839247748344636994786946
Y1: 2304166573499266061307561870253195

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 5.95182
# E = 3.76440448e-09 <-- much better poly
[/code][/QUOTE]

Can you double check these polys. Both are saying "evaluated polynomial is not multiple of n".

Max0526 2021-06-06 16:08

[QUOTE=Stargate38;580146]Can someone please post the full list of numbers, along with reservations? I would like to try one of the smaller ones (SNFS difficulty <140), if there are any unreserved.[/QUOTE]

[url]https://docs.google.com/spreadsheets/d/1G-FaJRjNMf9blg45skDnryMiZ1bHkHvMvirERPrz9Jc/edit#gid=0[/url]

Thank you for factoring with us!

Max0526 2021-06-06 16:09

[QUOTE=RichD;580152]Can you double check these polys. Both are saying "evaluated polynomial is not multiple of n".[/QUOTE]
On it!

EDIT: I messed up a sign for Y0, sorry. Try it now please. Let me know if something is still off.[code](9, 6) c125 / snfs142 --> poly 2
n: 33686217476140019958989433779508350063727869238075948049679241969708104956801555447665897320946173678832895308681936166779529
# a = -193151928107839247748344636994786946/2304166573499266061307561870253195
Y0: 193151928107839247748344636994786946
Y1: 2304166573499266061307561870253195

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 5.80159
# E = 3.72046912e-09 <-- much better poly[/code]

RichD 2021-06-06 16:20

[QUOTE=Max0526;580158]On it!

EDIT: I messed up a sign for Y0, sorry. Try it now please. Let me know if something is still off.[code](9, 6) c125 / snfs142 --> poly 2
n: 33686217476140019958989433779508350063727869238075948049679241969708104956801555447665897320946173678832895308681936166779529
# a = -193151928107839247748344636994786946/2304166573499266061307561870253195
Y0: 193151928107839247748344636994786946
Y1: 2304166573499266061307561870253195

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 5.80159
# E = 3.72046912e-09 <-- much better poly[/code][/QUOTE]

Still getting same thing. Shouldn't one Y be positive and the other Y negative?

Max0526 2021-06-06 16:21

[QUOTE=swishzzz;580149]Reserving t45 ecm for the 3 composites in line 84 (8, -7). What are the snfs difficulties for these?[/QUOTE]
Reserved.
SNFS 239 for all three numbers, too high for this project I'd say.
Maybe try lines 116, 117, 83 instead. It's all clear now. Let me know.

Max0526 2021-06-06 16:22

[QUOTE=RichD;580159]Still getting same thing. Shouldn't one Y be positive and the other Y negative?[/QUOTE]
On it! Recreating both with checks.

EDIT: I checked both. They will run properly now.[code](9, 6) c125 / snfs142 --> poly 1
n: 33686217476140019958989433779508350063727869238075948049679241969708104956801555447665897320946173678832895308681936166779529
# a = -193151928107839247748344636994786946/2304166573499266061307561870253195
Y0: 193151928107839247748344636994786946
Y1: 2304166573499266061307561870253195

# poly x^4 - 12*x^3 + 62*x^2 - 168*x + 196
c0: 196
c1: -168
c2: 62
c3: -12
c4: 1

skew: 5.45483
# E = 3.70731984e-09 <-- a much better poly

----------------------

(9, 6) c125 / snfs142 --> poly 2
n: 33686217476140019958989433779508350063727869238075948049679241969708104956801555447665897320946173678832895308681936166779529
# a = 1416580160812854183955024191330598082/402433022230173357925842207081346257
Y0: -1416580160812854183955024191330598082
Y1: 402433022230173357925842207081346257

# poly x^4 - 12*x^3 + 62*x^2 - 168*x + 196
c0: 196
c1: -168
c2: 62
c3: -12
c4: 1

skew: 3.66266
# E = 2.48911046e-09[/code]

Stargate38 2021-06-06 16:31

Reserving C122 from line 105 (9, 8) for ECM and NFS. What's the SNFS difficulty for that one?

Max0526 2021-06-06 16:53

[QUOTE=Stargate38;580162]Reserving C122 from line 105 (9, 8) for ECM and NFS. What's the SNFS difficulty for that one?[/QUOTE]
Reserved. Updated SNFS 188/189 in the sheet. Too high for this project I'd say.
Maybe look at line 106 and please let me know.
Thank you for factoring with us!

Stargate38 2021-06-06 17:05

ECM has about 46 minutes left until t40, and then I'll run GNFS on the C122.

bur 2021-06-06 17:34

I probably make some stupid mistake, when using the poly I get:

[CODE]Warning:Polynomial Selection (root optimized): Invalid polyselect file '/home/florian/Math/factorizations/SNFS/forum.poly': Key n missing
Warning:Polynomial Selection (root optimized): Invalid polyselect file '/home/florian/Math/factorizations/SNFS/forum.poly': Key n missing[/CODE]
And cado fails.

From what I can see, n: is there as it should be.



This is the poly file:

[CODE]n: 52241534590213705608428031799544177114898332495868045475031061652146772820386260197176363790731631003711544201169238012854931521936237993439
# a = 5043861836862596749419584668138860133250/4611493799370558561548601217536824836609
Y0: -5043861836862596749419584668138860133250
Y1: 4611493799370558561548601217536824836609

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 2.48522
# E = 3.71562975e-10 <-- a much better poly[/CODE]

Max0526 2021-06-06 17:40

A huge thank you to all!
 
From wombatman's PM:

[QUOTE=wombatman]Max,

If you end up doing something with the people who helped clear the composites,[/QUOTE]

What would you suggest?
I really appreciate all the help from the MersenneForum supportive never-giving-up community! I'd buy you all a huge bucket of ice cream (or stronger liquids). Shipment might be a problem though. :-)

But I am open for suggestions.
E.g., when the huge projects are run (VBCurtis last summer running C200+ GNFS comes to mind) and somebody needs a major hardware upgrade to host it or to speed up processing of relations / matrix steps, please feel free sending me a PM with a request for a donation.

If you read the (corrected) preprint paper, my name is in the acknowledgements at the end of p. 19. I also contributed many of the record/subrecord Z8 and Z2xZ6 curves this year alone:
1) [url]https://web.math.pmf.unizg.hr/~duje/tors/z8.html[/url]
2) [url]https://web.math.pmf.unizg.hr/~duje/tors/z8old5.html[/url]
3) [url]https://web.math.pmf.unizg.hr/~duje/tors/z2z6old5.html[/url]

The "High rank elliptic curves with prescribed torsion" chart ([url]https://web.math.pmf.unizg.hr/~duje/tors/tors.html[/url]) with the record contributions is also in the fresh off the press Dr. Dujella's Number Theory book ([url]https://www.amazon.com/NUMBER-THEORY-Andrej-Dujella/dp/9530308973[/url]).
That explains my interest in the topic.

I was working alone on Figure 2 plot last weekend and managed to complete 16 full factorizations (32 new plot points).
For Figure 3, we have already added 61 * 2 = 122 points! My estimate was to jump to 250 from 157 (it was actually 170, the published plot is missing 13 points due to symmetry). We have at least 266 points now, and more are coming!

A huge thank you to all!

bur 2021-06-06 17:48

Maybe the paper could mention mersenneforum.org users in the acknowledgements? But in general I participated for fun, it's nice to do factoring that has actual use.

Max0526 2021-06-06 17:52

[QUOTE=bur;580170]I probably make some stupid mistake, when using the poly I get:

[CODE]Warning:Polynomial Selection (root optimized): Invalid polyselect file '/home/florian/Math/factorizations/SNFS/forum.poly': Key n missing
Warning:Polynomial Selection (root optimized): Invalid polyselect file '/home/florian/Math/factorizations/SNFS/forum.poly': Key n missing[/CODE]
And cado fails.

From what I can see, n: is there as it should be.



This is the poly file:

[CODE]n: 52241534590213705608428031799544177114898332495868045475031061652146772820386260197176363790731631003711544201169238012854931521936237993439
# a = 5043861836862596749419584668138860133250/4611493799370558561548601217536824836609
Y0: -5043861836862596749419584668138860133250
Y1: 4611493799370558561548601217536824836609

# poly x^4 - 24*x^3 + 152*x^2 - 336*x + 196
c0: 196
c1: -336
c2: 152
c3: -24
c4: 1

skew: 2.48522
# E = 3.71562975e-10 <-- a much better poly[/CODE][/QUOTE]
The poly is correct[code]
> restart;
> n:=52241534590213705608428031799544177114898332495868045475031061652146772820386260197176363790731631003711544201169238012854931521936237993439;
> # a = 5043861836862596749419584668138860133250/4611493799370558561548601217536824836609
> Y0:=-5043861836862596749419584668138860133250;
> Y1:=4611493799370558561548601217536824836609;
> c0:=196;
> c1:=-336;
> c2:=152;
> c3:=-24;
> c4:=1;
> x:=-Y0/Y1;
> f:=c4*x^4 +c3*x^3 + c2*x^2 +c1*x + c0;
> numer(f)/n;
n := 52241534590213705608428031799544177114898332495868045475031\
0616521467728203862601971763637907316310037115442011692380\
12854931521936237993439


Y0 := -5043861836862596749419584668138860133250


Y1 := 4611493799370558561548601217536824836609


c0 := 196


c1 := -336


c2 := 152


c3 := -24


c4 := 1


5043861836862596749419584668138860133250
x := ----------------------------------------
4611493799370558561548601217536824836609


f := -8880262838571802175476173201447069222044490638481267808096\
5698237518669771798631459428865725465767447290933837985098\

/
46586701638738409876963356762081233839974444 / 452237442\
/
1369890053145750173716984347798481033886204802975767274877\
7745669677661238029121720725385480102999660363917820822410\
7788923262304676001699799065692161


-169984723998427923796 <-- negative cofactor snfs160/c140[/code]
CADO might not like that the cofactor snfs160/c140 is negative (I doubt it), but just in case try to change all signs for c0-c4 and rerun. Please let me know.

Do you supply the same n in the command line?

And, you factored the number already, right, at least by FactorDB and the sheet?

Max0526 2021-06-06 18:09

[QUOTE=bur;580172]Maybe the paper could mention mersenneforum.org users in the acknowledgements? But in general I participated for fun, it's nice to do factoring that has actual use.[/QUOTE]

The second instance of my name should be for sure changed to MersenneForum.
I'll personally ask Dr. Dujella to change it.

> factoring that has actual use.
The meaning of plot 3 is that it shows (with a bit of a stretch) the existence of the infinite number of at least rank 4 Z2xZ6 elliptic curves. Some of them (hopefully also the infinite number of them) might have ranks 6, 8, 10, ... How many rank 6 Z2xZ6 curves did we find by now? Only four! [url]https://web.math.pmf.unizg.hr/~duje/tors/z2z6.html[/url] Two of them were discovered just last year, none of them are mine.

I guess we need to involve some MersenneForum participants in high rank elliptic curve search too! :-)

bur 2021-06-06 18:09

I honestly don't remember if I factored the number already, thanks for noticing... :D


Anyway, same problem on next composite, I used the CADO converter to convert it to msieve fb and back to cado poly. I had to delete m: and re-introduce skew: but now it works. Maybe some character encoding problem because I copied the poly from a Win10 machine to linux via Putty. Who knows.


And btw I don't know if the question about algebraic or rational side sieving was already answered, but at least for the c134 rational side was faster after 5% test-sieving.

Plutie 2021-06-06 18:26

(3, -8) c130 will be factored in around 5 hours, but the c168 doesn't seem doable right now.
Could I reserve (9, -3)'s c118?

Max0526 2021-06-06 18:27

[QUOTE=bur;580176]Maybe some character encoding problem because I copied the poly from a Win10 machine to linux via Putty.[/QUOTE]
One known problem is copy-pasting a minus sign (there could be so many codes for that symbol), especially from a PDF file.

Max0526 2021-06-06 18:28

[QUOTE=Plutie;580178](3, -8) c130 will be factored in around 5 hours, but the c168 doesn't seem doable right now.
Could I reserve (9, -3)'s c118?[/QUOTE]

Reserved. Do you need SNFS polys? Please let me know.

bur 2021-06-06 20:01

Cado failed at square root stage with

[CODE]Error, found no suitable prime up to 1000000[/CODE]


Any idea what might be the problem?

Max0526 2021-06-06 20:14

[QUOTE=bur;580186]Cado failed at square root stage with

[CODE]Error, found no suitable prime up to 1000000[/CODE]


Any idea what might be the problem?[/QUOTE]

CADO is famous for failing like that on SNFS polys of degree 4.
Take all the raw relations, pass them to msieve and finish everything in msieve.
If it is too complicated for you, you could zip the whole relation folder and along with poly upload it somewhere for me. I usually use Mega ([url]https://mega.io/[/url]) but Google Drive should work too I guess.

EDIT: I read through this: [url]https://gitlab.inria.fr/cado-nfs/cado-nfs/-/blob/simpler-merge/README.msieve[/url]
and succeeded recovering CADO relations for SNFS 170 through msieve.
[code]II) Using msieve filtering and linear algebra with relations in CADO format

1) Create a file msieve.fb, which contains:

N <number to be factored>
R0 <coeff of x^0, rational side>
R1 <coeff of x^1, rational side>
A0 <coeff of x^0, algebraic side>
A1 <etc>
A2 <etc>
A3 <etc>
A4 <etc>
A5 <etc>

This can be done with:

$ ./convert_poly -of msieve < cxxx.poly > msieve.fb <-- I did it manually

2) create a file msieve.dat, which contains:

N <number to be factored>
<all the relations in GGNFS/CADO format>

(Do not include free relations, since the CADO-NFS format is not
recognized by msieve, and msieve includes them in the filtering.)

3) then run "msieve -nc -v <number to be factored>"
The msieve output goes into msieve.log.
You can add the "-t 4" option to use 4 threads.
[/code]

frmky 2021-06-07 02:03

For these polynomials, there is no small prime p for which the algebraic polynomial mod p is irreducible. The square root algorithm requires one. msieve forges ahead anyway with a small prime, which sometimes (often enough) works. Perhaps CADO just gives up?

Max0526 2021-06-07 02:13

[QUOTE=frmky;580198]For these polynomials, there is no small prime p for which the algebraic polynomial mod p is irreducible. The square root algorithm requires one. msieve forges ahead anyway with a small prime, which sometimes (often enough) works. Perhaps CADO just gives up?[/QUOTE]
Copy-paste form CADO's README[code]The default square root algorithm does not work in some very rare cases
that could possibly occur with SNFS polynomials (a degree 4 polynomial
with Galois group $Z/2 \times Z/2$ is the only reasonable example, next
case is for degree 8). The CRT approach is a workaround. See
[`sqrt/crtaglsqrt.c`](sqrt/crtaglsqrt.c) .[/code]They misspelled crtalgsqrt there. I tried that workaround, it didn't work for me. All our SNFS polys are degree 4 and CADO might fail in the last stage. All the collected relations are good though, msieve finishes everything properly.


EDIT: or we want to believe so, see EdH's comment below.

EdH 2021-06-07 02:21

[QUOTE=Max0526;580199]Copy-paste form CADO's README[code]The default square root algorithm does not work in some very rare cases
that could possibly occur with SNFS polynomials (a degree 4 polynomial
with Galois group $Z/2 \times Z/2$ is the only reasonable example, next
case is for degree 8). The CRT approach is a workaround. See
[`sqrt/crtaglsqrt.c`](sqrt/crtaglsqrt.c) .[/code]They misspelled crtalgsqrt there. I tried that workaround, it didn't work for me. All our SNFS polys are degree 4 and CADO might fail in the last stage. All the collected relations are good though, msieve finishes everything properly.[/QUOTE]
Except in my case (mentioned earlier). Msieve failed SQRT as well, with a "lanczos error."

Max0526 2021-06-07 04:28

Thank you for factoring with us!
 
68 * 2 = 136 new points on Figure 3 plot in two days! Much better than was initially predicted!

Thank you, everybody, for factoring with us!

Some non-Mersenne members joined the effort too (e.g. thyrex from TeslaCrypt forum at BleepingComputer).
Stages 5 and 6 are fully done, we are only 2 lines (3 factorizations, 4 points) off in stage 7.
I sent an email to Dr. Dujella with a request to acknowledge Mersenne Forum community for the help with factorization during this weekend. We'll probably hear from the authors in the next couple of days.
Building Magma script will take me some time next week. I will post the output of the run in this thread when it's done.
Feel free to continue for as long as it's fun for you, I am still monitoring and updating the sheet all the time. I suggested to stop at SNFS 170, now I see that many of you have much better hardware. The sky is a limit then!
I am still hoping to derive some kind of Aurifeuillean factorization for this case and split all the c270s right in the middle. Or create a new spin procedure and get twice better SNFS polys. Yeah, we wish! But some of it might happen and will be posted here.

Thank you again for all your hard and amazing work! I hope you enjoyed this weekend!

swishzzz 2021-06-07 05:13

I just found this 26 digit prime factor 48302990143744527119714651 of the c184 ([url]http://factordb.com/index.php?id=1100000002599666930[/url]) 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)?

Max0526 2021-06-07 05:37

[QUOTE=swishzzz;580209]I just found this 26 digit prime factor 48302990143744527119714651 of the c184 ([url]http://factordb.com/index.php?id=1100000002599666930[/url]) 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)?[/QUOTE]
1) How did you even notice it?
2) Yes, there is a way.
3a) I believe I just killed all but one composite of (10, -4) by your trick.
3b) and c148 from (7, -7)
3c) and c177 from (8, -8)
3d) and c119 from (2, -8)
4) Working on doing the same for the rest of the cases.


All times are UTC. The time now is 07:58.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.