Add lcm and gcd functions

[kunerd]

No description provided.

[vks]

An implementation:

extern crate ramp;

use std::cmp::Ordering;
use ramp::Int;

#[derive(Debug,Copy,Clone,PartialEq,Eq)]
struct GcdResult<T> {
    /// Greatest common divisor.
    gcd: T,
    /// Coefficients such that: gcd(a, b) = c1*a + c2*b
    c1: T, c2: T,
}

/// Calculate greatest common divisor and the corresponding coefficients.
fn extended_gcd(a: Int, b: Int) -> GcdResult<Int> {
    // Euclid's extended algorithm
    let (mut s, mut old_s) = (Int::zero(), Int::one());
    let (mut t, mut old_t) = (Int::one(), Int::zero());
    let (mut r, mut old_r) = (b, a);

    while r != 0 {
        let quotient = &old_r / &r;
        let mut tmp;
        tmp = r.clone(); r = &old_r - &quotient * r; old_r = tmp;
        tmp = s.clone(); s = &old_s - &quotient * s; old_s = tmp;
        tmp = t.clone(); t = &old_t - &quotient * t; old_t = tmp;
    }

    let _quotients = (t, s); // == (a, b) / gcd

    GcdResult { gcd: old_r, c1: old_s, c2: old_t }
}

fn main() {
    println!("{:?}", extended_gcd(Int::from(6), Int::from(3)));
}

From this it is possible to calculate a few other number theoretical functions.

Where should this functionality go? int.rs? A new file? Should the interface rather be a.gcd(b)? Should it be destructive?

(By the way, I think everything should be destructive, adding a .clone() is easy. We could get rid of square and only have dsquare, because .clone().dsquare() is equivalent to .square().)

[Aatch]

@vks I'd really like to see this implemented in the low-level section to avoid as much copying. Probably in a new file ll/gcd.rs with the signature unsafe fn extended_gcd(gp: *mut Limb, ap: *mut Limb, an: i32, bp: *mut Limb, bn: i32) -> i32 with {ap, an} and {bp,bn} being modified in-place, and the gcd being in gp and the return value being the number of limbs in the GCD.

Since GCD is integral to implementing rationals, I want to make sure it's reasonably efficient in it's first implementation. Doesn't have to be super-tuned like GMP's right away, but just implementing it in the unsafe portion of the library should be enough.

As for what the higher-level API should be, I think that a static method on Int is probably the best option, so calling it would be Int::gcd(a, b), and have it take a and b by-value, with that returning an Int too, then an extended_gcd method which could either take a and b by-value and return the GcdResult you have there or take a and b as mutable-references and modify them in-place. I'm leaning towards the first option as I agree that pretty much everything that might have to modify the value passed should take it by-value.

[kunerd]

Euclid's extended algorithm is not a good fit for multiple-precision integers, see http://cacr.uwaterloo.ca/hac/about/chap14.pdf Section 14.4 for more details. I think it would be a good idea to implement one or more of the algorithms, which are described in this section.

[kunerd]

I have implemented the binary gcd and the extended binary gcd algorithms, as described in the "Handbook of applied cryptography". Both run two times faster as Euclid's extended algorithm.
@Aatch: I have no idea how to move my current safe implementation into the ll part. Should I create a pull-request for the save implementation, so that we can move it into ll together?

[kunerd]

I have seen, that other libraries (like GMP) are using different algorithms for the various input sizes.
Therefore, @vks It would be very nice to have your extended euclidean algorithm implemented in the low-level part of ramp also - as aatch already said. After that we can do some benchmarks that orientate on the thresholds used by GMP.

See also:
GMP - gcd()
https://gmplib.org/manual/Greatest-Common-Divisor-Algorithms.html
For really large inputs maybe also:
https://hal.archives-ouvertes.fr/file/index/docid/71533/filename/RR-5050.pdf#page=22&zoom=auto,-74,716

[vks]

I don't know yet when I'll find the time to implement the low-level version. (I've had a quick look at low-level ramp, and frankly it made the task at hand seem a bit daunting.)

[vks]

The only thing missing to close this issue is a safe interface to gcd and lcm, right?

Edit: Nevermind, those are implemented. It would be nice to have extended Euclid algorithm though, to get the coefficients.

[rozbb]

I like the idea of a low-level extended gcd function. I may try to implement it in the future.