| 656 | // B[NB] ---- multiplicant |
| 657 | |
| 658 | void AsymmetricMultiply(word *R, word *T, const word *A, unsigned int NA, const word *B, unsigned int NB) |
| 659 | { |
| 660 | if (NA == NB) |
| 661 | { |
| 662 | if (A == B) |
| 663 | RecursiveSquare(R, T, A, NA); |
| 664 | else |
| 665 | RecursiveMultiply(R, T, A, B, NA); |
| 666 | |
| 667 | return; |
| 668 | } |
| 669 | |
| 670 | if (NA > NB) |
| 671 | { |
| 672 | swap(A, B); |
| 673 | swap(NA, NB); |
| 674 | } |
| 675 | |
| 676 | assert(NB % NA == 0); |
| 677 | assert((NB/NA)%2 == 0); // NB is an even multiple of NA |
| 678 | |
| 679 | if (NA==2 && !A[1]) |
| 680 | { |
| 681 | switch (A[0]) |
| 682 | { |
| 683 | case 0: |
| 684 | SetWords(R, 0, NB+2); |
| 685 | return; |
| 686 | case 1: |
| 687 | CopyWords(R, B, NB); |
| 688 | R[NB] = R[NB+1] = 0; |
| 689 | return; |
| 690 | default: |
| 691 | R[NB] = LinearMultiply(R, B, A[0], NB); |
| 692 | R[NB+1] = 0; |
| 693 | return; |
| 694 | } |
| 695 | } |
| 696 | |
| 697 | RecursiveMultiply(R, T, A, B, NA); |
| 698 | CopyWords(T+2*NA, R+NA, NA); |
| 699 | |
| 700 | unsigned i; |
| 701 | |
| 702 | for (i=2*NA; i<NB; i+=2*NA) |
| 703 | RecursiveMultiply(T+NA+i, T, A, B+i, NA); |
| 704 | for (i=NA; i<NB; i+=2*NA) |
| 705 | RecursiveMultiply(R+i, T, A, B+i, NA); |
| 706 | |
| 707 | if (Add(R+NA, R+NA, T+2*NA, NB-NA)) |
| 708 | Increment(R+NB, NA); |
| 709 | } |
| 710 | |
| 711 | // R[N] ----- result = A inverse mod 2**(WORD_BITS*N) |
| 712 | // T[3*N/2] - temporary work space |
no test coverage detected