Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T12:13:27.631Z Has data issue: false hasContentIssue false

Theorems on factorization and primality testing

Published online by Cambridge University Press:  24 October 2008

J. M. Pollard
Affiliation:
(Mathematics Department, Plessey Telecommunications Research, Taplow Court, Taplow, Maidenhead, Berkshire)
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

1. Introduction. This paper is concerned with the problem of obtaining theoretical estimates for the number of arithmetical operations required to factorize a large integer n or test it for primality. One way of making these problems precise uses a multi-tape Turing machine (e.g. (1), although we require a version with an input tape). At the start of the calculation n is written in radix notation on one of the tapes, and the machine is to stop after writing out the factors in radix notation or after writing one of two symbols denoting ‘prime’ or ‘composite’. There are, of course, other definitions which could be used; but the differences between these are unimportant for our purpose.

Information

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1974