Add: Cairo0 IsQuadResidue Hint

[Tomi-3-0]

Implement Cairo0 isQuadResidue hint #243

This hint checks if an input value x is a quadratic residue and calculates its square root. If x is not a quadratic residue, it computes the square root of the result of dividing x by 3 i.e., √(x/3) or 3 * y² = x;

The hint utilizes Legendre() method which returns 1 if x is a quadratic residue (i.e., z is congruent to x mod q: z ≡ x² (mod q)) and 0 or -1 if it isn't. Additionally, it returns 1 for input values of 1 or 0 for input values of 0, as 0² is always 0, and 1² is always 1, irrespective of the modulus.

Link to other helper methods used:

• Sqrt() function implementation
• Div() function implementation

[cicr99]

This PR is blocked due to issue #338

[rodrigo-pino]

@Tomi-3-0 can you explain what is the issue your having here. I don't understand why you cannot fix it?

Converting them to uint256 and finding the sqrt of it good enough? Why is it that using the fp.Element sqrt doesn't work

[Tomi-3-0]

@Tomi-3-0 can you explain what is the issue your having here. I don't understand why you cannot fix it?

Converting them to uint256 and finding the sqrt of it good enough? Why is it that using the fp.Element sqrt doesn't work

@rodrigo-pino sqrt function from the uint256 library does not perform modular arithmetic as required by the hint

[rodrigo-pino]

What do you mean modular arithmetic? Maybe I am missing something, but what operation do you need to do exactly that cannot be composed by the existing arithmetic operations of the uint256/fp library

[Tomi-3-0]

What do you mean modular arithmetic? Maybe I am missing something, but what operation do you need to do exactly that cannot be composed by the existing arithmetic operations of the uint256/fp library

@rodrigo-pino The fp library's Sqrt function computes the square root modulo a prime q. It calculates the integer value z such that z² ≡ x (mod q). For example, 55 ≡ 16 (mod 13), but 55 ≇ 16 (mod 11) since 39 is a multiple of 13 but not of 11 let's say x = 81 and q = 0x800000000000011000000000000000000000000000000000000000000000001. If we calculate the square root of 81 modulo q using the fp library's Sqrt function, it will provide the result according to modular arithmetic rules.

On the other hand, the uint256 library's sqrt function computes the square root in a traditional mathematical sense, disregarding modular arithmetic. For example, sqrt(81) would return 9.

The issue here arises when the results obtained for some values differ from those obtained from the same function in other contexts, such as Lambdaclass's VM

[rodrigo-pino]

Hey @Tomi-3-0 I understand how the uint256 and the felt arithmetic operations work. What I am asking is what operation you want to do?

What is the arithmetic operation that should be performed to get to the right value?

I don't think it is a blocker, unless you require an operation that re-defines the math operators (+, -, etc...) , it should be achieved by a finite combination of your classic arithmetic operators. So please tell me what is the operation and maybe the solution is for us to define it.

[Tomi-3-0]

Hey @Tomi-3-0 I understand how the uint256 and the felt arithmetic operations work. What I am asking is what operation you want to do?

What is the arithmetic operation that should be performed to get to the right value?

I don't think it is a blocker, unless you require an operation that re-defines the math operators (+, -, etc...) , it should be achieved by a finite combination of your classic arithmetic operators. So please tell me what is the operation and maybe the solution is for us to define it.

Hi @rodrigo-pino ,Thanks for your time.

The arithmetic operation to be performed is to

• find the sqrt of an integer divided by 3 i.e √(x÷3) if the integer isn't a quadratic residue OR
• find the sqrt of an integer (√x) if it's a quadratic residue.

I use the Legendre() method to check if an integer is a quadratic residue

[rodrigo-pino]

Hey @Tomi-3-0 I understand how the uint256 and the felt arithmetic operations work. What I am asking is what operation you want to do? What is the arithmetic operation that should be performed to get to the right value? I don't think it is a blocker, unless you require an operation that re-defines the math operators (+, -, etc...) , it should be achieved by a finite combination of your classic arithmetic operators. So please tell me what is the operation and maybe the solution is for us to define it.

Hi @rodrigo-pino ,Thanks for your time.

The arithmetic operation to be performed is to

* find the sqrt of an integer divided by 3 i.e `√(x÷3)` if the integer isn't a quadratic residue
  OR

* find the sqrt of an integer `(√x)` if it's a quadratic residue.

I use the Legendre() method to check if an integer is a quadratic residue

