bug: EXP will run out of resources on high exponent

[greged93]

Bug Report

Kakarot version: ee6458a

Current behavior:
Given a high exponent value when calling the EXP opcode, the transaction will run out of resources. This is due to the fact that we don't use the fast powering algorithm for high exponent values. See code below:

kakarot/src/kakarot/instructions/stop_and_arithmetic_operations.cairo

Lines 462 to 466 in 95df46c

	let (b_minus_one) = uint256_sub(b, one_uint);
	let temp_pow = internal_exp(a=a, b=b_minus_one);
	let (res, _) = uint256_mul(a, temp_pow);
	return res;
	}

Expected behavior:
Exponentiation should work for high value of exponent.

Steps to reproduce:

• clone ef-tests: https://github.com/kkrt-labs/ef-tests
• generate katana dump of kakarot system and move the .katana folder to your ef-tests directory
• run

TARGET=expPower256_d0g0v0_Shanghai cargo test -p ef-testing --features ef-tests -- --nocapture

Failing output should be:

2023-08-25T09:40:07.242339Z  WARN katana_core::backend::executor: Transaction execution error: "Error in the called contract (0x04e2460d0debdacdde372cb598b4e4403939ca112c8720e1c2aca13f6ac09b9a):
Error at pc=0:7:
Got an exception while executing a hint.
Cairo traceback (most recent call last):
Unknown location (pc=0:163)
Unknown location (pc=0:149)

Error in the called contract (0x04e2460d0debdacdde372cb598b4e4403939ca112c8720e1c2aca13f6ac09b9a):
Error at pc=0:31:
Got an exception while executing a hint.
Cairo traceback (most recent call last):
Unknown location (pc=0:4606)
Unknown location (pc=0:4545)
Unknown location (pc=0:4374)
Unknown location (pc=0:376)

Error in the called contract (0x049c085e55e5ab05ea46e16706720852421e86c1f8aeeab2be257313c4e290f4):
Error at pc=0:490:
Could not reach the end of the program. RunResources has no remaining steps.
Cairo traceback (most recent call last):
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18022)
Unknown location (pc=0:17250)
Unknown location (pc=0:9424)
"
[!] Case ~/code/rust/ef-tests/crates/ef-testing/ethereum-tests/BlockchainTests/GeneralStateTests/VMTests/vmArithmeticTest/expPower256.json failed (description: expPower256): Test failed: failed test expPower256_d0g0v0_Shanghai: expected storage value 0x0000000000000000000000000000000000000000000000000000000000000001, got 0x0000000000000000000000000000000000000000000000000000000000000000