From 51cf88a8d91b8067d0b077e50d39452dd71e8b77 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Mon, 3 Dec 2018 07:10:09 -0500 Subject: Extend ct_modulo to handle negative inputs Unfortunately Barrett reductions API allows negative inputs --- src/lib/math/bigint/divide.cpp | 25 +++++++++++++++++-------- 1 file changed, 17 insertions(+), 8 deletions(-) (limited to 'src/lib') diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp index 5e2dd92d9..2dfb7405e 100644 --- a/src/lib/math/bigint/divide.cpp +++ b/src/lib/math/bigint/divide.cpp @@ -20,13 +20,14 @@ namespace { */ void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) { - if(x.sign() == BigInt::Negative) - { + if(x.sign() != y.sign()) q.flip_sign(); - if(r.is_nonzero()) { --q; r = y.abs() - r; } + + if(x.is_negative() && r.is_nonzero()) + { + q -= 1; + r = y.abs() - r; } - if(y.sign() == BigInt::Negative) - q.flip_sign(); } inline bool division_check(word q, word y2, word y1, @@ -101,7 +102,7 @@ void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out) r = r_gte_y.select(r - y, r); } - if(x.sign() == BigInt::Negative) + if(x.is_negative()) { q.flip_sign(); if(r != 0) @@ -117,8 +118,8 @@ void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out) BigInt ct_modulo(const BigInt& x, const BigInt& y) { - if(x.is_negative() || y.is_negative() || y.is_zero()) - throw Invalid_Argument("ct_modulo requires x >= 0 and y > 0"); + if(y.is_negative() || y.is_zero()) + throw Invalid_Argument("ct_modulo requires y > 0"); const size_t y_words = y.sig_words(); @@ -140,6 +141,14 @@ BigInt ct_modulo(const BigInt& x, const BigInt& y) r.ct_cond_swap(r_gte_y, t); } + if(x.is_negative()) + { + if(r.is_nonzero()) + { + r = y - r; + } + } + return r; } -- cgit v1.2.3