@Tomi-3-0 thanks for answering. I still didn't understand the issue so I looked into other VMs Using felt sqrt is a must from what I've seen. From the failing test I get that from the possible values you're not getting the one that you're expected. In this case "-10" which is not technically wrong though.

[Tomi-3-0]

Hey @Tomi-3-0 I understand how the uint256 and the felt arithmetic operations work. What I am asking is what operation you want to do? What is the arithmetic operation that should be performed to get to the right value? I don't think it is a blocker, unless you require an operation that re-defines the math operators (+, -, etc...) , it should be achieved by a finite combination of your classic arithmetic operators. So please tell me what is the operation and maybe the solution is for us to define it.

Hi @rodrigo-pino ,Thanks for your time.

The arithmetic operation to be performed is to

* find the sqrt of an integer divided by 3 i.e `√(x÷3)` if the integer isn't a quadratic residue
  OR

* find the sqrt of an integer `(√x)` if it's a quadratic residue.

I use the Legendre() method to check if an integer is a quadratic residue

@Tomi-3-0 thanks for answering. I still didn't understand the issue so I looked into other VMs Using felt sqrt is a must from what I've seen. From the failing test I get that from the possible values you're not getting the one that you're expected. In this case "-10" which is not technically wrong though.

@rodrigo-pino Exactly. And for some other values too e.g 762 the results are different too. Thanks

[TAdev0]

Hi @Tomi-3-0 , do you have any update on this?

I'd like to understand what the issue is exactly. You don't get the same result as the python cairo vm for that hint, because of sqrt function in the hint. Currently, your last commit calculates sqrt on uint256, so the result will obviously be different as it doesnt calculate the square root in a finite field. square roots in finite fields can produce multiple results. I suppose then that we just need to find an implementation in Go that matches the one used by the python vm ?

[Tomi-3-0]

Hi @Tomi-3-0 , do you have any update on this?

I'd like to understand what the issue is exactly. You don't get the same result as the python cairo vm for that hint, because of sqrt function in the hint. Currently, your last commit calculates sqrt on uint256, so the result will obviously be different as it doesnt calculate the square root in a finite field. square roots in finite fields can produce multiple results. I suppose then that we just need to find an implementation in Go that matches the one used by the python vm ?

Hello @TAdev0 . Thanks for checking this out. My previous implementation calculates the square root in a finite field, but there were still differences in the results.

I also suppose that finding a matching implementation/or creating our own implementation might be the solution

I have to mention also that the implementations of the sqrt function in the go and python libraries seem to follow the same logic (Tonelli-Shanks algo)

[TAdev0]

@Tomi-3-0 ok it's clear! Do you want to investigate and try with one or 2 other libraries? I can also work on it, as you prefer. If you find a library that matches, then we can probably spot the difference in the implementation

Which cases exactly had mismatch in values? Did you also have succcessful tests for some values that matched correctly when testing the whole hint?

[Tomi-3-0]

@Tomi-3-0 ok it's clear! Do you want to investigate and try with one or 2 other libraries? I can also work on it, as you prefer. If you find a library that matches, then we can probably spot the difference in the implementation

Which cases exactly had mismatch in values? Did you also have succcessful tests for some values that matched correctly when testing the whole hint?

@TAdev0 yes most values matched correctly. I would appreciate some help. Thanks

[TAdev0]

@Tomi-3-0 ok great, will look into it tomorrow or the day after :) Could you just indicate me (if you remember) some values that didnt work?

[Tomi-3-0]

@Tomi-3-0 ok great, will look into it tomorrow or the day after :) Could you just indicate me (if you remember) some values that didnt work?

@TAdev0 151461 is a good test value

[TAdev0]

hey @Tomi-3-0 I tried a few things and here is where I am :

• currently, the implementation returns P - result, instead of result , both being a valide square root of x , when x is a quadratic residue in the context of the stark field

• I tried using big/math that implements ModSqrt , which uses under the hood modSqrtTonelliShanks , if p is not 3 mod 4 or 5 mod 8 (in these cases, a faster method is used). WIth this implementation, i have the same result as the one with sqrt method of Element library

