Как устранить возможное мультипликативное переполнение, чтобы получить правильную операцию модуля? - PullRequest
Новая
       61

Как устранить возможное мультипликативное переполнение, чтобы получить правильную операцию модуля?

0 голосов
/ 02 февраля 2019

Я должен выполнить (a * b) % m, но a, b, и m являются 128-битными типами без знака, и переполнение во время умножения является большой возможностью.Как я могу все еще получить правильный ответ (вероятно, используя % больше)?

Я пытаюсь реализовать модульную функцию экспоненты в Rust, где самый большой встроенный тип - u128 (который являетсямаксимум я могу использовать).Все три переменные действительно большие, поэтому (a * b) > 2^128 легкоЯ могу использовать a.overflowing_mul(b), чтобы определить, произошло ли переполнение, но я не знаю, как вернуться к результату переполнения (который можно рассматривать как (a * b) % 2^128), чтобы получить (a * b) % m.

MyМодульный код экспоненты выглядит следующим образом (в настоящее время поддержка переполнения не добавляется): 

fn mod_exp(b: u128, e: u128, m: u128) {
    (0..e).fold(1, |x, _| (x * b) % m)
    //                    ^^^^^^^^^^^
}

С математической точки зрения: 

(a * b) % m IS ACTUALLY (a * b) % B % m
| B = current base (2^128)

Примеры: 

// Mathematical
(9 * 13) % 11 = 7
// Real (base 20):
(9 * 13) % (B = 20) % 11 = 6
         ^^^^^^^^^^        ^ should be 7

(8 * 4) % 14 = 4
(8 * 4) % (B = 16) % 14 = 0
        ^^^^^^^^^^        ^ should be 4

1 Ответ

0 голосов
/ 05 февраля 2019

Эта реализация, основанная на разделении 128-битного продукта на четыре 64-битных продукта, в пять раз быстрее num_bigint::BigUint, в десять раз быстрее uint::U256 и в 2,3 раза быстрее gmp::mpz::Mpz: 

fn mul_mod(a: u128, b: u128, m: u128) -> u128 {
    if m <= 1 << 64 {
        ((a % m) * (b % m)) % m
    } else {
        let add = |x: u128, y: u128| x.checked_sub(m - y).unwrap_or_else(|| x + y);
        let split = |x: u128| (x >> 64, x & !(!0 << 64));
        let (a_hi, a_lo) = split(a);
        let (b_hi, b_lo) = split(b);
        let mut c = a_hi * b_hi % m;
        let (d_hi, d_lo) = split(a_lo * b_hi);
        c = add(c, d_hi);
        let (e_hi, e_lo) = split(a_hi * b_lo);
        c = add(c, e_hi);
        for _ in 0..64 {
            c = add(c, c);
        }
        c = add(c, d_lo);
        c = add(c, e_lo);
        let (f_hi, f_lo) = split(a_lo * b_lo);
        c = add(c, f_hi);
        for _ in 0..64 {
            c = add(c, c);
        }
        add(c, f_lo)
    }
}

( Предупреждение: ни одна из этих реализаций не подходит для использования в криптографическом коде, поскольку онине защищены от атак по побочным каналам.)

...