feat: Implement scalar_to_base_neg3_le in Cairo1

[feltroidprime]

Counting the positive and negative multiplicities of the base (-3) decomposition of a u128 is needed for efficient elliptic curve scalar multiplication.

Implement the Cairo1 version of

https://github.com/keep-starknet-strange/garaga/blob/ecbcf0c0185a4e62b428edbf19b4cc9dbf2cb69c/hydra/hints/neg_3.py#L41-L64

Annotations were added on the python function to help you on the expected types.

FYI, the CairoZero version of it is here https://github.com/keep-starknet-strange/garaga/blob/ecbcf0c0185a4e62b428edbf19b4cc9dbf2cb69c/src/fustat/utils.cairo#L440 where the decomposition in digits happens inside the hint and is verified.

Since it is not possible in Cairo1, you must also implement the following function https://github.com/keep-starknet-strange/garaga/blob/ecbcf0c0185a4e62b428edbf19b4cc9dbf2cb69c/hydra/hints/neg_3.py#L1-L21 then count the positive and negative multiplicities.

However, the CairoZero version may still contains important information or clarifications.

• Be sure to implement this function for u128 in input.
• Use constant array of felt252 for powers of (-3) % STARK where STARK = 2^251+ 17*2^192 + 1. , similarly to the Cairo0 version.
• Write the utils functions in the contracts branch of the repo, under src/cairo/src/utils.cairo. Generate some test vectors with the python functions and test it. Try to automatize the creation of a test function to simplify its generation.
• Be as performant as possible. Benchmark your implementation.

[luiz-lvj]

Hi! I'm working on this issue

[feltroidprime]

closed by #127