test if a and b are coprime */
| 1188 | |
| 1189 | /* test if a and b are coprime */ |
| 1190 | static int coprime(const uint16_t* a, const uint16_t* b) { |
| 1191 | uint16_t x[16], y[16], t[16]; |
| 1192 | int i; |
| 1193 | int iszero; |
| 1194 | memcpy(x, a, 32); |
| 1195 | memcpy(y, b, 32); |
| 1196 | |
| 1197 | /* simple gcd loop: while x!=0, (x,y)=(y%x,x) */ |
| 1198 | while (1) { |
| 1199 | iszero = 1; |
| 1200 | for (i = 0; i < 16; ++i) { |
| 1201 | if (x[i] != 0) { |
| 1202 | iszero = 0; |
| 1203 | break; |
| 1204 | } |
| 1205 | } |
| 1206 | if (iszero) break; |
| 1207 | mulmod256(t, y, NULL, x); |
| 1208 | memcpy(y, x, 32); |
| 1209 | memcpy(x, t, 32); |
| 1210 | } |
| 1211 | |
| 1212 | /* return whether y=1 */ |
| 1213 | if (y[0] != 1) return 0; |
| 1214 | for (i = 1; i < 16; ++i) { |
| 1215 | if (y[i] != 0) return 0; |
| 1216 | } |
| 1217 | return 1; |
| 1218 | } |
| 1219 | |
| 1220 | static void run_modinv_tests(void) { |
| 1221 | /* Fixed test cases. Each tuple is (input, modulus, output), each as 16x16 bits in LE order. */ |
no test coverage detected