diff options
| author | Gloria Mundi <gloria@gloria-mundi.eu> | 2026-09-14 23:25:14 +0200 |
|---|---|---|
| committer | Gloria Mundi <gloria@gloria-mundi.eu> | 2026-09-14 23:25:14 +0200 |
| commit | 5b85f8063460cfeec6b7a798b5dfeb06755354fd (patch) | |
| tree | 972c39aa4ca7bdcea3cd04789034f1d034f6cd32 /content/math | |
| parent | 77ca873deccb6c38f235896bf03f53d6cc0bcf2e (diff) | |
| parent | cf4b381136961c321eb0e2140a954a74341d5f2c (diff) | |
Diffstat (limited to 'content/math')
| -rw-r--r-- | content/math/legendre.cpp | 2 | ||||
| -rw-r--r-- | content/math/sqrtModCipolla.cpp | 4 |
2 files changed, 3 insertions, 3 deletions
diff --git a/content/math/legendre.cpp b/content/math/legendre.cpp index b85ea2a..80825ea 100644 --- a/content/math/legendre.cpp +++ b/content/math/legendre.cpp @@ -1,4 +1,4 @@ -ll legendre(ll a, ll p) { // p prim >= 2 +ll legendreS(ll a, ll p) { // p prim >= 2 ll s = powMod(a, p / 2, p); return s < 2 ? s : -1ll; } diff --git a/content/math/sqrtModCipolla.cpp b/content/math/sqrtModCipolla.cpp index c062646..a65e84c 100644 --- a/content/math/sqrtModCipolla.cpp +++ b/content/math/sqrtModCipolla.cpp @@ -1,7 +1,7 @@ -ll sqrtMod(ll a, ll p) {// teste mit Legendre ob Lösung existiert +ll sqrtMod(ll a, ll p) { // teste mit legendreS ob lösung existiert if (a < 2) return a; ll t = 0; - while (legendre((t*t-4*a) % p, p) >= 0) t = rng() % p; + while (legendreS((t*t-4*a) % p, p) >= 0) t = rng() % p; ll b = -t, c = -t, d = 1, m = p; for (m++; m /= 2; b = (a+a-b*b) % p, a = (a*a) % p) { if (m % 2) { |