View Single Post
Old 2020-09-16, 03:16   #2
VBCurtis's Avatar
Feb 2005
Riverside, CA

106258 Posts

It's generally the size of the input, or the size of the original composite that generates the polynomial (for example, you might have a 25 digit factor already, but doing SNFS on the original number is faster than doing GNFS on the cofactor, so the SNFS difficulty doesn't match the composite size).

Say I'm trying to factor 2^901 - 1. That can be written 2x^6 - 1, with x equal to 2^150. That nice poly is what SNFS would use- so even if a couple of factors are known and the cofactor is 200 digits, this SNFS job at ~270 digits would be easier than a GNFS of 200.
VBCurtis is online now   Reply With Quote