Download and unpack qisog20181030.tar.gz
:
wget https://quantum.isogeny.org/qisog20181030.tar.gz
gunzip qisog20181030.tar
tar xf qisog20181030.tar
cd qisog20181030
The software has been tested under Linux. Times mentioned below are on one core of a 3.5GHz Haswell CPU.
Bitoperation 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 bitoperation counts.
For example:

The
512 mul quad
line innaturalcost.exp
says241908
, meaning 241908 nonlinear bit operations to multiply 512bit integers. 
The
511 ... (x*y)%p quad
line incsidhcost.exp
says447902
, meaning 447902 nonlinear bit operations to multiply integers modulo the CSIDH512 prime. 
The
511 ... (x^1)%p quad
line says220691666
, meaning 220691666 nonlinear bit operations for inversion. 
The
511 ... iteration1 quad
line says3805535430
, meaning 3805535430 nonlinear bit operations for one iteration of the main loop handling one isogeny computation. 
The
511 ... iteration2 quad
line says4969644344
, 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 CSIDH512 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 lisogeny 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 lisogeny 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.