mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Factoring humongous Cunningham numbers (https://www.mersenneforum.org/showthread.php?t=5722)

EdH 2019-10-12 22:03

[QUOTE=swellman;527850]B^2 is the expert on Yafu, but I believe it tries to find a SNFS fit, picks the best one (through test sieving on higher difficulty levels than Ed’s example above) and goes with that. If there is no SNFS form found it defaults to GNFS. If GNFS is lower than the SNFS equivalent, it goes with GNFS (this step sometimes occurs early in the process).

In no case does Yafu attempt to generate a GNFS poly. Yafu just looks at SNFS vs GNFS difficulties and picks accordingly.

B^2 posted [URL="https://www.mersenneforum.org/showpost.php?p=527082&postcount=396"]an example[/URL] of SNFS generation recently, with further discussion in that thread.[/QUOTE]Actually, I see the documentation says it does test sieve as low as 140 digits by default and I haven't changed that in my instances. Here is B[SUP]2[/SUP]'s info from the doc:
[code]
[snfs]
usage: snfs(expression, cofactor)

description:
Automated factorization using the special number field sieve. yafu generates snfs polynomials
suitable for the input expression, used for factoring the "cofactor" of the expression. Sieving
and post-processing then take place in exactly the same manner as with the nfs function above.
You can resume sieving or postprocessing with either the nfs or snfs functions. As with the nfs
function, you can provide your own polynomial (and ggnfs parameters if desired) in a file named
nfs.job (the "n: <your number>" must be first, as with gnfs); in order to proceed as snfs, you
must have "type: snfs" and "size: <snfs difficulty>" lines in the job file. yafu will adjust the
minimum relations estimate to account for the easier difficulty, and should otherwise proceed
just as in nfs.

Supported special forms are:
Various k*b^n+c including:
Cunningham numbers (b^n +- 1 with with b=2, 3, 5, 6, 7, 10, 11, 12)
Brent forms (b^n +/- 1, where 13<=b<=99)
Odd perfect numbers (b^n - 1, b>99)
Generalized Cullen/Woodall numbers (a*b^a +/- 1)
Others: k*2^n +/- 1, repunits, mersenne plus 2, etc.
(Note that for large b, cases with k>1 or abs(c)>1 may not be detected)
Homogeneous Cunningham numbers (a^n +/- b^n, where a,b <= 12 and gcd(a,b) == 1)
XYYXF numbers (x^y + y^x, where 1<y<x<151)

snfs supports all the command line flags for nfs, as well as one additional flag:
-testsieve <num> Number of digits beyond which yafu will test sieve the top
3 polynomials discovered by snfs (default: 140)

Note: if a certain poly is particularly bad and is taking too long to test sieve,
you can safely terminate the ggnfs process, and yafu should still get an accurate
score and continue trial sieving the other polys.

Examples:
1) perform snfs poly selection but skip test sieving for an odd perfect number,
outputing the poly to a custom job file:
"snfs(158071^37-1, (158071^37-1)/158070)" -v -np -job opn.poly -testsieve 300

2) resume sieving and do post processing:
"snfs(158071^37-1, (158071^37-1)/158070)" -v -R -ns -nc -job opn.poly
[/code]

EdH 2019-10-13 01:17

8-5,333 (SNFS):
[code]
146496653036655767180104684135090129933082763041292914489727432550693
2296717191420129888977067236407615410763629622977448879573287248015038342562388752724972079
[/code]

EdH 2019-10-13 15:44

11+8,288 (SNFS):
[code]
13442202935866563435153323151330476595960131129977207638804230111311051243195969
2403229894880044587415233205226287043745089064490314427361122371968482181538589441
[/code]

EdH 2019-10-14 01:04

3-2,621 (SNFS):[code]
28439446329097202231177799987462926292668185335436083761521577655306893371
2403544903480704915669933317775778576104526571332366033177533763093465961055748474982669294731
[/code]

EdH 2019-10-14 12:52

3+2,621 (SNFS):
[code]
155119128277659449823050367548480126156491430247895677761263
1459940613546686441832746449910913629975723579758678351155712813526896778626109967612860404302749497858201711
[/code]

EdH 2019-10-14 20:35

8-7,321 (SNFS):
[code]
123387016815330529818331176834042770683822352190206635496401
90871968372478622796729904351005528049257950013403869528811254061061763880207106415756963188900817721677961710264337234453551751
[/code]

EdH 2019-10-15 13:12

5+4,423 (SNFS):
[code]
19758207553637988203557320913191764312624295279563315505484940383585770631147
555685434835780829307507705178665407340798053526779379534090655428883868016836376010166204954461547896691082208583443
[/code]

R.D. Silverman 2019-10-15 13:22

[QUOTE=EdH;528042]5+4,423 (SNFS):
[code]
19758207553637988203557320913191764312624295279563315505484940383585770631147
555685434835780829307507705178665407340798053526779379534090655428883868016836376010166204954461547896691082208583443
[/code][/QUOTE]

Query: What size factor bases are you using [or the factor base bounds]?
29 bit LP?

EdH 2019-10-15 13:43

[QUOTE=R.D. Silverman;528043]Query: What size factor bases are you using [or the factor base bounds]?
29 bit LP?[/QUOTE]
YAFU provided this when run:
[code]
nfs: searching for homogeneous cunningham special forms...
nfs: input divides 5^423 + 4^423
nfs: degree 4 difficulty = 197.11, degree 6 difficulty = 197.11
nfs: choosing degree 6
nfs: guessing snfs difficulty 197 is roughly equal to gnfs difficulty 140
[/code]and this in nfs.job:
[code]
n: 10979348156018934848590051025448590653320541773017848001320066157517310085832266444979685246586316980466631059791401818866831274318284425535191437164188325706129211672085961314087055106924299121
# 5^423+4^423, difficulty: 197.11, anorm: 1.00e+36, rnorm: 7.11e+38
# scaled difficulty: 197.11, suggest sieving algebraic side
# size = 9.328e-10, alpha = 0.000, combined = 1.594e-11, rroots = 0
type: snfs
size: 197
skew: 1.0000
c6: 1
c3: -1
c0: 1
Y1: -19807040628566084398385987584
Y0: 710542735760100185871124267578125
m: 539809501992287277268479085703090996021680111767066327485507268286545640645798163882143549073901569889922915107123457343999521712610447343902664661660965058569474740713830713914002857221150816

rlim: 14000000
alim: 14000000
lpbr: 28
lpba: 28
mfbr: 56
mfba: 56
rlambda: 2.6
alambda: 2.6
[/code]

EdH 2019-10-15 22:23

7+2,351 (SNFS):
[code]
541184183409777436479806969602059571890583008659821204953396757
642446633697187382630607613659904768872788062481443386513864219493365781277525072544036605073175645090022970710316305533
[/code]

EdH 2019-10-16 12:31

10+3,297 (SNFS):
[code]
36536424801240841928735848669768246079471305668135697483
27370485438576078968470422838371074358183318042043301499971262811202235971524408067447225076217782895721459993029830165971347
[/code]


All times are UTC. The time now is 22:31.

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