```> From: Дмитри? Антипо? [mailto:dmitry.antipov / mail.ru]
...
>   I'm finished merging my Bignums with 1.7.2 shapshot dated
> 2002-06-04. All issues listed in README within my previous tarball are

> fixed

Thanks!

One comment, did you consider implementing the shift methods with the
mpn methods mpn_rshift and mpn_lshift?

> (except for round-up differences).
...
> I'm thinking about 4 new number theoretic functions (`Integer' means
> `Fixnum or Bignum'):
>
> - Integer.gcd(Integer) -> Integer
>   Return a greatest common divisor

What about the ``extended'' gcd (mpz_gcdext), which is
probably more useful the gcd itself - lets say

Integer#gcd_ext(other_int) -> [gcd,m,n] such that
self*m + other_int*n = gcd (of self and other_int)

>
> - Integer.lcm(Integer) -> Integer
>   Return a least common multiple
>
> - Integer.prime? -> true or false
>   Return true if Integer is prime, false otherwise
>
> - Integer.factorize -> array of factors with exponents
>   For example:
>   17.factorize -> [17] (17 is prime)
>   36.factorize -> [[2, 2], [3, 2]] (36 = 2^2 * 3^2)
>   645645654.factorize -> [2, [3, 5], 137, 9697]
>                          (645645654 =  2 * 3^5 * 137 * 9697)
>
> These are a common tasks for numerical algorithms and appropriate
> functions
> (IMHO) will be quite useful. The impelementation for Fixnum is not
> hard, but it's a serious task to implement fast `prime?' and
> `factorize' for Bignums.
>
> Any ideas ?

You surely are aware the gmp has a probabilistic primality test. Anyway,
what about using a free implementation based on
Lenstra's elliptic curve Method - see
http://www.loria.fr/~zimmerma/records/ecmnet.html

...

/Christoph

```