|
|
|
|
|
|
by jedwards1211
521 days ago
|
|
|
The wiki article on GNFS says: > The size of the input to the algorithm is log2 n or the number of bits in the binary representation of n. Any element of the order nc for a constant c is exponential in log n. The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input. "Super-polynomial" means that the running time increases by more than the square. In any case, even if the algorithm were just polynomial, the argument about squaring costs doesn't work out. |
|
|