Special number field sieve

Abstract

Integer factorization is a problem not yet solved for arbitrary integers. Huge integers are therefore widely used for encrypting, e.g. in the RSA encryption scheme. The special number field sieve holds the current factorization record for factoring the number 2^(1039)+1. The algorithm depends on arithmetic in an algebraic number field and is a further development from the quadratic sieve factoring algorithm. We therefor present the quadratic sieve as an introduction to the ideas behind the special number field sieve first. Then the special number field is described. The key concepts is evaluated one bye one. Everything is illustrated with the corresponding parts of an example factorization. The running time of the special number field sieve is then evaluated and compared against that of the quadratic sieve. The special number field sieve only applies to integers of a special form, but a generalization has been made, the general number field sieve. It is slower but all estimates suggests it is asymptotically faster than all other existing general purpose algorithms.