From: Christoph <chr_news@...>
Date: 2002-06-09T09:28:53+09:00
Subject: RE: Another implementation of Bignum [tarball attached]

> 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