src/nt/residue/q/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/qpow/mod/lib.hpp" | ||
| 4 | #include "../../inverse/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | 924425 | CEXP auto qresidue(u64 a, u64 p) NE { | |
| 9 | 924425 | std::optional<u64> ret; | |
| 10 |
2/2✓ Branch 0 taken 4805 times.
✓ Branch 1 taken 919620 times.
|
924425 | if (!(a %= p)) { |
| 11 | 4805 | ret.emplace(0); | |
| 12 | 4805 | return ret; | |
| 13 | } | ||
| 14 | 1997430 | auto f = [](u64 a, u64 p) NE { return qpow_mod(a, p / 2, p) == 1; }; | |
| 15 |
2/2✓ Branch 1 taken 459487 times.
✓ Branch 2 taken 460133 times.
|
919620 | if (!f(a, p)) return ret; |
| 16 | 460133 | u64 r = 2; | |
| 17 |
2/2✓ Branch 1 taken 617677 times.
✓ Branch 2 taken 460133 times.
|
1077810 | while (f(r, p)) ++r; |
| 18 | 460133 | csint n = std::countr_zero(p - 1); | |
| 19 | 460133 | cu64 m = (p - 1) >> n, g = qpow_mod(r, m, p), b = qpow_mod(a, m / 2, p), am = qpow_mod(a, m, p); | |
| 20 | 460133 | u64 e = 0; | |
| 21 |
2/2✓ Branch 3 taken 2548726 times.
✓ Branch 4 taken 460133 times.
|
3008859 | flt_ (int, k, 1, n) e |= (u64)(qpow_mod(am * inverse(qpow_mod(g, e, p), p) % p, 1 << (n - 1 - k), p) == p - 1) << k; |
| 22 | 460133 | ret.emplace(a * b % p * inverse(qpow_mod(g, e / 2, p), p) % p); | |
| 23 | 460133 | return ret; | |
| 24 | } | ||
| 25 | |||
| 26 | } // namespace tifa_libs | ||
| 27 |