Abstract
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.
Keywords
Primality testArithmeticNotationPrime (order theory)Computer scienceFactorizationTuring machineInteger (computer science)Radix (gastropod)Prime factorMathematicsAlgebra over a fieldProgramming languageDiscrete mathematicsAlgorithmCombinatoricsComputationPure mathematics
Related Publications
On the Power of Quantum Computation
The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on...
Computing Machinery and Intelligence (1950)
Abstract Together with ‘On Computable Numbers’, ‘Computing Machinery and Intelligence’ forms Turing’s best-known work. This elegant and sometimes amusing essay was originally pu...
On the power of quantum computation
The quantum model of computation is a probabilistic model, similar to the probabilistic Turing Machine, in which the laws of chance are those obeyed by particles on a quantum me...
Analyzing bagging
Bagging is one of the most effective computationally intensive procedures to improve on unstable estimators or classifiers, useful especially for high dimensional data set probl...
Boosting the margin: a new explanation for the effectiveness of voting methods
One of the surprising recurring phenomena observed in experiments\nwith boosting is that the test error of the generated classifier usually does\nnot increase as its size become...
Publication Info
- Year
- 1974
- Type
- article
- Volume
- 76
- Issue
- 3
- Pages
- 521-528
- Citations
- 401
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
401
OpenAlex
Cite This
J. M. Pollard
(1974).
Theorems on factorization and primality testing.
Mathematical Proceedings of the Cambridge Philosophical Society
, 76
(3)
, 521-528.
https://doi.org/10.1017/s0305004100049252
Identifiers
- DOI
- 10.1017/s0305004100049252