Download and unpack qisog-20181030.tar.gz:

    wget https://quantum.isogeny.org/qisog-20181030.tar.gz
    gunzip qisog-20181030.tar
    tar -xf qisog-20181030.tar
    cd qisog-20181030

The software has been tested under Linux. Times mentioned below are on one core of a 3.5GHz Haswell CPU.

Bit-operation simulator

To run:

    cd bits
    make

This takes 8 minutes. If you don't have clang++, try changing clang++ to g++ in bits/Makefile.

Copies of the expected outputs are in bits/*.exp. In particular, bits/*cost.exp shows various bit-operation counts. For example:

• The 512 mul quad line in naturalcost.exp says 241908, meaning 241908 nonlinear bit operations to multiply 512-bit integers.

• The 511 ... (x*y)%p quad line in csidhcost.exp says 447902, meaning 447902 nonlinear bit operations to multiply integers modulo the CSIDH-512 prime.

• The 511 ... (x^-1)%p quad line says 220691666, meaning 220691666 nonlinear bit operations for inversion.

• The 511 ... iteration1 quad line says 3805535430, meaning 3805535430 nonlinear bit operations for one iteration of the main loop handling one isogeny computation.

• The 511 ... iteration2 quad line says 4969644344, meaning 4969644344 nonlinear bit operations for one iteration of the main loop handling two isogeny computations.

Some outputs also have matching Sage scripts:

    cd bits
    sage pointtest.sage | cmp - pointtest.exp
    sage pointtest3.sage | cmp - pointtest3.exp
    sage elligatortest2.sage | cmp - elligatortest2.exp
    sage csidhtest.sage | cmp - csidhtest.exp
    python crandom.py | sage csidhtest2.sage | cmp - csidhtest2.exp

Internally, the core of the simulator is bits/bit.h, counting the number of NOTs, XORs, ANDs, and ORs. The value method decapsulates the value of a bit.

Mathematical calculations of failure probabilities

Probabilities are computed for the 74 CSIDH-512 primes, with C = 5. These parameters are set at the top of each script. Each output line indicates the number of iterations and the failure probability for that number of iterations. Each failure probability is printed in the form a * 2^(-b), where a (rounded to three digits after the decimal point) is between 0.500 inclusive and 1.000 exclusive, and b is a nonnegative integer.

To compute failure probabilities for iteration1 (each iteration tries to reduce the top nonzero exponent), in a realistic model where each l-isogeny step has failure chance 1/l:

    cd chances
    sage top1exact.sage 210 > top1exact.out.210

Here 210 asks for results for 0, 1, ..., 209 iterations. This takes 7 seconds. Changing 210 to 500 increases the time to 40 seconds.

To compute failure probabilities for iteration2 (each iteration tries to reduce the top nonzero exponent and the next exponent having the same sign), in a realistic model where each l-isogeny step has failure chance 1/l:

    cd chances
    sage top2exact.sage 110 50 upper > top2exact.out.110.50.upper

Here 110 asks for results for 0, 1, ..., 109 iterations; 50 indicates the number of bits of precision in the calculation; upper computes upper bounds on failure probabilities (while lower would have computed lower bounds). This takes 164 seconds. Changing 110 50 to 350 512 increases the time to 6143 seconds, and then changing lower to upper increases the time to 9908 seconds.

To compute failure probabilities for iteration1 (each iteration tries to reduce the top nonzero exponent), in a pessimistic model where each isogeny step has failure chance 1/3:

    cd chances
    sage top1crude.sage 500 > top1crude.out.500

Here 500 asks for results for 0, 1, ..., 499 iterations. This takes 92 seconds. Changing 500 to 1000 increases the time to 790 seconds.

Experiments

The following programs need libsodium installed.

To run 10000000 iteration1 experiments in the realistic model:

    cd chances
    make
    ./top1trials > top1trials.out

This takes 83 seconds.

To run 10000000 iteration2 experiments in the realistic model:

    cd chances
    make
    ./top2trials > top2trials.out

This takes 94 seconds.

To run 10000000 iteration1 experiments in the pessimistic model:

    cd chances
    make
    ./top1ctrials > top1ctrials.out

This takes 72 seconds.

---

Version: This is version 2018.10.31 of the "Software" web page.