Optimizations for modular arithmetic

[hecmas]

Description

In the rom, almost each of the functions involving modular arithmetic can be highly optimized. In particular, the (in average) two arithmetic and one binary operations needed for computing modular operations could be interchanged by two binary operations, which cost half the "price".

Example

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; POST: The result is in the range [0,BN254_P)
;;
;; subFpBN254:
;;             in: A,C ∈ Fp
;;             out: C = A - C (mod BN254_P) ∈ Fp
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
subFpBN254:
        ; 0] Negate C
        A => D
        %BN254_P => A
        C => B
        $ => C      :SUB
        D => A

        ; 1] Compute and check the sub over Z
        ; A·[1] + [BN254_P-C] = [D]·2²⁵⁶ + [E]
        1 => B
        $${var _subFpBN254_AC = A + C}
        ${_subFpBN254_AC >> 256} => D
        ${_subFpBN254_AC} => E :ARITH

        ; 2] Check it over Fp, that is, it must be satisfied that:
        ; [BN254_P]·[(A - C) / p] + [(A - C) % p] = D·2²⁵⁶ + E
        ; where C < BN254_P
        %BN254_P => A
        ${_subFpBN254_AC / const.BN254_P} => B        ; quotient  (256 bits)
        ${_subFpBN254_AC % const.BN254_P} => C        ; residue (256 bits)
        E :ARITH

        ; 3] Check that the result is lower than BN254_P
        A => B
        C => A
        1       :LT, RETURN

is using two binary and two arithmetic operations.

It could be optimized as follows:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  PRE: A,C are assumed to be in the range [0,BN254_P)
;; POST: The result is in the range [0,BN254_P)
;;
;; subFpBN254:
;;             in: A,C ∈ Fp
;;             out: C = A - C (mod BN254_P) ∈ Fp
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

subFpBN254:
        C => B
        $ => C  :SUB, JMPC(subFpBN254_addp)
                :RETURN
subFpBN254_addp:
        ; NOTE: 5·BN254_P < 2²⁵⁶ < 6·BN254_P

        B => C ; save for later use

        %BN254_P => B
        $ => A  :ADD ; It cannot overflow under the PRE condition

        C => B
        $ => C  :SUB, RETURN

which, in the worst case, uses 3 binaries.

Counters

Counters went from:

{
  cntArith: 53585n,
  cntBinary: 52558n,
  cntKeccakF: 0n,
  cntSha256F: 0n,
  cntMemAlign: 0n,
  cntPoseidonG: 0n,
  cntPaddingPG: 0n,
  cntSteps: 442368
}

to

{
  cntArith: 40173n,
  cntBinary: 53050n,
  cntKeccakF: 0n,
  cntSha256F: 0n,
  cntMemAlign: 0n,
  cntPoseidonG: 0n,
  cntPaddingPG: 0n,
  cntSteps: 376292
}

taking as reference the invocation of the testEcMul.zkasm test.

[hecmas]

This and more have been introduced in PR 328. In particular, the introduction of the modular arithmetic has allowed to reduce the, in average, 2 arithmetics and 1 binary per each Fp arithmetic operation to a single arithmetic.