solve-diagonal-distribution.md

The solve_diagonal_distribution distribution

Synopsis

Synopsis: mpirun solve_diagonal_distribution \
   [ -delta-bound <delta-bound> ] [ -eta-bound <eta-bound> ] \
      [ -adaptive | -non-adaptive | -non-adaptive-early-abort ] \
         [ -closest | -enumerate ] [ -timeout <timeout> ] \
            [ -lll | -lll-then-bkz | -bkz | -hkz ] \
               <distribution> <n> { <distribution> <n> }

Simulates the quantum algorithm by sampling the distribution, and solves the simulated outputs of $n$ runs for the logarithm $d$ given the order $r$.

This when accepting to search all combinations of peak indices $\eta_1, \ldots, \eta_n$ such that $\eta_i \in [-B_\eta, B_\eta] \cap \mathbb Z$.

In total $10^3$ problem instances are consider to gather statistics.

The results are written to the console and to logs/solve-diagonal.txt.

Note: This is an MPI program. The node with rank zero acts as server. All other nodes are clients, requesting jobs from and reporting back to the server node. A minimum of two nodes is hence required.

Mandatory command line arguments

Tuples <distribution> where

• <distribution> is the path to the distribution
• <n> is the number of runs

Optional command line arguments

Flag specifying the search bound $B_\Delta$ in $\Delta$ (defaults to DELTA_BOUND):

• -delta-bound <eta-bound> sets $B_\Delta$ to <eta-bound>

  All $\Delta \in [-B_\Delta, B_\Delta] \cap \mathbb Z$ are searched when sampling $k_i$ given $j_i$ and $\eta_i$.

Flag specifying the search bound $B_\eta$ in $\eta$ (defaults to same as for the distribution):

• -eta-bound <eta-bound> sets $B_\eta$ to <eta-bound>

  All $\eta_i \in [-B_\eta, B_\eta] \cap \mathbb Z$ are searched when sampling $j_i$ and $\eta_i$, and when solving the pairs $(j_i, k_i)$ for $d$ given $r$.

Flags specifying the search strategy (defaults to -adaptive):

• -adaptive increment or decrement $n$ to find the minimum
• -non-adaptive attempt to solve only for the $n$ specified
• -non-adaptive-early-abort abort immediately if there are too many failures

Flags specifying whether an enumeration is performed (defaults to -closest):

• -closest solves by finding the closest vector to a given lattice vector
• -enumerate solves by enumerating the lattice

Flag specifying the enumeration timeout (defaults to 300 s):

• -timeout <timeout> sets the enumeration timeout to <timeout> seconds

  Once this timeout is elapsed the enumeration is aborted. This is reported as a failure to solve.

Flags specifying the lattice reduction algorithm (defaults to -lll-then-bkz):

• -lll use Lenstra-Lenstra-Lovász (LLL)
• -bkz use block Korkin-Zolotarev (BKZ)
• -hkz use Hermite Korkin-Zolotarev (HKZ)
• -lll-then-bkz use LLL and then BKZ if solving the LLL-reduced basis fails

Interpreting the output

The log file logs/solve-diagonal.txt is on the format

# Processing: diagonal-distribution-det-dim-2048-m-2048-sigma-12-s-30.txt
# Bounds: (eta = <all> (0), delta = 1000000)
# Search strategy: Adaptive
# Solution method: Closest
# Reduction algorithm: LLL then BKZ
# Timestamp: 2024-02-29 11:18:15 CET
m: 2048 sigma: 12 s: 30 n: 34 -- success: 987 -- fail: 11 (5) -- prepare:    69.406 ms solve:  2412.413 ms [ 1817.261, 78989.007] ** incrementing
m: 2048 sigma: 12 s: 30 n: 35 -- success: 997 -- fail: 3 (2) -- prepare:    42.009 ms solve:  2244.208 ms [ 2022.457, 85395.739] ** stopping

where we find $m$, $\varsigma$, $s$ or $\ell$, $n$ — #success — #fail — prep-time — solve-time, and where

• $m$ is the bit length of the order $r$,
• $\varsigma$ is the bit length of the padding,
• $s$ is the tradeoff factor such that $\ell = \lceil m / s \rceil$, if $s$ was specified when the distribution was generated, otherwise $\ell$ is explicitly stated instead,
• $n$ is the number of runs,
• #success is the number of problem instances that were successfully solved,
• #fail is the number of problem instances not solved, where the count within parenthesis is the number of problem instances that failed due to sampling errors,
• prep-time is the average time in ms required to setup the problem instances, and
• solve-time is the average [min, max] time in ms required to solve the problem instances.