func newIsQuadResidueHint(x, y hinter.ResOperander) hinter.Hinter {
	return &GenericZeroHinter{
		Name: "IsQuadResidue",
		Op: func(vm *VM.VirtualMachine, _ *hinter.HintRunnerContext) error {
			//> from starkware.crypto.signature.signature import FIELD_PRIME
			//>	from starkware.python.math_utils import div_mod, is_quad_residue, sqrt
			//>	x = ids.x
			//>	if is_quad_residue(x, FIELD_PRIME):
			//>		ids.y = sqrt(x, FIELD_PRIME)
			//>	else:
			//>		ids.y = sqrt(div_mod(x, 3, FIELD_PRIME), FIELD_PRIME)

			x, err := hinter.ResolveAsFelt(vm, x)
			if err != nil {
				return err
			}

			yAddr, err := y.GetAddress(vm)
			if err != nil {
				return err
			}

			xBigInt := math_utils.AsInt(x)

			var value = memory.MemoryValue{}

			if x.IsZero() || x.IsOne() {
				value = memory.MemoryValueFromFieldElement(x)

			} else {
				var result *fp.Element = new(fp.Element)

				if x.Legendre() == 1 {
					// result = x.Sqrt(x)

					var primeBigInt = new(big.Int)
					primeBigInt, ok := primeBigInt.SetString("3618502788666131213697322783095070105623107215331596699973092056135872020481", 10)
					if !ok {
						panic("")
					}

					var tempResult = new(big.Int)
					tempResult.ModSqrt(&xBigInt, primeBigInt)

					result.SetBigInt(tempResult)

				} else {
					result = x.Sqrt(new(fp.Element).Div(x, new(fp.Element).SetUint64(3)))
				}

				value = memory.MemoryValueFromFieldElement(result)
			}

			return vm.Memory.WriteToAddress(&yAddr, &value)
		},
	}
}

My guess (not necessarily right) is that both methods return the highest valid result , instead of the smallest.

[TAdev0]

@Tomi-3-0 , the following implementation passes all the tests :

func newIsQuadResidueHint(x, y hinter.ResOperander) hinter.Hinter {
	return &GenericZeroHinter{
		Name: "IsQuadResidue",
		Op: func(vm *VM.VirtualMachine, _ *hinter.HintRunnerContext) error {
			//> from starkware.crypto.signature.signature import FIELD_PRIME
			//>	from starkware.python.math_utils import div_mod, is_quad_residue, sqrt
			//>	x = ids.x
			//>	if is_quad_residue(x, FIELD_PRIME):
			//>		ids.y = sqrt(x, FIELD_PRIME)
			//>	else:
			//>		ids.y = sqrt(div_mod(x, 3, FIELD_PRIME), FIELD_PRIME)

			x, err := hinter.ResolveAsFelt(vm, x)
			if err != nil {
				return err
			}

			yAddr, err := y.GetAddress(vm)
			if err != nil {
				return err
			}

			xBigInt := math_utils.AsInt(x)

			var value = memory.MemoryValue{}

			if x.IsZero() || x.IsOne() {
				value = memory.MemoryValueFromFieldElement(x)

			} else {
				var result *fp.Element = new(fp.Element)

				if x.Legendre() == 1 {
					// result = x.Sqrt(x)

					var primeBigInt = new(big.Int)
					primeBigInt, ok := primeBigInt.SetString("3618502788666131213697322783095070105623107215331596699973092056135872020481", 10)
					if !ok {
						panic("")
					}

					var tempResult = new(big.Int)
					tempResult.ModSqrt(&xBigInt, primeBigInt)
					tempResult.Sub(primeBigInt, tempResult)

					result.SetBigInt(tempResult)

				} else {
					result = x.Sqrt(new(fp.Element).Div(x, new(fp.Element).SetUint64(3)))
				}

				value = memory.MemoryValueFromFieldElement(result)
			}

			return vm.Memory.WriteToAddress(&yAddr, &value)
		},
	}
}

What i did is computing P - result withing result being the result of the ModSqrt of the Big package.

Now, we need to make sure this implementation works in all situations. Maybe the best solution would be :

• check whether the result of ModSqrt is greater or lower than P / 2
• compute P - result only if greater

what do you think?

[Tomi-3-0]

Great job @TAdev0 . Give me a minute to check this out. On first glance, seems like you're only computing P - result when the input x is a quadratic residue.

Did you compare your results with the result of let's say the python VM?

Because calling the sqrt() funtion alone from the element library on an input e.g x.sqrt() gave results that differ. You can test this with input values of 9 and 100 for example.

[TAdev0]

i have not extensively test with the python vm for now. will do it in the weekend.

yeah i added P-result computation to get the lowest valid result for the square root.

[Tomi-3-0]

i have not extensively test with the python vm for now. will do it in the weekend.

yeah i added P-result computation to get the lowest valid result for the square root.

Cool. I would also be working on this. Thank you @TAdev0 💥

[TAdev0]

here is a cairo file you can use to test :

%builtins output
from starkware.cairo.common.serialize import serialize_word
from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.bool import FALSE, TRUE


