Edit made on July 19, 2013 by GuestEditor at 15:45:08
Deleted text in red /
Inserted text in green
Integer factorisation is the problem of finding a
non-trivial factor 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 prime then 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 factor 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.