| 108 | // ------------------------------------------------ |
| 109 | |
| 110 | void Int::ModInv() { |
| 111 | |
| 112 | // Compute modular inverse of this mop _P |
| 113 | // 0 < this < P , P must be odd |
| 114 | // Return 0 if no inverse |
| 115 | |
| 116 | // 256bit |
| 117 | //#define XCD 1 // ~62 kOps/s |
| 118 | //#define BXCD 1 // ~167 kOps/s |
| 119 | //#define MONTGOMERY 1 // ~200 kOps/s |
| 120 | //#define PENK 1 // ~179 kOps/s |
| 121 | #define DRS62 1 // ~365 kOps/s |
| 122 | |
| 123 | Int u(&_P); |
| 124 | Int v(this); |
| 125 | Int r((int64_t)0); |
| 126 | Int s((int64_t)1); |
| 127 | |
| 128 | #ifdef XCD |
| 129 | |
| 130 | Int q, t1, t2, w; |
| 131 | |
| 132 | // Classic XCD |
| 133 | |
| 134 | bool bIterations = true; // Remember odd/even iterations |
| 135 | while (!u.IsZero()) { |
| 136 | // Step X3. Divide and "Subtract" |
| 137 | q.Set(&v); |
| 138 | q.Div(&u, &t2); // q = u / v, t2 = u % v |
| 139 | w.Mult(&q, &r); // w = q * r |
| 140 | t1.Add(&s, &w); // t1 = s + w |
| 141 | |
| 142 | // Swap u,v & r,s |
| 143 | s.Set(&r); |
| 144 | r.Set(&t1); |
| 145 | v.Set(&u); |
| 146 | u.Set(&t2); |
| 147 | |
| 148 | bIterations = !bIterations; |
| 149 | } |
| 150 | |
| 151 | if (!v.IsOne()) { |
| 152 | CLEAR(); |
| 153 | return; |
| 154 | } |
| 155 | |
| 156 | if (!bIterations) { |
| 157 | Set(&_P); |
| 158 | Sub(&s); /* inv = n - u1 */ |
| 159 | } else { |
| 160 | Set(&s); /* inv = u1 */ |
| 161 | } |
| 162 | |
| 163 | #endif |
| 164 | |
| 165 | #ifdef BXCD |
| 166 | |
| 167 | #define SWAP_SUB(x,y) x.Sub(&y);y.Add(&x) |