X-Git-Url: https://pd.if.org/git/?a=blobdiff_plain;f=tomsfastmath%2Fsrc%2Fmont%2Ffp_montgomery_setup.c;fp=tomsfastmath%2Fsrc%2Fmont%2Ffp_montgomery_setup.c;h=55f16dc4be5a5529f2b679bd08ae09abf1cfef45;hb=66bc25938679f1d6a1d1200f329093d82a5e99b4;hp=0000000000000000000000000000000000000000;hpb=a52ee0733f420ca20224049260d6fc5cf7d8f621;p=zpackage

diff --git a/tomsfastmath/src/mont/fp_montgomery_setup.c b/tomsfastmath/src/mont/fp_montgomery_setup.c
new file mode 100644
index 0000000..55f16dc
--- /dev/null
+++ b/tomsfastmath/src/mont/fp_montgomery_setup.c
@@ -0,0 +1,48 @@
+/* TomsFastMath, a fast ISO C bignum library.
+ * 
+ * This project is meant to fill in where LibTomMath
+ * falls short.  That is speed ;-)
+ *
+ * This project is public domain and free for all purposes.
+ * 
+ * Tom St Denis, tomstdenis@gmail.com
+ */
+#include <tfm_private.h>
+
+/* setups the montgomery reduction */
+int fp_montgomery_setup(fp_int *a, fp_digit *rho)
+{
+  fp_digit x, b;
+
+/* fast inversion mod 2**k
+ *
+ * Based on the fact that
+ *
+ * XA = 1 (mod 2**n)  =>  (X(2-XA)) A = 1 (mod 2**2n)
+ *                    =>  2*X*A - X*X*A*A = 1
+ *                    =>  2*(1) - (1)     = 1
+ */
+  b = a->dp[0];
+
+  if ((b & 1) == 0) {
+    return FP_VAL;
+  }
+
+  x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
+  x *= 2 - b * x;               /* here x*a==1 mod 2**8 */
+  x *= 2 - b * x;               /* here x*a==1 mod 2**16 */
+  x *= 2 - b * x;               /* here x*a==1 mod 2**32 */
+#ifdef FP_64BIT
+  x *= 2 - b * x;               /* here x*a==1 mod 2**64 */
+#endif
+
+  /* rho = -1/m mod b */
+  *rho = (((fp_word) 1 << ((fp_word) DIGIT_BIT)) - ((fp_word)x));
+
+  return FP_OKAY;
+}
+
+
+/* $Source$ */
+/* $Revision$ */
+/* $Date$ */