diff options
| author | lloyd <[email protected]> | 2006-08-16 16:18:37 +0000 |
|---|---|---|
| committer | lloyd <[email protected]> | 2006-08-16 16:18:37 +0000 |
| commit | b8d15b3286d44ce8b5fe4938be7c501bb98c2547 (patch) | |
| tree | 509767cad308a2b38a2b3dbf130119a6f91e9de1 | |
| parent | d0a5ecdb4f7b1ddbefdc6a46525c276b9203abfe (diff) | |
Split Montgomery reduction into two functions, the core algorithm linked
as C (for replacing by asm later), and another that performs a subtract
if needed (inside powm_mnt.cpp). That way an asm version of the Montgomery
algorithm won't have to deal with calling other functions.
| -rw-r--r-- | include/mp_core.h | 4 | ||||
| -rw-r--r-- | src/mp_asm.cpp | 5 | ||||
| -rw-r--r-- | src/powm_mnt.cpp | 12 |
3 files changed, 15 insertions, 6 deletions
diff --git a/include/mp_core.h b/include/mp_core.h index fd489a561..77e43690a 100644 --- a/include/mp_core.h +++ b/include/mp_core.h @@ -47,9 +47,9 @@ void bigint_simple_mul(word[], const word[], u32bit, const word[], u32bit); void bigint_linmul_add(word[], u32bit, const word[], u32bit, word); /************************************************* -* Modular Reduction * +* Montgomery Reduction * *************************************************/ -void montgomery_reduce(word[], u32bit, const word[], u32bit, word); +void bigint_monty_redc(word[], u32bit, const word[], u32bit, word); /************************************************* * Misc Utility Operations * diff --git a/src/mp_asm.cpp b/src/mp_asm.cpp index ec2e31011..02f75f281 100644 --- a/src/mp_asm.cpp +++ b/src/mp_asm.cpp @@ -199,7 +199,7 @@ void bigint_simple_mul(word z[], const word x[], u32bit x_size, /************************************************* * Montgomery Reduction Algorithm * *************************************************/ -void montgomery_reduce(word z[], u32bit z_size, +void bigint_monty_redc(word z[], u32bit z_size, const word x[], u32bit x_size, word u) { for(u32bit j = 0; j != x_size; ++j) @@ -227,9 +227,6 @@ void montgomery_reduce(word z[], u32bit z_size, carry = !z_j[k]; } } - - if(bigint_cmp(z + x_size, x_size + 1, x, x_size) >= 0) - bigint_sub2(z + x_size, x_size + 1, x, x_size); } } diff --git a/src/powm_mnt.cpp b/src/powm_mnt.cpp index ad1ac312c..d28bfacfe 100644 --- a/src/powm_mnt.cpp +++ b/src/powm_mnt.cpp @@ -12,6 +12,18 @@ namespace Botan { namespace { /************************************************* +* Montgomery Reduction * +*************************************************/ +void montgomery_reduce(word z[], u32bit z_size, + const word x[], u32bit x_size, word u) + { + bigint_monty_redc(z, z_size, x, x_size, u); + + if(bigint_cmp(z + x_size, x_size + 1, x, x_size) >= 0) + bigint_sub2(z + x_size, x_size + 1, x, x_size); + } + +/************************************************* * Try to choose a good window size * *************************************************/ u32bit choose_window_bits(u32bit exp_bits, u32bit, |