| 574 | // ------------------------------------------------ |
| 575 | |
| 576 | void Int::ModSqrt() { |
| 577 | |
| 578 | if (_P.IsEven()) { |
| 579 | CLEAR(); |
| 580 | return; |
| 581 | } |
| 582 | |
| 583 | if (!HasSqrt()) { |
| 584 | CLEAR(); |
| 585 | return; |
| 586 | } |
| 587 | |
| 588 | if ((_P.bits64[0] & 3) == 3) { |
| 589 | |
| 590 | Int e(&_P); |
| 591 | e.AddOne(); |
| 592 | e.ShiftR(2); |
| 593 | ModExp(&e); |
| 594 | |
| 595 | } else if ((_P.bits64[0] & 3) == 1) { |
| 596 | |
| 597 | //int nbBit = _P.GetBitLength(); |
| 598 | |
| 599 | // Tonelli Shanks |
| 600 | uint64_t e=0; |
| 601 | Int S(&_P); |
| 602 | S.SubOne(); |
| 603 | while (S.IsEven()) { |
| 604 | S.ShiftR(1); |
| 605 | e++; |
| 606 | } |
| 607 | |
| 608 | // Search smalest non-qresidue of P |
| 609 | Int q((uint64_t)1); |
| 610 | do { |
| 611 | q.AddOne(); |
| 612 | } while (q.HasSqrt()); |
| 613 | |
| 614 | Int c(&q); |
| 615 | c.ModExp(&S); |
| 616 | |
| 617 | Int t(this); |
| 618 | t.ModExp(&S); |
| 619 | |
| 620 | Int r(this); |
| 621 | Int ex(&S); |
| 622 | ex.AddOne(); |
| 623 | ex.ShiftR(1); |
| 624 | r.ModExp(&ex); |
| 625 | |
| 626 | uint64_t M = e; |
| 627 | while (!t.IsOne()) { |
| 628 | |
| 629 | Int t2(&t); |
| 630 | uint64_t i=0; |
| 631 | while (!t2.IsOne()) { |
| 632 | t2.ModSquare(&t2); |
| 633 | i++; |