Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[New Hints] 384_bit_prime_field.json #982

Closed
pefontana opened this issue Apr 13, 2023 · 0 comments · Fixed by #1004
Closed

[New Hints] 384_bit_prime_field.json #982

pefontana opened this issue Apr 13, 2023 · 0 comments · Fixed by #1004
Assignees
@fmoletta
Labels
whitelisted-hint Implementation of hint on whitelist directory

Comments

@pefontana
Copy link
Collaborator

pefontana commented Apr 13, 2023 •
edited by fmoletta
Loading

Implement the remaining hints in 384_bit_prime_field.json

These hints can be found here: https://github.com/NethermindEth/research-basic-Cairo-operations-big-integers/tree/main/lib

NewHint#3 UINT348_UNSIGNED_DIV_REM (PR 960)

assigned: @fmoletta
status: MERGED

                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack(ids.a, num_bits_shift = 128)",
                "div = pack(ids.div, num_bits_shift = 128)",
                "quotient, remainder = divmod(a, div)",
                "",
                "quotient_split = split(quotient, num_bits_shift=128, length=3)",
                "assert len(quotient_split) == 3",
                "",
                "ids.quotient.d0 = quotient_split[0]",
                "ids.quotient.d1 = quotient_split[1]",
                "ids.quotient.d2 = quotient_split[2]",
                "",
                "remainder_split = split(remainder, num_bits_shift=128, length=3)",
                "ids.remainder.d0 = remainder_split[0]",
                "ids.remainder.d1 = remainder_split[1]",
                "ids.remainder.d2 = remainder_split[2]"

NewHint#4 UINT348_UNSIGNED_DIV_REM_EXPANDED (PR 960)

assigned: @fmoletta
status: MERGED

                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack(ids.a, num_bits_shift = 128)",
                "b = pack(ids.b, num_bits_shift = 128)",
                "p = pack(ids.p, num_bits_shift = 128)",
                "",
                "res = (a - b) % p",
                "",
                "",
                "res_split = split(res, num_bits_shift=128, length=3)",
                "",
                "ids.res.d0 = res_split[0]",
                "ids.res.d1 = res_split[1]",
                "ids.res.d2 = res_split[2]"

NewHint#5 UINT384_DIV(Notes: not in the same lib as the others)

assigned: @fmoletta
status: REVIEW

                "from starkware.python.math_utils import div_mod",
                "",
                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack(ids.a, num_bits_shift = 128)",
                "b = pack(ids.b, num_bits_shift = 128)",
                "p = pack(ids.p, num_bits_shift = 128)",
                "# For python3.8 and above the modular inverse can be computed as follows:",
                "# b_inverse_mod_p = pow(b, -1, p)",
                "# Instead we use the python3.7-friendly function div_mod from starkware.python.math_utils",
                "
                ",
                "",
                "",
                "b_inverse_mod_p_split = split(b_inverse_mod_p, num_bits_shift=128, length=3)",
                "",
                "ids.b_inverse_mod_p.d0 = b_inverse_mod_p_split[0]",
                "ids.b_inverse_mod_p.d1 = b_inverse_mod_p_split[1]",
                "ids.b_inverse_mod_p.d2 = b_inverse_mod_p_split[2]"

NewHint#6 UNSIGNED_DIV_REM_UINT768_BY_UINT384 (Notes: here https://github.com/NethermindEth/research-basic-Cairo-operations-big-integers/blob/ed9a84694bcc56d3ee20ad07f8580e25d9eb8a3b/lib/uint384_extension.cairo)

assigned: @fmoletta
status: MERGED #983

                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift ",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "    ",
                "def pack_extended(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2, z.d3, z.d4, z.d5)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack_extended(ids.a, num_bits_shift = 128)",
                "div = pack(ids.div, num_bits_shift = 128)",
                "",
                "quotient, remainder = divmod(a, div)",
                "",
                "quotient_split = split(quotient, num_bits_shift=128, length=6)",
                "",
                "ids.quotient.d0 = quotient_split[0]",
                "ids.quotient.d1 = quotient_split[1]",
                "ids.quotient.d2 = quotient_split[2]",
                "ids.quotient.d3 = quotient_split[3]",
                "ids.quotient.d4 = quotient_split[4]",
                "ids.quotient.d5 = quotient_split[5]",
                "",
                "remainder_split = split(remainder, num_bits_shift=128, length=3)",
                "ids.remainder.d0 = remainder_split[0]",
                "ids.remainder.d1 = remainder_split[1]",
                "ids.remainder.d2 = remainder_split[2]"

