Remember, an integer is a number with no fractional part, and might be positive, negative, or zero. However, when we talk about integer factorisation it suffices to restrict ourselves to positive numbers.
Integer factorisation is the problem of finding a non-trivial divisor of a given number. A factor of $n$ is a number that divides $n,$ and non-trivial means neither 1 nor $n.$

For example, a non-trivial factor of 11111 is 41, whereas trivial factors are 1, -1, 11111 and -11111.

If n is a prime number then by definition it has no non-trivial factors. There are techniques for identifying non-primes that do not explicitly exhibit a factor, so the question of finding a non-trivial divisor is interesting.

The RSA public key cryptosystem uses numbers that are hard to factor, and if a way could be found to factor numbers quickly then that would effectively break it.


(none) (none) AGentleIntroductionToNPC
TimeComplexity
(none) AGentleIntroductionToTimeComplexity

You are here

FactoringIntegers
Divisor
Integer
PrimeNumber
(none) (none) ComplexNumber
CompositeNumber
CountingNumber
PrimePair
RationalNumber
RealNumber
WholeNumber

Local neighbourhood - D3


Last change to this page
Full Page history
Links to this page
Edit this page
  (with sufficient authority)
Change password
Recent changes
All pages
Search