Algorithmic number theory-the complexity contribution

Though algorithmic number theory is one of man´s oldest intellectual pursuits, its current vitality is perhaps unrivalled in history. This is due in part to the injection of new ideas from computational complexity. In this paper, a brief history of the symbiotic relationship between number theory and complexity theory will be presented. In addition, some of the technical aspects underlying `modern´ methods of primality testing and factoring will be described. Finally, an extensive lists of open problems in algorithmic number theory will be provided