generate-diagonal-distribution.md

The generate_diagonal_distribution executable

Synopsis

Synopsis: mpirun generate_diagonal_distribution \
   [ -dim <dimension> ] [ -eta-bound <eta-bound> ] \
      [ -det | -rnd | -exp <d> <r> ] \
         ( [ -s ] <m> <sigma> <s> { <m> <sigma> <s> } | \
             -l   <m> <sigma> <l> { <m> <sigma> <l> } )

Computes a part of the distribution induced by Shor's algorithm for computing general discrete logarithms when modified as in [E19p].

The full distribution is two-dimensional in $(\alpha_d, \alpha_r)$. This executable computes and stores a distribution in $(\alpha_r, \eta)$ for $\eta \in [-B_\eta, B_\eta] \cap \mathbb Z$ via the expression for $f_\eta(\theta_r)$ given in [E19p].

When the distribution is to be sampled by other executables, $(\alpha_r, \eta)$ is first sampled from the part of the distribution computed by this executable. Then $j$ is sampled uniformly at random from all values of $j$ that yield $\alpha_r$. Finally, $k$ is then sampled given $j$ and $\eta$ via the angle $\phi_\eta$ and the expression for $h(\phi_\eta)$ given in [E19p]

The distribution is said to be diagonal since constructive interference is expected to arise on the "diagonal" in the argument plane where the angle $\phi_\eta$ is small.

The distribution generated will be assigned an appropriate name and written to the distributions directory. If this directory does not exist, it will be created. If the distribution already exists, an error will be reported.

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 <m> <sigma> <s> where

• <m> is the bit length $m$ of the order $r$
• <sigma> is the padding length $\varsigma$
• <s> is the tradeoff factor $s$; used to set $\ell = \lceil m / s \rceil$

or, if the -l flag is specified, tuples <m> <sigma> <l> where

• <m> and <sigma> are as above
• <l> is the parameter $\ell$

Optional command line arguments

Flags specifying the value of $d$ and $r$ (defaults to -det):

• -det selects $d$ and $r$ deterministically by reading from Catalan's constant
• -rnd selects $r$ uniformly at random from $(2^{m-1}, 2^m)$ and $d$ uniformly at random from $[r/2, r)$
• -exp <d> <r> explicitly sets $d$ and $r$ to <d> and <r> where it is required that $0 < d < r$ and $2^{m-1} < r < 2^m$

Flag specifying the bound $B_\eta$ (defaults to 0):

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

  The bound $B_\eta$ controls how many peak indices $\eta$ are included in the distribution: More specifically, the peaks with peak indices $\eta \in [-B_\eta, B_\eta] \cap \mathbb Z$ are included.

Flag specifying the dimension (defaults to 2048):

• -dim <dimension> sets the dimension to <dimension>

  The dimension specifies the resolution of the histogram. Must be a power of two.