// Returns TRUE if `x` is a quadratic residue modulo the STARK prime. Returns FALSE otherwise.
// Returns TRUE on 0.
@known_ap_change
func is_quad_residue(x: felt) -> felt {
    alloc_locals;
    local y;
    %{
        from starkware.crypto.signature.signature import FIELD_PRIME
        from starkware.python.math_utils import div_mod, is_quad_residue, sqrt

        x = ids.x
        if is_quad_residue(x, FIELD_PRIME):
            ids.y = sqrt(x, FIELD_PRIME)
            print(ids.y)
        else:
            ids.y = sqrt(div_mod(x, 3, FIELD_PRIME), FIELD_PRIME)
            print(ids.y)
    %}
    // Relies on the fact that 3 is not a quadratic residue modulo the prime, so for every field
    // element x, either:
    //   * x is a quadratic residue and there exists y such that y^2 = x.
    //   * x is not a quadratic residue and there exists y such that 3 * y^2 = x.
    tempvar y_squared = y * y;
    if (y_squared == x) {
        ap += 1;
        return TRUE;
    } else {
        assert 3 * y_squared = x;
        return FALSE;
    }
}

func fill_array(array_start: felt*, iter: felt) -> () {
    if (iter == 10) {
        return ();
    }
    assert array_start[iter] = iter;
    return fill_array(array_start, iter + 1);
}

func check_quad_res{output_ptr: felt*}(inputs: felt*, expected: felt*, iter: felt) {
    if (iter == 10) {
        return ();
    }
    serialize_word(inputs[iter]);
    serialize_word(expected[iter]);

    assert is_quad_residue(inputs[iter]) = expected[iter];
    return check_quad_res(inputs, expected, iter + 1);
}

func main{output_ptr: felt*}() {
    alloc_locals;
    let (inputs: felt*) = alloc();
    fill_array(inputs, 0);

    let (expected: felt*) = alloc();
    assert expected[0] = 1;
    assert expected[1] = 1;
    assert expected[2] = 1;
    assert expected[3] = 0;
    assert expected[4] = 1;
    assert expected[5] = 1;
    assert expected[6] = 0;
    assert expected[7] = 1;
    assert expected[8] = 1;
    assert expected[9] = 1;

    check_quad_res(inputs, expected, 0);

    return ();
}

I added print(ids.y) to print the result of the sqrt. Indeed, with the python VM, sqrt(9) returns 3 , not P-3 . So my modification works correctly in this situation. We should check all situations / edge cases to make sure its ok like this

[TAdev0]

just check with the value 2

			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(2)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("1120755473020101814179135767224264702961552391386192943129361948990833801454")),
			},

1120755473020101814179135767224264702961552391386192943129361948990833801454 is what the python vm returns for 2

here , we fail, and we have 2497747315646029399518187015870805402661554823945403756843730107145038219027

this means here, we dont need to do P - result I think we just need to a check that result < P - result , and if not, apply P - result , and then we're good

[TAdev0]

final implementation:

func newIsQuadResidueHint(x, y hinter.ResOperander) hinter.Hinter {
	return &GenericZeroHinter{
		Name: "IsQuadResidue",
		Op: func(vm *VM.VirtualMachine, _ *hinter.HintRunnerContext) error {
			//> from starkware.crypto.signature.signature import FIELD_PRIME
			//>	from starkware.python.math_utils import div_mod, is_quad_residue, sqrt
			//>	x = ids.x
			//>	if is_quad_residue(x, FIELD_PRIME):
			//>		ids.y = sqrt(x, FIELD_PRIME)
			//>	else:
			//>		ids.y = sqrt(div_mod(x, 3, FIELD_PRIME), FIELD_PRIME)

			x, err := hinter.ResolveAsFelt(vm, x)
			if err != nil {
				return err
			}

			yAddr, err := y.GetAddress(vm)
			if err != nil {
				return err
			}

			xBigInt := math_utils.AsInt(x)

			var value = memory.MemoryValue{}

			if x.IsZero() || x.IsOne() {
				value = memory.MemoryValueFromFieldElement(x)

			} else {
				var result *fp.Element = new(fp.Element)

				if x.Legendre() == 1 {
					// result = x.Sqrt(x)

					var primeBigInt = new(big.Int)
					primeBigInt, ok := primeBigInt.SetString("3618502788666131213697322783095070105623107215331596699973092056135872020481", 10)
					if !ok {
						panic("")
					}

					halfPrimeBigInt := new(big.Int).Rsh(primeBigInt, 1)

					var tempResult = new(big.Int)
					tempResult.ModSqrt(&xBigInt, primeBigInt)

					if tempResult.Cmp(halfPrimeBigInt) > 0 {
						tempResult.Sub(primeBigInt, tempResult)
					}

					result.SetBigInt(tempResult)

				} else {
					result = x.Sqrt(new(fp.Element).Div(x, new(fp.Element).SetUint64(3)))
				}

				value = memory.MemoryValueFromFieldElement(result)
			}

			return vm.Memory.WriteToAddress(&yAddr, &value)
		},
	}
}

