A couple of questions about polynomial selection

[jasonp]

Note also that the -nc1 argument to msieve can take optional parameters that limit the number of relations read in, without you having to truncate your relation file.

[Batalov]

Something is off with that 'estimated min of relations', then. Because a matrix this small for 107% of the real min of relations doesn't sound right.

The matrix size appears believable (had a couple of 5.0Ms in this range); ...maybe the small size is characteristic of the RSA keys; come to think of it, the larger the penultimate factor ever happened to be, the smaller the matrix looked relative to siblings but it's hard to put a finger on it.

[debrouxl]

The matrix used for the TI-83+ OS 512-bit (C154-C155) signing key was 5.4M, but it was barely-oversieved. Matrices for the 13 other keys, created from up to nearly 70M raw relations, may have been smaller, I'll try to dig on my HDD for some msieve logs.

[jasonp]

In my experience the matrix is never more than 25-30% smaller than the initial one, even after large numbers of excess relations are thrown at it.

[aifbowman]

Hi all,

Sorry for not posting in a while, have been extremely busy getting the key factored for the deadline (yesterday!) but thanks to all your help I've done it :).

The two factors were relatively close together (one~20% larger than the other), might that have something to do with the small matrix size and/or sieve time? At least I assume they are closer together than average, having not factorised a key before.

fivemack- my polynomial file hasn't changed since I started, but I did manage to find these in the .log file:

Thu Nov 25 20:40:58 2010  found 20661549 hash collisions in 85473045 relations
Thu Nov 25 20:41:48 2010  added 121472 free relations
Thu Nov 25 20:41:49 2010  commencing duplicate removal, pass 2
Thu Nov 25 20:52:38 2010  found 23426918 duplicates and 62167599 unique relations

As for the rest, I have no idea where to find them. This is my poly file:

n: 7823445407949925252516952959603663363759565065213243539144686925012567049413798634116058539700325978831844466909241650643702088625525642002090404962143815108959
Y0: -13219363105675918783631415787677
Y1: 434875388347029907
c0: -1029014326642417092571489085992812040908800
c1: 8731184474997278725133622876587840
c2: 7284353183492994522204038424
c3: -20527989187953486362
c4: -11361050513065
c5: 19380
skew: 29242800.02
type: gnfs
qintsize:10000

I am more than happy to use the -nc1 arguement to investigate how matrix size changes with oversieving, I'm assuming you want me to post the results for your own interest, rather than just thinking it would be a useful learning exercise for me (which of course it will be)?

[warut]

Amazing! No factoring experience before, but could jump directly to factor a 160-digit RSA key.

[jrk]

Originally Posted by aifbowman

What worries me is 1. the matrix is much smaller then the one for the c160 you were talking about earlier fivemack, and 2. the ETA is much shorter as well... any ideas if there is a problem or am I just worrying over nothing?

fivemack's params allowed three large primes on the algebraic side. Your params most likely allowed only two large primes. The extra large primes in this case make the sieving faster, but at the expense of making the matrix dimensions larger.