src/nt/dlog/bsgs/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/iroot/sqrt/lib.hpp" | ||
| 4 | #include "../../../math/qpow/mod/lib.hpp" | ||
| 5 | #include "../../../util/alias/others/lib.hpp" | ||
| 6 | #include "../../mod/barrett/lib.hpp" | ||
| 7 | #include "../naive/lib.hpp" | ||
| 8 | |||
| 9 | namespace tifa_libs { | ||
| 10 | |||
| 11 | // solve $a^x\equiv b \pmod m$ | ||
| 12 | 1048 | inline auto bsgs(u64 a, u64 b, u64 m) NE { | |
| 13 | 1048 | std::optional<u64> ret; | |
| 14 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1048 times.
|
1048 | if (m < 64) { |
| 15 | ✗ | ret = dlog_naive(a, b, m); | |
| 16 | ✗ | return ret; | |
| 17 | } | ||
| 18 |
2/4✓ Branch 0 taken 1048 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1048 times.
|
1048 | if (a %= m, b %= m; m == 1 || b == 1) { |
| 19 | ✗ | ret.emplace(0); | |
| 20 | ✗ | return ret; | |
| 21 | } | ||
| 22 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1048 times.
|
1048 | if (!a) { |
| 23 | ✗ | if (!b) ret.emplace(1); | |
| 24 | ✗ | return ret; | |
| 25 | } | ||
| 26 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1048 times.
|
1048 | if (a == 1) { |
| 27 | ✗ | if (b == 1) ret.emplace(0); | |
| 28 | ✗ | return ret; | |
| 29 | } | ||
| 30 | 1048 | hmap<u64, u64> hmp; | |
| 31 | 1048 | barrett<0> brt(m, a); | |
| 32 | 1048 | u64 sqrt_m = isqrt(m), s = brt.reduce(b); | |
| 33 |
1/2✓ Branch 0 taken 1048 times.
✗ Branch 1 not taken.
|
1048 | if (sqrt_m * sqrt_m < m) ++sqrt_m; |
| 34 |
2/2✓ Branch 2 taken 28069067 times.
✓ Branch 3 taken 1048 times.
|
28070115 | for (u64 i = 1; i <= sqrt_m; ++i, s = brt.reduce(s)) hmp[s] = i; |
| 35 | 1048 | cu64 _ = qpow_mod(a, sqrt_m, m); | |
| 36 | 1048 | s = _, brt.reset(m, _); | |
| 37 |
2/2✓ Branch 1 taken 15939535 times.
✓ Branch 2 taken 450 times.
|
15939985 | for (u64 i = 1; i <= sqrt_m; ++i, s = brt.reduce(s)) |
| 38 |
5/6✓ Branch 1 taken 598 times.
✓ Branch 2 taken 15938937 times.
✓ Branch 4 taken 598 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 598 times.
✓ Branch 7 taken 15938937 times.
|
15939535 | if (hmp[s] && i * sqrt_m >= hmp[s]) { |
| 39 | 598 | ret.emplace(i * sqrt_m - hmp[s]); | |
| 40 | 598 | return ret; | |
| 41 | } | ||
| 42 | 450 | return ret; | |
| 43 | 1048 | } | |
| 44 | |||
| 45 | } // namespace tifa_libs | ||
| 46 |