and the tests, with value from the python vm :

		{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(0)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltInt64(0)),
			},
			// Test case: x is 1
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(1)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltInt64(1)),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(2)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("1120755473020101814179135767224264702961552391386192943129361948990833801454")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(3)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("1")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(4)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("2")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(5)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("703125680814918687568381966029303999302590701505467922907419583337579557417")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(6)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("1120755473020101814179135767224264702961552391386192943129361948990833801454")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(7)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("209880913220488156313834499058596184255382000503803956865172539718143124843")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(8)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("1376991842625927585339051248646540699700002432559210813714368158154204417573")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(9)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltInt64(3)),
			},

everything passes :)

[Tomi-3-0]

Great job! I will test on a few other corner values and give a feedback asap

[Tomi-3-0]

final implementation:

func newIsQuadResidueHint(x, y hinter.ResOperander) hinter.Hinter {
	return &GenericZeroHinter{
		Name: "IsQuadResidue",
		Op: func(vm *VM.VirtualMachine, _ *hinter.HintRunnerContext) error {
			//> from starkware.crypto.signature.signature import FIELD_PRIME
			//>	from starkware.python.math_utils import div_mod, is_quad_residue, sqrt
			//>	x = ids.x
			//>	if is_quad_residue(x, FIELD_PRIME):
			//>		ids.y = sqrt(x, FIELD_PRIME)
			//>	else:
			//>		ids.y = sqrt(div_mod(x, 3, FIELD_PRIME), FIELD_PRIME)

			x, err := hinter.ResolveAsFelt(vm, x)
			if err != nil {
				return err
			}

			yAddr, err := y.GetAddress(vm)
			if err != nil {
				return err
			}

			xBigInt := math_utils.AsInt(x)

			var value = memory.MemoryValue{}

			if x.IsZero() || x.IsOne() {
				value = memory.MemoryValueFromFieldElement(x)

			} else {
				var result *fp.Element = new(fp.Element)

				if x.Legendre() == 1 {
					// result = x.Sqrt(x)

					var primeBigInt = new(big.Int)
					primeBigInt, ok := primeBigInt.SetString("3618502788666131213697322783095070105623107215331596699973092056135872020481", 10)
					if !ok {
						panic("")
					}

					halfPrimeBigInt := new(big.Int).Rsh(primeBigInt, 1)

					var tempResult = new(big.Int)
					tempResult.ModSqrt(&xBigInt, primeBigInt)

					if tempResult.Cmp(halfPrimeBigInt) > 0 {
						tempResult.Sub(primeBigInt, tempResult)
					}

					result.SetBigInt(tempResult)

				} else {
					result = x.Sqrt(new(fp.Element).Div(x, new(fp.Element).SetUint64(3)))
				}

				value = memory.MemoryValueFromFieldElement(result)
			}

			return vm.Memory.WriteToAddress(&yAddr, &value)
		},
	}
}

and the tests, with value from the python vm :

		{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(0)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltInt64(0)),
			},
			// Test case: x is 1
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(1)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltInt64(1)),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(2)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("1120755473020101814179135767224264702961552391386192943129361948990833801454")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(3)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("1")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(4)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("2")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(5)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("703125680814918687568381966029303999302590701505467922907419583337579557417")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(6)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("1120755473020101814179135767224264702961552391386192943129361948990833801454")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(7)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("209880913220488156313834499058596184255382000503803956865172539718143124843")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(8)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltString("1376991842625927585339051248646540699700002432559210813714368158154204417573")),
			},
			{
				operanders: []*hintOperander{
					{Name: "y", Kind: uninitialized},
					{Name: "x", Kind: fpRelative, Value: feltInt64(9)},
				},
				makeHinter: func(ctx *hintTestContext) hinter.Hinter {
					return newIsQuadResidueHint(ctx.operanders["x"], ctx.operanders["y"])
				},
				check: varValueEquals("y", feltInt64(3)),
			},

everything passes :)

[Tomi-3-0]

@TAdev0 passes all tests! Made a few design changes, but the same logic. I think this is ready for review.

THANKS!

[cicr99]

Good work! 🎉