Implement modular exponentiation in chiquito 2024

[leolara]

considering this is the implementation of fibonacci in chiquito:

machine fibo(signal n) (signal b) {
            // n and be are created automatically as shared
            // signals
            signal a;
            signal i;
           
            // there is always a state called initial
            // input signals get binded to the signal
            // in the initial state (first instance)
            state initial {
             signal c;
           
             i, a, b, c <== 1, 1, 1, 2;
           
             -> middle {
              a', b', n' <== b, c, n;
             }
            }
           
            state middle {
             signal c;
           
             c <== a + b;
           
             if i + 1 == n {
              -> final {
               i', b', n' <== i + 1, c, n
              }
             } else {
              -> middle {
               i', a', b', n' <== i + 1, b, c, n;
              }
             }
            }
           
            // there is always a state called final
            // output signals get automatically bindinded to the signals
            // with the same name in the final step (last instance)
            state final {
            }
           }

Implement modular exponentiation (https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Modular_Exponentiation) , low to high version.

Consider you do not need to do mod n because the field arithmetic does it intrinsically.

[leolara]

you can use vars like in circom