annotate bn_mp_exptmod.c @ 139:cc04b085e7dd libtommath

Pristine compilation works.
author Matt Johnston <matt@ucc.asn.au>
date Fri, 17 Dec 2004 06:27:22 +0000
parents 22d5cf7d4b1a
children a96ff234ff19
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 * LibTomMath is a library that provides multiple-precision
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 * integer arithmetic as well as number theoretic functionality.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 * The library was designed directly after the MPI library by
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 * Michael Fromberger but has been written from scratch with
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 * additional optimizations in place.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 * The library is free for all purposes without any express
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 * guarantee it works.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 #include <tommath.h>
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 /* this is a shell function that calls either the normal or Montgomery
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 * exptmod functions. Originally the call to the montgomery code was
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 * embedded in the normal function but that wasted alot of stack space
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 * for nothing (since 99% of the time the Montgomery code would be called)
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24 {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25 int dr;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 /* modulus P must be positive */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28 if (P->sign == MP_NEG) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 return MP_VAL;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 /* if exponent X is negative we have to recurse */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 if (X->sign == MP_NEG) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 mp_int tmpG, tmpX;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 int err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37 /* first compute 1/G mod P */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38 if ((err = mp_init(&tmpG)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 return err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42 mp_clear(&tmpG);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43 return err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46 /* now get |X| */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47 if ((err = mp_init(&tmpX)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 mp_clear(&tmpG);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 return err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 mp_clear_multi(&tmpG, &tmpX, NULL);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 return err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 /* and now compute (1/G)**|X| instead of G**X [X < 0] */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57 err = mp_exptmod(&tmpG, &tmpX, P, Y);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58 mp_clear_multi(&tmpG, &tmpX, NULL);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59 return err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
60 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 /* is it a DR modulus? */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63 dr = mp_dr_is_modulus(P);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
65 /* if not, is it a uDR modulus? */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
66 if (dr == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
67 dr = mp_reduce_is_2k(P) << 1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
68 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
69
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
70 /* if the modulus is odd or dr != 0 use the fast method */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
71 #ifndef NO_FAST_EXPTMOD
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
72 if (mp_isodd (P) == 1 || dr != 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73 return mp_exptmod_fast (G, X, P, Y, dr);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
74 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
75 else
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76 #endif
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
77 {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78 /* otherwise use the generic Barrett reduction technique */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79 return s_mp_exptmod (G, X, P, Y);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
81 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82