Factoring C187_107_97
 

I am factoring the XYYXF composite C187_107_97 by SNFS using factmsieve.py. The polynomial was generated using snfspoly.c with factmsieve generating the other parameters. The generated poly file is
[CODE]
n: 1970345977420632690008948509322951440148724745279741786494613809492047336276554068706986489307194824089709584059325864029709240415141266323406226638548697536767621473236330705499257806527
c5: 9409
c0: 11449
Y1: 361652753503381222732386945219508196243
Y0: -527480512638944839726474542256547576188897
skew: 1.00
rlim: 24800000
alim: 24800000
lpbr: 29
lpba: 29
mfbr: 58
mfba: 58
rlambda: 2.6
alambda: 2.6
[/CODE]I have been sieving from 12.4M to 60M+ on the rational side. factmsieve estimated the minmum relations as 43939705. So far I have generated 47350766 raw relations but msieve filtering is asking for more. The extract from the log file for the filtering step is
[CODE]
Sat Jan 12 09:08:46 2013 commencing number field sieve (187-digit input)
Sat Jan 12 09:08:46 2013 R0: -527480512638944839726474542256547576188897
Sat Jan 12 09:08:46 2013 R1: 361652753503381222732386945219508196243
Sat Jan 12 09:08:46 2013 A0: 11449
Sat Jan 12 09:08:46 2013 A1: 0
Sat Jan 12 09:08:46 2013 A2: 0
Sat Jan 12 09:08:46 2013 A3: 0
Sat Jan 12 09:08:46 2013 A4: 0
Sat Jan 12 09:08:46 2013 A5: 9409
Sat Jan 12 09:08:46 2013 skew 1.00, size 1.730e-15, alpha 1.611, combined = 1.780e-12 rroots = 1
Sat Jan 12 09:08:46 2013
Sat Jan 12 09:08:46 2013 commencing relation filtering
Sat Jan 12 09:08:46 2013 estimated available RAM is 35518.5 MB
Sat Jan 12 09:08:46 2013 commencing duplicate removal, pass 1
Sat Jan 12 09:14:22 2013 error -15 reading relation 27951059
Sat Jan 12 09:14:22 2013 error -15 reading relation 27952970

<error reading relation lines deleted>

Sat Jan 12 09:14:29 2013 error -15 reading relation 28124674
Sat Jan 12 09:14:29 2013 error -5 reading relation 28134737
Sat Jan 12 09:18:14 2013 skipped 2 relations with b > 2^32
Sat Jan 12 09:18:14 2013 found 8743260 hash collisions in 46409758 relations
Sat Jan 12 09:18:45 2013 added 20 free relations
Sat Jan 12 09:18:45 2013 commencing duplicate removal, pass 2
Sat Jan 12 09:21:28 2013 found 8727284 duplicates and 37682494 unique relations
Sat Jan 12 09:21:28 2013 memory use: 213.2 MB
Sat Jan 12 09:21:28 2013 reading ideals above 720000
Sat Jan 12 09:21:28 2013 commencing singleton removal, initial pass
Sat Jan 12 09:31:09 2013 memory use: 1378.0 MB
Sat Jan 12 09:31:09 2013 reading all ideals from disk
Sat Jan 12 09:31:10 2013 memory use: 1375.7 MB
Sat Jan 12 09:31:15 2013 keeping 43406083 ideals with weight <= 200, target excess is 207563
Sat Jan 12 09:31:19 2013 commencing in-memory singleton removal
Sat Jan 12 09:31:23 2013 begin with 37682494 relations and 43406083 unique ideals
Sat Jan 12 09:32:03 2013 reduce to 13412005 relations and 15124443 ideals in 24 passes
Sat Jan 12 09:32:03 2013 max relations containing the same ideal: 101
Sat Jan 12 09:32:05 2013 filtering wants 1000000 more relations
Sat Jan 12 09:32:05 2013 elapsed time 00:23:21
[/CODE]I have completed one previous SNFS (C170_108_101) which only required 1.8% excess relations over the minimum to form a matrix, so I am concerned that something has gone wrong with this job as the current excess is ~7%.

I am a relative novice at this so any help from the experts on the forum would be welcome.

You had 8M7 duplicates, which were removed, so it looks quite normal for me to have the additional required. But don't take it for granted, and wait for some guy who actually knows what he says. You can't control how many duplicates you get (beside of the trivial case when you sieve the same ranges and get everything duplicated :P)

