Challenge Problem: Find the additional trait constraints on egcd that make this work.

egcd.rs

use std::ops::*;

trait Builder {
  fn zero() -> Self;
  fn is_zero(&self) -> bool;
  fn from_u8(x: u8) -> Self;
}

pub fn egcd<S>(a: &S, b: &S) -> (S, S, S)
  where
    S: Builder + Clone,
    FIXME
{
    let mut s: S      = S::zero();
    let mut old_s: S  = S::from_u8(1);
    let mut t: S      = S::from_u8(1);
    let mut old_t: S  = S::zero();
    let mut r: S      = b.clone();
    let mut old_r: S  = a.clone();
    while !r.is_zero() {
        let quotient: S = old_r.clone() / r.clone();
        let prov_r = r.clone();
        let prov_s = s.clone();
        let prov_t = t.clone();
        r = old_r - (r * &quotient);
        s = old_s - (s * &quotient);
        t = old_t - (t * &quotient);
        old_r = prov_r;
        old_s = prov_s;
        old_t = prov_t;
    }
    (old_r, old_s, old_t)
}

pub trait Builder {
    fn zero() -> Self;
    fn is_zero(&self) -> bool;
    fn from_u8(x: u8) -> Self;
    fn mul(&self, &Self) -> Self;
    fn div(&self, &Self) -> Self;
    fn sub(&self, &Self) -> Self;
}

pub fn egcd<S>(a: &S, b: &S) -> (S, S, S)
    where
        S: Builder + Clone
{
    let mut s: S = S::zero();
    let mut old_s: S = S::from_u8(1);
    let mut t: S = S::from_u8(1);
    let mut old_t: S = S::zero();
    let mut r: S = b.clone();
    let mut old_r: S = a.clone();
    while !r.is_zero() {
        let quotient: S = old_r.sub(&r);
        let prov_r = r.clone();
        let prov_s = s.clone();
        let prov_t = t.clone();
        r = old_r.sub(&r.mul(&quotient));
        s = old_s.sub(&s.mul(&quotient));
        t = old_t.sub(&t.mul(&quotient));
        old_r = prov_r;
        old_s = prov_s;
        old_t = prov_t;
    }
    (old_r, old_s, old_t)
}