Botan  1.10.9
mp_monty.cpp
Go to the documentation of this file.
1 /*
2 * Montgomery Reduction
3 * (C) 1999-2011 Jack Lloyd
4 * 2006 Luca Piccarreta
5 *
6 * Distributed under the terms of the Botan license
7 */
8 
9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/mp_asm.h>
11 #include <botan/internal/mp_asmi.h>
12 #include <botan/mem_ops.h>
13 
14 namespace Botan {
15 
16 extern "C" {
17 
18 /*
19 * Montgomery Reduction Algorithm
20 */
21 void bigint_monty_redc(word z[], size_t z_size,
22  const word p[], size_t p_size,
23  word p_dash, word ws[])
24  {
25  const size_t blocks_of_8 = p_size - (p_size % 8);
26 
27  for(size_t i = 0; i != p_size; ++i)
28  {
29  word* z_i = z + i;
30 
31  const word y = z_i[0] * p_dash;
32 
33  /*
34  bigint_linmul3(ws, p, p_size, y);
35  bigint_add2(z_i, z_size - i, ws, p_size+1);
36  */
37 
38  word carry = 0;
39 
40  for(size_t j = 0; j != blocks_of_8; j += 8)
41  carry = word8_madd3(z_i + j, p + j, y, carry);
42 
43  for(size_t j = blocks_of_8; j != p_size; ++j)
44  z_i[j] = word_madd3(p[j], y, z_i[j], &carry);
45 
46  word z_sum = z_i[p_size] + carry;
47  carry = (z_sum < z_i[p_size]);
48  z_i[p_size] = z_sum;
49 
50  for(size_t j = p_size + 1; carry && j != z_size - i; ++j)
51  {
52  ++z_i[j];
53  carry = !z_i[j];
54  }
55  }
56 
57  word borrow = 0;
58  for(size_t i = 0; i != p_size; ++i)
59  ws[i] = word_sub(z[p_size + i], p[i], &borrow);
60 
61  ws[p_size] = word_sub(z[p_size+p_size], 0, &borrow);
62 
63  copy_mem(ws + p_size + 1, z + p_size, p_size + 1);
64 
65  copy_mem(z, ws + borrow*(p_size+1), p_size + 1);
66  clear_mem(z + p_size + 1, z_size - p_size - 1);
67  }
68 
69 void bigint_monty_mul(word z[], size_t z_size,
70  const word x[], size_t x_size, size_t x_sw,
71  const word y[], size_t y_size, size_t y_sw,
72  const word p[], size_t p_size, word p_dash,
73  word ws[])
74  {
75  bigint_mul(&z[0], z_size, &ws[0],
76  &x[0], x_size, x_sw,
77  &y[0], y_size, y_sw);
78 
79  bigint_monty_redc(&z[0], z_size,
80  &p[0], p_size, p_dash,
81  &ws[0]);
82  }
83 
84 void bigint_monty_sqr(word z[], size_t z_size,
85  const word x[], size_t x_size, size_t x_sw,
86  const word p[], size_t p_size, word p_dash,
87  word ws[])
88  {
89  bigint_sqr(&z[0], z_size, &ws[0],
90  &x[0], x_size, x_sw);
91 
92  bigint_monty_redc(&z[0], z_size,
93  &p[0], p_size, p_dash,
94  &ws[0]);
95  }
96 
97 }
98 
99 }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:32
word word_madd3(word a, word b, word c, word *d)
Definition: mp_asm.h:102
void bigint_monty_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:84
word word8_madd3(word z[8], const word x[8], word y, word carry)
Definition: mp_asmi.h:159
void bigint_monty_redc(word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:21
void bigint_sqr(word z[], size_t z_size, word workspace[], const word x[], size_t x_size, size_t x_sw)
Definition: mp_karat.cpp:303
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:22
void bigint_monty_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:69
void bigint_mul(word z[], size_t z_size, word workspace[], const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw)
Definition: mp_karat.cpp:248
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:66