[QUOTE=amphoria;324480]I have completed one previous SNFS (C170_108_101) which only required 1.8% excess relations over the minimum to form a matrix, so I am concerned that something has gone wrong with this job as the current excess is ~7%.[/QUOTE]

Estimating required relations is not an exact science (not yet). The statement "the current excess is ~7%" is utterly meaningless. Judging from this line "reduce to 13412005 relations and 15124443 ideals in 24 passes", I'd say you need about 4-5 million additional relations. Let's call it 5million relations for ease of bookkeeping.

Thanks both of you for confirming that I am still on the right track. I was obviously very lucky with the first composite coming out so close to the "minimum".

[QUOTE=axn;324484]Judging from this line "reduce to 13412005 relations and 15124443 ideals in 24 passes", I'd say you need about 4-5 million additional relations. Let's call it 5million relations for ease of bookkeeping.[/QUOTE]

I am interested to know how you can compute the number of relations still needed from this statement?

lpbr: 29 lpba: 29
 

I use this estimation for number of unique relations.

0.8*2^(LP size+1)/((LP size+1)*LN(2)-1)/1000000

Example:

For lpbr: 29 lpba: 29

0.8*2^[B]30[/B]/(([B]30[/B]*LN(2)-1)/1000000=43.4M unique relations.

I know it is a little oversieved.

Carlos

[QUOTE=amphoria;324502]I am interested to know how you can compute the number of relations still needed from this statement?[/QUOTE]

I use the simple rule-of-thumb: (#ideals - #relations) * C, where C is typically between 2 and 3. Like I said, not an exact science :smile:

[QUOTE=axn;324562]I use the simple rule-of-thumb: (#ideals - #relations) * C, where C is typically between 2 and 3. Like I said, not an exact science :smile:[/QUOTE]

Well in the end I needed over 8 million more raw relations - as you say not an exact science. :smile:

The number of unique relations was 43.56M so this falls just inside Carlos' formula. The linalg is now underway.

[QUOTE=amphoria;324710]

The number of unique relations was 43.56M so this falls just inside Carlos' formula. The linalg is now underway.[/QUOTE]

I won?! lol

Does snfspoly.c consider sextics? I don't know much about the details of that program. Not using the sextic unfortunately may have cost you here. It seems to sieve almost 30% faster:

[CODE]01/14/13 16:30:58 v1.33 @ dooku, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.0.1
detected Intel(R) Xeon(R) CPU X5680 @ 3.33GHz
detected L1 = 32768 bytes, L2 = 12582912 bytes, CL = 64 bytes
measured cpu frequency ~= 3325.183750
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
======= bbuhrow@gmail.com =======
======= Type help at any time, or quit to quit =======
===============================================================
cached 78498 primes. pmax = 999983


>> nfs: checking for job file - no job file found
nfs: checking for poly file - no poly file found
nfs: commencing nfs on c213: 384216106300465843559976189074741965396740806146885983052581436401044400003594732030645233587909047023368743158724418262283609774510034480364058057419660762439373472307183080067573333361236765052984542607095787020
nfs: searching for brent special forms...
nfs: searching for homogeneous cunningham special forms...
nfs: searching for XYYXF special forms...
nfs: input divides 107^97 + 97^107
gen: ========================================================
gen: best 3 polynomials:
gen: ========================================================

n: 6403601771674430725999603151245699423279013435781433050876357273350740000059912200510753893131817450389479052645406971038060162908500574672734300956994346040656224538453051334459555556020612750883075710118263117
# 107^97+97^107, difficulty: 214.57, anorm: 2.04e+38, rnorm: 2.67e+41
# scaled difficulty: 219.11, suggest sieving rational side
type: snfs
size: 214
skew: 4.6705
c6: 1
c0: 10379
Y1: -295216374856540727739668685278401
Y0: 577951262543040979328274795306257089
m: 2711399951580252266500487591561148063871668954562066325413400616019312741417206912765389779924104879574956404755850736305034332251178549282954076749009694756190489431950323554248502694002387772923040289700884431

n: 6403601771674430725999603151245699423279013435781433050876357273350740000059912200510753893131817450389479052645406971038060162908500574672734300956994346040656224538453051334459555556020612750883075710118263117
# 107^97+97^107, difficulty: 216.56, anorm: 2.08e+34, rnorm: 5.17e+47
# scaled difficulty: 223.11, suggest sieving rational side
type: snfs
size: 216
skew: 1.0400
c5: 9409
c0: 11449
Y1: -361652753503381222732386945219508196243
Y0: 527480512638944839726474542256547576188897
m: 4909503818674627746206502257286703771624942581354939434626417475246852125974830492966415903463742553072020575348492633524190735745551429437757067382409110367393034458297519141351382068266883209330716943613953009

n: 6403601771674430725999603151245699423279013435781433050876357273350740000059912200510753893131817450389479052645406971038060162908500574672734300956994346040656224538453051334459555556020612750883075710118263117
# 107^97+97^107, difficulty: 214.57, anorm: 2.04e+26, rnorm: 1.38e+59
# scaled difficulty: 224.06, suggest sieving rational side
type: snfs
size: 214
skew: 10.0934
c4: 1
c0: 10379
Y1: -5072366953385878222451914929597073120434548877601
Y0: 439376500173838607834000067424313966415740914919073313
m: 1407734850043981357117790053114179514510359357246419432165745908338664805751202823918240391135967489404126022113432052865767985689500409446884647385642175097344070232915594298398620793545707972031544479201077077

nfs: guessing snfs difficulty 214 is roughly equal to gnfs difficulty 149
nfs: guessing snfs difficulty 216 is roughly equal to gnfs difficulty 150
nfs: guessing snfs difficulty 214 is roughly equal to gnfs difficulty 149
nfs: guessing snfs difficulty 214 is roughly equal to gnfs difficulty 149

test: generating factor bases
test: fb generation took 5.1065 seconds
test: commencing test sieving of polynomial 0 on the rational side over range 20200000-20202000
gnfs-lasieve4I14e (with asm64): L1_BITS=15, SVN $Revision: 399 $
FBsize 1283148+0 (deg 6), 1282512+0 (deg 1)
total yield: 2964, q=20202011 (0.07955 sec/rel)
test: new best estimated total sieving time = 51 days 19h 30m 9s (with 1 threads)

test: generating factor bases
test: fb generation took 3.4572 seconds
test: commencing test sieving of polynomial 1 on the rational side over range 21000000-21002000
gnfs-lasieve4I14e (with asm64): L1_BITS=15, SVN $Revision: 399 $
FBsize 1327905+0 (deg 5), 1329941+0 (deg 1)
total yield: 2080, q=21002039 (0.11184 sec/rel)
test: estimated total sieving time = 72 days 22h 4m 3s (with 1 threads)

test: generating factor bases
test: fb generation took 2.3713 seconds
test: commencing test sieving of polynomial 2 on the rational side over range 25726662-25728662
gnfs-lasieve4I14e (with asm64): L1_BITS=15, SVN $Revision: 399 $
FBsize 951288+0 (deg 4), 1608463+0 (deg 1)
total yield: 1382, q=25728673 (0.15196 sec/rel)
test: estimated total sieving time = 250 days 1h 42m 3s (with 1 threads)
test: test sieving took 691.90 seconds

gen: ========================================================
gen: selected polynomial:
gen: ========================================================

n: 6403601771674430725999603151245699423279013435781433050876357273350740000059912200510753893131817450389479052645406971038060162908500574672734300956994346040656224538453051334459555556020612750883075710118263117
# 107^97+97^107, difficulty: 214.57, anorm: 2.04e+38, rnorm: 2.67e+41
# scaled difficulty: 219.11, suggest sieving rational side
type: snfs
size: 214
skew: 4.6705
c6: 1
c0: 10379
Y1: -295216374856540727739668685278401
Y0: 577951262543040979328274795306257089
m: 2711399951580252266500487591561148063871668954562066325413400616019312741417206912765389779924104879574956404755850736305034332251178549282954076749009694756190489431950323554248502694002387772923040289700884431
rlim: 20200000
alim: 20200000
lpbr: 29
lpba: 29
mfbr: 58
mfba: 58
rlambda: 2.6
alambda: 2.6
[/CODE]

0.079 sec/rel vs. 0.112 sec/rel.

[QUOTE=bsquared;324723]Does snfspoly.c consider sextics? I don't know much about the details of that program. Not using the sextic unfortunately may have cost you here. It seems to sieve almost 30% faster:
[/QUOTE]

You have to pass the degree of the polynomial that you are looking for to snfspoly.c as a parameter otherwise it defaults to a quintic.

It looks like I should take a look at yafu. :smile:

[QUOTE=amphoria;324725]You have to pass the degree of the polynomial that you are looking for to snfspoly.c as a parameter otherwise it defaults to a quintic.

It looks like I should take a look at yafu. :smile:[/QUOTE]

Its not formally released yet but this new stuff is currently in a beta testing phase. If you want to try it out PM me and I can get you a test binary (or you can build your own from SVN if you know how to do that sort of thing).