Euclidean Algorithm to get the inverse element
| 469 | |
| 470 | // Euclidean Algorithm to get the inverse element |
| 471 | int modReverse(int a, int b) |
| 472 | { |
| 473 | a = abs(a); |
| 474 | b = abs(b); |
| 475 | // r_{-2},r_{-1} |
| 476 | int r1 = a, r2 = b; |
| 477 | // s_{-2},s_{-1} |
| 478 | int s11 = 1, s12 = 0; |
| 479 | // t_{-2},t_{-1} |
| 480 | int t21 = 0, t22 = 1; |
| 481 | |
| 482 | // q_j |
| 483 | int q = r1 / r2; |
| 484 | |
| 485 | int tempS = s12, tempT = t22, tempR = r1; |
| 486 | r1 = r2; |
| 487 | r2 = -q * r2 + tempR; |
| 488 | |
| 489 | while (r2 != 0) |
| 490 | { |
| 491 | tempS = s12; |
| 492 | tempT = t22; |
| 493 | s12 = (-q) * s12 + s11; |
| 494 | t22 = (-q) * t22 + t21; |
| 495 | s11 = tempS; |
| 496 | t21 = tempT; |
| 497 | |
| 498 | q = r1 / r2; |
| 499 | tempR = r1; |
| 500 | r1 = r2; |
| 501 | r2 = -q * r2 + tempR; |
| 502 | } |
| 503 | |
| 504 | if (r1 == 1) |
| 505 | { |
| 506 | return s12 > 0 ? s12 : s12 + b; |
| 507 | } |
| 508 | else |
| 509 | { |
| 510 | return -1; |
| 511 | } |
| 512 | } |
| 513 | |
| 514 | QCircuit constModMul(QVec &qvec, int base, int module_Num, QVec &qvec1, QVec &qvec2, QVec &qvec3) |
| 515 | { |