# BitVM3 Exponents Optimization

Inspired by the optimization of [Forward Adaptor Element Generation](https://www.notion.so/BitVM3-Discussion-211f0a489b98807182f7ea9e022c3a5b), we find another exponent's optimization for BitVM3, which reduces the computation of the whole circuit.
The origin design includes five small co-prime exponents as the public parameters. The smaller primes are better for performance, e.g., we can choose {3, 5, 7, 11, 13} as these exponents. The following is an example of the *AND* gate, where $T_{01} = c_0/c_{01}$ and $T_{02}=c_0/c_{02}$ are the adaptors.

$a_0^e\cdot b_0^{e_1} = c_0 \mod N$
$a_0^e\cdot b_1^{e_2} = c_{01} \mod N$
$a_1^e\cdot b_0^{e_3} = c_{02} \mod N$
$a_1^e\cdot b_1^{e_4} = c_1 \mod N$

We propose another method to calculate the output label, using three small primes. The example of the *AND* gate is following.

$a_0^{e} \cdot b_0^{e_1} = c_0 \mod N$
$a_0^{e} \cdot b_1^{e_2} = c_{01} \mod N$
$a_1^{e} \cdot b_0^{e_2} = c_{02} \mod N$
$a_1^{e} \cdot b_1^{e_1} = c_1 \mod N$

This method will eliminate two “bigger” primes, e.g., we can choose {3, 5, 7} as the public parameters. Assigning $e=3, e_1=5, e_2=7, e_3=11, e_4=13$, the table below shows the contrast of computation operations, where M represents multiplication operation, S represents square operation and the parentheses represents the cost of each exponent operation.

| | Origin | This method |
| ------------------------------ | ----------------- | ----------------- |
| computation per gate for row 1 | (1S+1M) + (2S+1M) | (1S+1M) + (2S+1M) |
| computation per gate for row 2 | (0) + (2S+2M) | (0) + (2S+2M) |
| computation per gate for row 3 | (1S+1M) + (1S+1M) | (1S+1M) + (1M) |
| computation per gate for row 4 | (0) + (1M) | (0) + (0) |
| total | 7S+7M | 6S+6M |