Mercurial > dropbear

comparison bn_mp_n_root.c @ 190:d8254fc979e9 libtommath-orig LTM_0.35

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import of libtommath 0.35
author Matt Johnston <matt@ucc.asn.au>
date Fri, 06 May 2005 08:59:30 +0000
parents d29b64170cf0
children
comparison
equal deleted inserted replaced
142:d29b64170cf0 190:d8254fc979e9
38 if ((res = mp_init (&t1)) != MP_OKAY) { 38 if ((res = mp_init (&t1)) != MP_OKAY) {
39 return res; 39 return res;
40 } 40 }
41 41
42 if ((res = mp_init (&t2)) != MP_OKAY) { 42 if ((res = mp_init (&t2)) != MP_OKAY) {
43 goto __T1; 43 goto LBL_T1;
44 } 44 }
45 45
46 if ((res = mp_init (&t3)) != MP_OKAY) { 46 if ((res = mp_init (&t3)) != MP_OKAY) {
47 goto __T2; 47 goto LBL_T2;
48 } 48 }
49 49
50 /* if a is negative fudge the sign but keep track */ 50 /* if a is negative fudge the sign but keep track */
51 neg = a->sign; 51 neg = a->sign;
52 a->sign = MP_ZPOS; 52 a->sign = MP_ZPOS;
55 mp_set (&t2, 2); 55 mp_set (&t2, 2);
56 56
57 do { 57 do {
58 /* t1 = t2 */ 58 /* t1 = t2 */
59 if ((res = mp_copy (&t2, &t1)) != MP_OKAY) { 59 if ((res = mp_copy (&t2, &t1)) != MP_OKAY) {
60 goto __T3; 60 goto LBL_T3;
61 } 61 }
62 62
63 /* t2 = t1 - ((t1**b - a) / (b * t1**(b-1))) */ 63 /* t2 = t1 - ((t1**b - a) / (b * t1**(b-1))) */
64 64
65 /* t3 = t1**(b-1) */ 65 /* t3 = t1**(b-1) */
66 if ((res = mp_expt_d (&t1, b - 1, &t3)) != MP_OKAY) { 66 if ((res = mp_expt_d (&t1, b - 1, &t3)) != MP_OKAY) {
67 goto __T3; 67 goto LBL_T3;
68 } 68 }
69 69
70 /* numerator */ 70 /* numerator */
71 /* t2 = t1**b */ 71 /* t2 = t1**b */
72 if ((res = mp_mul (&t3, &t1, &t2)) != MP_OKAY) { 72 if ((res = mp_mul (&t3, &t1, &t2)) != MP_OKAY) {
73 goto __T3; 73 goto LBL_T3;
74 } 74 }
75 75
76 /* t2 = t1**b - a */ 76 /* t2 = t1**b - a */
77 if ((res = mp_sub (&t2, a, &t2)) != MP_OKAY) { 77 if ((res = mp_sub (&t2, a, &t2)) != MP_OKAY) {
78 goto __T3; 78 goto LBL_T3;
79 } 79 }
80 80
81 /* denominator */ 81 /* denominator */
82 /* t3 = t1**(b-1) * b */ 82 /* t3 = t1**(b-1) * b */
83 if ((res = mp_mul_d (&t3, b, &t3)) != MP_OKAY) { 83 if ((res = mp_mul_d (&t3, b, &t3)) != MP_OKAY) {
84 goto __T3; 84 goto LBL_T3;
85 } 85 }
86 86
87 /* t3 = (t1**b - a)/(b * t1**(b-1)) */ 87 /* t3 = (t1**b - a)/(b * t1**(b-1)) */
88 if ((res = mp_div (&t2, &t3, &t3, NULL)) != MP_OKAY) { 88 if ((res = mp_div (&t2, &t3, &t3, NULL)) != MP_OKAY) {
89 goto __T3; 89 goto LBL_T3;
90 } 90 }
91 91
92 if ((res = mp_sub (&t1, &t3, &t2)) != MP_OKAY) { 92 if ((res = mp_sub (&t1, &t3, &t2)) != MP_OKAY) {
93 goto __T3; 93 goto LBL_T3;
94 } 94 }
95 } while (mp_cmp (&t1, &t2) != MP_EQ); 95 } while (mp_cmp (&t1, &t2) != MP_EQ);
96 96
97 /* result can be off by a few so check */ 97 /* result can be off by a few so check */
98 for (;;) { 98 for (;;) {
99 if ((res = mp_expt_d (&t1, b, &t2)) != MP_OKAY) { 99 if ((res = mp_expt_d (&t1, b, &t2)) != MP_OKAY) {
100 goto __T3; 100 goto LBL_T3;
101 } 101 }
102 102
103 if (mp_cmp (&t2, a) == MP_GT) { 103 if (mp_cmp (&t2, a) == MP_GT) {
104 if ((res = mp_sub_d (&t1, 1, &t1)) != MP_OKAY) { 104 if ((res = mp_sub_d (&t1, 1, &t1)) != MP_OKAY) {
105 goto __T3; 105 goto LBL_T3;
106 } 106 }
107 } else { 107 } else {
108 break; 108 break;
109 } 109 }
110 } 110 }
118 /* set the sign of the result */ 118 /* set the sign of the result */
119 c->sign = neg; 119 c->sign = neg;
120 120
121 res = MP_OKAY; 121 res = MP_OKAY;
122 122
123 __T3:mp_clear (&t3); 123 LBL_T3:mp_clear (&t3);
124 __T2:mp_clear (&t2); 124 LBL_T2:mp_clear (&t2);
125 __T1:mp_clear (&t1); 125 LBL_T1:mp_clear (&t1);
126 return res; 126 return res;
127 } 127 }
128 #endif 128 #endif