Breaking down the Aleo example: twoadicity

In this program we will work with fields (“finite field” or “Galois field”). We will calculate the number of powers of two in a simple factorization of the input number “n”.

First, let’s understand what a “finite field” is.
It is a field consisting of a finite number of elements. Finite fields are widely used in cryptography. The article by Diffie and Helman on public key cryptography, which proposed a protocol for key exchange, is considered the main work in this area. Later, many cryptoprotocols and networks based on the use of finite fields have appeared.

For a better understanding of how finite fields can be computed, you can read the tutorial.

Fields combine well with constraint systems. One way to use fields is instead of integers for arithmetic (this doesn’t always make sense — it depends on the case). Such programs will create fewer constraints and are cheaper to run and verify.

The code itself:

Here we take a field from the inputs file:

This is the field which is subject to further analysis (it is a parameter in main)

At the very beginning of main we create a duplicate of field “n” and set the counter to 0.

Since the ints field (line 7) has 253 bits or less, any number in the field will have no more than 252 powers of two in its simple factorization.

In line 8 we have a check:

We define the is_even predicate for fields as follows:

• If n is even and non-zero, then obviously n/2 < n.
• If n is odd, then n-p is an even negative number equivalent to the field, and (n-p)/2 is a field-equivalent negative number closer to 0, larger than n-p.
• If we add p to both of these negative numbers, we get n/2 = (n-p)/2 + p = (n+p)/2 greater than n and still less than p.
• If the check passes, we divide the field by a power of two and update the counter.

If the program is correct, (from line 13) we get the answer:

Original version: https://medium.com/@kaylej/415e21c6e8ff