## `numlib::ecm` -- factor an integer using the elliptic curve method

#### Introduction

`numlib::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)`

#### Parameters

`n` | - | positive integer
`BaseBound` | - | positive integer
`Base` | - | list of primes
`s` | - | integer
`Step2Bound` | - | positive integer

#### Returns

`numlib::ecm` returns an integer that divides `n`; the return value may equal 1 or `n`.

#### Related Functions

`ifactor`

#### Details

- Basically, `numlib::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.
- The starting point is computed from the parameter `s`. It is chosen at random if `s` is not given.
- The starting point chosen is multiplied either by all primes in `Base`, or all primes below `BaseBound`, or -- if neither of both is given -- by all primes below 1000.
- The post-processing step consists of a certain number of iterations, determined by the parameter `Step2Bound`. By default, 100 times `BaseBound` (or the maximum of `Base`, respectively) is chosen.

#### Example 1

We factor an integer using the default parameters.

    >> numlib::ecm(10000019070000133)

                                     10000019

#### Example 2

If too few multiplications on the elliptic curve are carried out, the algorithm is likely to fail.

    >> numlib::ecm(10000019070000133, 50)

                                         1

#### Background

- A description of the algorithm can be found in ``Speeding the Pollard and Elliptic Curve Methods of Factorization'', by Peter Montgomery, Math. of Comp. 48 (177), pages 243-264, January 1987.

#### Changes

- no changes

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000