IntModSqrt
Description
Compute a modular square root.
Parameters
| Name | Direction | Description |
|---|---|---|
result |
out | Destination for the root |
value |
in | Value whose square root is requested |
modulus |
in | Modulus |
Usage example (from documentation)
bool ok = IntModSqrt(&root, &value, &modulus);Success
Returns true when a modular square root exists.
Failure
Returns false otherwise.
Usage example (Cross-references)
Usage examples (Cross-references)
- In
Int.c:2760:
}
bool IntModSqrt(Int *result, const Int *value, const Int *modulus) {
ValidateInt(result);
ValidateInt(value);- In
Math.c:841:
bool test_int_mod_sqrt(void) {
WriteFmt("Testing IntModSqrt\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:850:
Int check = IntInit(&alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
IntSquareMod(&check, &root, &mod);
result = result && (IntCompare(&check, 10) == 0);- In
Math.c:863:
bool test_int_mod_sqrt_no_solution(void) {
WriteFmt("Testing IntModSqrt no-solution case\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:871:
Int root = IntFrom(99, &alloc.base);
bool result = !IntModSqrt(&root, &value, &mod);
result = result && (IntCompare(&root, 99) == 0);- In
Math.c:1143:
// ---------------------------------------------------------------------------
bool test_m1_modsqrt_p3mod4_residue(void) {
WriteFmt("Testing IntModSqrt p==3 mod 4 residue (p=7,a=2)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1152:
Int check = IntInit(&alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
IntSquareMod(&check, &root, &mod);- In
Math.c:1174:
// Kills the Jacobi guard (2471) and the modulus==2 misfire (2452).
bool test_m1_modsqrt_p3mod4_nonresidue_preserves_result(void) {
WriteFmt("Testing IntModSqrt p==3 mod 4 non-residue (p=7,a=3)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1182:
Int root = IntFrom(99, &alloc.base);
bool result = !IntModSqrt(&root, &value, &mod);
result = result && (IntCompare(&root, 99) == 0);- In
Math.c:1200:
// ---------------------------------------------------------------------------
bool test_m1_modsqrt_p1mod4_tonelli_deep(void) {
WriteFmt("Testing IntModSqrt Tonelli deep (p=17,a=2,m=4)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1209:
Int check = IntInit(&alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
IntSquareMod(&check, &root, &mod);- In
Math.c:1230:
// IntSquareMod (2647), and m = i (2720).
bool test_m1_modsqrt_p1mod4_tonelli_jloop(void) {
WriteFmt("Testing IntModSqrt Tonelli j-loop (p=17,a=4)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1239:
Int check = IntInit(&alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
IntSquareMod(&check, &root, &mod);- In
Math.c:1260:
// 2647, 2720, 2723).
bool test_m1_modsqrt_p1mod4_tonelli_multi_outer(void) {
WriteFmt("Testing IntModSqrt Tonelli multi-outer (p=97,a=3)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1269:
Int check = IntInit(&alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
IntSquareMod(&check, &root, &mod);- In
Math.c:1289:
// the loop counters (i, j) and the m contraction across iterations.
bool test_m1_modsqrt_p1mod4_tonelli_deepest(void) {
WriteFmt("Testing IntModSqrt Tonelli deepest (p=257,a=2,m=8)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1298:
Int check = IntInit(&alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
IntSquareMod(&check, &root, &mod);- In
Math.c:1315:
// p = 13 -> q=3, m=2. a = 10 -> root 6 or 7 (both square to 10 mod 13).
bool test_m1_modsqrt_p1mod4_tonelli_shallow(void) {
WriteFmt("Testing IntModSqrt Tonelli (p=13,a=10,m=2)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1324:
Int check = IntInit(&alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
IntSquareMod(&check, &root, &mod);- In
Math.c:1341:
// Kills the Jacobi guard reached before the Tonelli machinery (2471).
bool test_m1_modsqrt_p1mod4_nonresidue_preserves_result(void) {
WriteFmt("Testing IntModSqrt p==1 mod 4 non-residue (p=13,a=2)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1349:
Int root = IntFrom(99, &alloc.base);
bool result = !IntModSqrt(&root, &value, &mod);
result = result && (IntCompare(&root, 99) == 0);- In
Math.c:1364:
// ---------------------------------------------------------------------------
bool test_m1_modsqrt_zero_value_sets_result_zero(void) {
WriteFmt("Testing IntModSqrt value 0 sets result 0\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1372:
Int root = IntFrom(99, &alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
// result overwritten to exactly 0 (not the 99 sentinel).
result = result && (IntCompare(&root, 0) == 0);- In
Math.c:1387:
// reduction (2441) feeding the a==0 fast path.
bool test_m1_modsqrt_multiple_of_modulus_sets_zero(void) {
WriteFmt("Testing IntModSqrt 21 mod 7 -> root 0\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1395:
Int root = IntFrom(99, &alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
result = result && (IntCompare(&root, 0) == 0);- In
Math.c:1411:
// ---------------------------------------------------------------------------
bool test_m1_modsqrt_modulus_two_sets_result(void) {
WriteFmt("Testing IntModSqrt modulus 2 (a=5 -> root 1)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1419:
Int root = IntFrom(99, &alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
result = result && (IntCompare(&root, 1) == 0);- In
Math.c:1434:
// ---------------------------------------------------------------------------
bool test_m1_modsqrt_even_modulus_fails(void) {
WriteFmt("Testing IntModSqrt even modulus 8 fails\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1442:
Int root = IntFrom(99, &alloc.base);
bool result = !IntModSqrt(&root, &value, &mod);
result = result && (IntCompare(&root, 99) == 0);- In
Math.c:1455:
// Kills the !prime guard / prime detection at lines 2458, 2464.
bool test_m1_modsqrt_composite_modulus_fails(void) {
WriteFmt("Testing IntModSqrt composite modulus 9 fails\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1463:
Int root = IntFrom(99, &alloc.base);
bool result = !IntModSqrt(&root, &value, &mod);
result = result && (IntCompare(&root, 99) == 0);- In
Math.c:1477:
// ---------------------------------------------------------------------------
bool test_m1_modsqrt_zero_modulus_fails_preserves_result(void) {
WriteFmt("Testing IntModSqrt zero modulus fails\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1485:
Int root = IntFrom(99, &alloc.base);
bool result = !IntModSqrt(&root, &value, &mod);
result = result && (IntCompare(&root, 99) == 0);- In
Math.c:1501:
// ---------------------------------------------------------------------------
bool test_m1_modsqrt_value_reduced_before_root(void) {
WriteFmt("Testing IntModSqrt reduces value first (23 mod 7)\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:1510:
Int check = IntInit(&alloc.base);
bool result = IntModSqrt(&root, &value, &mod);
IntSquareMod(&check, &root, &mod);- In
Math.c:2978:
// iterates. sqrt(2) mod 17 = 6 (6^2 = 36 = 2 mod 17).
bool test_fe_2596_mod_sqrt_tonelli_inner(void) {
WriteFmt("Testing IntModSqrt Tonelli-Shanks inner loop\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Math.c:2987:
Int check = IntInit(&alloc.base);
bool ok = IntModSqrt(&root, &value, &mod);
IntSquareMod(&check, &root, &mod);
bool result = ok && (IntCompare(&check, 2) == 0);- In
Math.c:4417:
Int r = IntFrom(9u, a);
bool ok = IntModSqrt(&r, &v, &m);
u64 rv = IntToU64(&r);
ok = ok && (rv * rv) % 7u == 2u;- In
Math.c:4440:
Int r = IntFrom(9u, a);
bool ok = IntModSqrt(&r, &v, &m);
u64 rv = IntToU64(&r);
ok = ok && (rv * rv) % 17u == 2u;- In
Math.c:4462:
Int r = IntFrom(9u, a);
bool ok = IntModSqrt(&r, &v, &m);
u64 rv = IntToU64(&r);
ok = ok && (rv * rv) % 41u == 10u;- In
Math.c:4483:
Int r = IntFrom(9u, a);
bool ok = IntModSqrt(&r, &v, &m) && IntIsZero(&r);
IntDeinit(&v);- In
Math.c:4503:
Int r = IntFrom(9u, a);
bool ok = IntModSqrt(&r, &v, &m) && IntToU64(&r) == 1u;
IntDeinit(&v);- In
Math.c:4523:
Int r = IntFrom(9u, a);
bool ok = !IntModSqrt(&r, &v, &m);
IntDeinit(&v);- In
Math.c:4542:
Int r = IntFrom(9u, a);
bool ok = !IntModSqrt(&r, &v, &m);
IntDeinit(&v);- In
Math.c:4561:
Int r = IntFrom(9u, a);
bool ok = !IntModSqrt(&r, &v, &m);
IntDeinit(&v);- In
Math.c:4707:
Int r = IntFrom(9u, a);
bool found = IntModSqrt(&r, &v, &m);
if (found) {
u64 rv = IntToU64(&r);- In
Math.c:4753:
Int check = IntFrom(0u, alloc);
bool ok = IntModSqrt(&root, &value, &modulus);
ok = ok && IntSquareMod(&check, &root, &modulus);
ok = ok && IntCompare(&check, 9u) == 0;- In
Math.c:4776:
Int check = IntFrom(0u, alloc);
bool ok = IntModSqrt(&root, &value, &modulus);
ok = ok && IntSquareMod(&check, &root, &modulus);
ok = ok && IntCompare(&check, 2u) == 0;
Last updated on