Brent, Richard P2003-07-112004-05-192011-01-052004-05-192011-01-051990http://hdl.handle.net/1885/40809http://digitalcollections.anu.edu.au/handle/1885/40809The problem of finding the prime factors of large composite numbers has always been of mathematical interest. With the advent of public key cryptosystems it is also of practical importance, because the security of some of these cryptosystems, such as the Rivest-Shamir-Adelman (RSA) system, depends on the difficulty of factoring the public keys. In recent years the best known integer factorisation algorithms have improved greatly, to the point where it is now easy to factor a 60-decimal digit number, and possible to factor numbers larger than 120 decimal digits, given the availability of enough computing power. We describe several recent algorithms for primality testing and factorisation, give examples of their use and outline some applications.200297 bytes356 bytesapplication/pdfapplication/octet-streamen-AUinteger factorisation algorithmsprimality testingpublic key cryptographyfactorisation1990