Mercurial > dropbear

annotate tomsfastmath/src/mont/fp_montgomery_setup.c @ 643:a362b62d38b2 dropbear-tfm

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a with Makefile.in renamed
author Matt Johnston <matt@ucc.asn.au>
date Wed, 23 Nov 2011 18:10:20 +0700
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
643
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 /* TomsFastMath, a fast ISO C bignum library.
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 *
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 * This project is meant to fill in where LibTomMath
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 * falls short. That is speed ;-)
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 *
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 * This project is public domain and free for all purposes.
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 *
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 * Tom St Denis, [email protected]
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 #include <tfm.h>
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 /* setups the montgomery reduction */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 int fp_montgomery_setup(fp_int *a, fp_digit *rho)
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 {
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 fp_digit x, b;
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 /* fast inversion mod 2**k
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 *
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 * Based on the fact that
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 *
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 * => 2*X*A - X*X*A*A = 1
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 * => 2*(1) - (1) = 1
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24 */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25 b = a->dp[0];
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 if ((b & 1) == 0) {
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28 return FP_VAL;
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 }
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31 x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 x *= 2 - b * x; /* here x*a==1 mod 2**8 */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 x *= 2 - b * x; /* here x*a==1 mod 2**16 */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 x *= 2 - b * x; /* here x*a==1 mod 2**32 */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 #ifdef FP_64BIT
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36 x *= 2 - b * x; /* here x*a==1 mod 2**64 */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37 #endif
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 /* rho = -1/m mod b */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40 *rho = (((fp_word) 1 << ((fp_word) DIGIT_BIT)) - ((fp_word)x));
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42 return FP_OKAY;
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43 }
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46 /* $Source$ */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47 /* $Revision$ */
a362b62d38b2 Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 /* $Date$ */