NewHint#7 UINT384_SQRT (PR 960)

assigned: @fmoletta
status: MERGED

                "from starkware.python.math_utils import isqrt",
                "",
                "def split(num: int, num_bits_shift: int, length: int):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "a = pack(ids.a, num_bits_shift=128)",
                "root = isqrt(a)",
                "assert 0 <= root < 2 ** 192",
                "root_split = split(root, num_bits_shift=128, length=3)",
                "ids.root.d0 = root_split[0]",
                "ids.root.d1 = root_split[1]",
                "ids.root.d2 = root_split[2]"

NewHint#8 UINT_SIGNED_NN (PR 971)

assigned: @fmoletta
status: In MERGED

                "memory[ap] = 1 if 0 <= (ids.a.d2 % PRIME) < 2 ** 127 else 0"

NewHint#9 ADD_NO_UINT384_CHECK (PR 960)

assigned: @fmoletta
status: Review

                "sum_d0 = ids.a.d0 + ids.b.d0",
                "ids.carry_d0 = 1 if sum_d0 >= ids.SHIFT else 0",
                "sum_d1 = ids.a.d1 + ids.b.d1 + ids.carry_d0",
                "ids.carry_d1 = 1 if sum_d1 >= ids.SHIFT else 0",
                "sum_d2 = ids.a.d2 + ids.b.d2 + ids.carry_d1",
                "ids.carry_d2 = 1 if sum_d2 >= ids.SHIFT else 0"

NewHint#10 (Note: here https://github.com/NethermindEth/research-basic-Cairo-operations-big-integers/blob/fbf532651959f27037d70cd70ec6dbaf987f535c/lib/field_arithmetic.cairo)

assigned: @fmoletta
status: MERGED

                "from starkware.python.math_utils import is_quad_residue, sqrt",
                "",
                "def split(num: int, num_bits_shift: int = 128, length: int = 3):",
                "    a = []",
                "    for _ in range(length):",
                "        a.append( num & ((1 << num_bits_shift) - 1) )",
                "        num = num >> num_bits_shift",
                "    return tuple(a)",
                "",
                "def pack(z, num_bits_shift: int = 128) -> int:",
                "    limbs = (z.d0, z.d1, z.d2)",
                "    return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))",
                "",
                "",
                "generator = pack(ids.generator)",
                "x = pack(ids.x)",
                "p = pack(ids.p)",
                "",
                "success_x = is_quad_residue(x, p)",
                "root_x = sqrt(x, p) if success_x else None",
                "",
                "success_gx = is_quad_residue(generator*x, p)",
                "root_gx = sqrt(generator*x, p) if success_gx else None",
                "",
                "# Check that one is 0 and the other is 1",
                "if x != 0:",
                "    assert success_x + success_gx ==1",
                "",
                "# `None` means that no root was found, but we need to transform these into a felt no matter what",
                "if root_x == None:",
                "    root_x = 0",
                "if root_gx == None:",
                "    root_gx = 0",
                "ids.success_x = int(success_x)",
                "ids.success_gx = int(success_gx)",
                "split_root_x = split(root_x)",
                "split_root_gx = split(root_gx)",
                "ids.sqrt_x.d0 = split_root_x[0]",
                "ids.sqrt_x.d1 = split_root_x[1]",
                "ids.sqrt_x.d2 = split_root_x[2]",
                "ids.sqrt_gx.d0 = split_root_gx[0]",
                "ids.sqrt_gx.d1 = split_root_gx[1]",
                "ids.sqrt_gx.d2 = split_root_gx[2]"
@pefontana pefontana moved this to Todo in Starknet Apr 13, 2023
@pefontana pefontana added the whitelisted-hint Implementation of hint on whitelist directory label Apr 13, 2023
@fmoletta fmoletta self-assigned this Apr 13, 2023
This was referenced Apr 14, 2023
Closed
Closed
@pefontana pefontana moved this from Todo to In Progress in Starknet Apr 17, 2023
@fmoletta fmoletta linked a pull request Apr 21, 2023 that will close this issue
feat: Implement hints on field_arithmetic lib (Part 2) #1004
Merged
6 tasks
@github-project-automation github-project-automation bot moved this from In Progress to Done in Starknet Apr 22, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@fmoletta fmoletta

Labels
whitelisted-hint Implementation of hint on whitelist directory
Projects
Starknet
Status: Done
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

feat: Implement hints on field_arithmetic lib (Part 2) lambdaclass/cairo-vm
2 participants
@pefontana @fmoletta