-rw-r--r-- 3279 high-ctidh-20210523/README.md
Prerequisites: Intel or AMD CPU with `adcx`/`adox`: i.e., Broadwell, Skylake, or newer. Linux with standard development tools plus `clang` plus `valgrind`. To download and unpack the latest version: wget -m https://ctidh.isogeny.org/high-ctidh-latest-version.txt version=$(cat ctidh.isogeny.org/high-ctidh-latest-version.txt) wget -m https://ctidh.isogeny.org/high-ctidh-$version.tar.gz tar -xzf ctidh.isogeny.org/high-ctidh-$version.tar.gz cd high-ctidh-$version To compile, test for functionality, tune for multiplications, and tune for cycles, for all selected sizes (511, 512, 1024, 2048): make This takes a while because of all the testing and tuning. Any test failure will stop the build process. You can separately run make generic # size-independent tests, 8.6 minutes make 511 # size 511, 1.5 minutes make 512 # size 512, 1.7 minutes make 1024 # size 1024, 25 minutes make 2048 # size 2048, 549 minutes where the timings shown here are on a 3GHz Skylake core. (Tuning for multiplications is machine-independent and can be precomputed. Tuning for cycles can be precomputed per microarchitecture. One can carry out both precomputations more efficiently by starting with measurements of `tree1`, `multiprod2`, `multiprod2_selfreciprocal`, `multieval_precompute`, and `multieval_postcompute`; the Python scripts include a preliminary implementation of this for the multiplication tuning, currently used only as a double-check.) The functionality testing included in "`make`" does not include a constant-time test. To run a constant-time test for all selected sizes: make timecop # 25 minutes For benchmarks regarding, e.g., size-511 code tuned for multiplications: ./bench511mults 16383 > bench511mults.out.16383 This runs a million experiments: more precisely, 16383 experiments for each of 65 keys. This takes hours, and generates hundreds of megabytes of data. Each measurement includes, for validation and separately for the action, a "`mulsq`" count that includes both multiplications and squarings, a "`sq`" count that includes only squarings, an "`addsub`" count that includes additions and subtractions, and a cycle count (which for multiplication-tuned code isn't far behind cycle-tuned code). The action also shows "`stattried`" counts showing the number of times each batch occurred publicly in an atomic block. To analyze average costs and standard deviations: ./analyze-costs < bench511mults.out.16383 \ > bench511mults.out.16383.analyze-costs Statistics are printed for each of the 65 keys separately, and ("`total`") for the all of the experiments together. To analyze whether the "`stattried`" counts are as expected: ./analyze-pr < bench511mults.out.16383 \ > bench511mults.out.16383.analyze-pr This prints, for each batch, 1−1/p times the number of times the batch was tried divided by the batch bound, where p is the smallest prime in the batch. For various size-511 microbenchmarks: ./umults511 ./ubench511 To select other CSIDH sizes and other CTIDH parameters (subject to various undocumented restrictions), edit the table at the top of `autogen` and run "`./autogen; make`".