Mercurial > dropbear

annotate libtommath/bn_mp_lcm.c @ 1691:2d3745d58843

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
try rearrange travis build matrix
author Matt Johnston <matt@ucc.asn.au>
date Tue, 26 May 2020 23:27:26 +0800
parents f52919ffd3b1
children 1051e4eea25a
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
1 #include "tommath_private.h"
284
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 #ifdef BN_MP_LCM_C
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 *
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 * LibTomMath is a library that provides multiple-precision
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 * integer arithmetic as well as number theoretic functionality.
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 *
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 * The library was designed directly after the MPI library by
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 * Michael Fromberger but has been written from scratch with
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 * additional optimizations in place.
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 *
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
12 * SPDX-License-Identifier: Unlicense
284
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 */
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 /* computes least common multiple as |a*b|/(a, b) */
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
16 int mp_lcm(const mp_int *a, const mp_int *b, mp_int *c)
284
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 {
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
18 int res;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
19 mp_int t1, t2;
284
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
22 if ((res = mp_init_multi(&t1, &t2, NULL)) != MP_OKAY) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
23 return res;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
24 }
284
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
26 /* t1 = get the GCD of the two inputs */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
27 if ((res = mp_gcd(a, b, &t1)) != MP_OKAY) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
28 goto LBL_T;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
29 }
284
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
31 /* divide the smallest by the GCD */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
32 if (mp_cmp_mag(a, b) == MP_LT) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
33 /* store quotient in t2 such that t2 * b is the LCM */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
34 if ((res = mp_div(a, &t1, &t2, NULL)) != MP_OKAY) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
35 goto LBL_T;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
36 }
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
37 res = mp_mul(b, &t2, c);
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
38 } else {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
39 /* store quotient in t2 such that t2 * a is the LCM */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
40 if ((res = mp_div(b, &t1, &t2, NULL)) != MP_OKAY) {
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
41 goto LBL_T;
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
42 }
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
43 res = mp_mul(a, &t2, c);
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
44 }
284
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
46 /* fix the sign to positive */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
47 c->sign = MP_ZPOS;
284
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 LBL_T:
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
50 mp_clear_multi(&t1, &t2, NULL);
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
51 return res;
284
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 }
eed26cff980b propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 #endif
389
5ff8218bcee9 propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 2af95f00ebd5bb7a28b3817db1218442c935388e)
Matt Johnston <matt@ucc.asn.au>
parents: 284
diff changeset
54
1655
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
55 /* ref: HEAD -> master, tag: v1.1.0 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
56 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
f52919ffd3b1 update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
Steffen Jaeckel <s_jaeckel@gmx.de>
parents: 1470
diff changeset
57 /* commit time: 2019-01-28 20:32:32 +0100 */