numlib::ecm -- factor an integer
using the elliptic curve method
Introductionnumlib::ecm(n) tries to factor the
positive integer n using the elliptic curve method.
numlib::ecm(n, BaseBound, s, Step2Bound)
and numlib::ecm(n, Base, s, Step2Bound) do
the same, with some internal parameters of the algorithm specified -
see the ``Details'' section. The last, or the last two, parameter(s)
may be omitted.
Call(s)numlib::ecm(n)
numlib::ecm(n, BaseBound)
numlib::ecm(n, Base)
numlib::ecm(n, BaseBound, s)
numlib::ecm(n, Base, s)
numlib::ecm(n, BaseBound, s, Step2Bound)
numlib::ecm(n, Base, s, Step2Bound)
Parametersn |
- | positive integer |
BaseBound |
- | positive integer |
Base |
- | list of primes |
s |
- | integer |
Step2Bound |
- | positive integer |
Returnsnumlib::ecm returns an integer that divides
n; the return value may equal 1 or n.
Related
Functions
Detailsnumlib::ecm takes an elliptic curve modulo
n and a point on that curve and computes some multiple of
that point. This multiplication may fail; in this case, a proper factor
of n can be found. Otherwise, the point computed is likely
to have small order; it is used in a post-processing step.s.
It is chosen at random if s is not given.Base, or all primes below BaseBound, or -- if
neither of both is given -- by all primes below 1000.Step2Bound. By
default, 100 times BaseBound (or the maximum of
Base, respectively) is chosen.
Example
1We factor an integer using the default parameters.
>> numlib::ecm(10000019070000133)
10000019
Example
2If too few multiplications on the elliptic curve are carried out, the algorithm is likely to fail.
>> numlib::ecm(10000019070000133, 50)
1
Background