- Generated by
1.8.13
|
LatMRG Guide
1.0
A software package to test and search for new linear congruential random number generators
|
This page lists the tags available for the xml configuration files.
These tags are sorted by the program modes where they can be used. The page also presents the default values the tags have. Every tag with a default value can be ommited. Additionaly, the ordering of tags in configuration files should not matter. If you get an error regarding that, please report it. Example configuration files are bundled with the software in the examples directory.
If you are not really familliar with XML, there is no neeed to panic. In fact we are not experts either, but the usage we make of this language is very basic. XML is a markup languages where different blocks of text are stored between tags quite similar to HTML tags. Tags can also have attributes which are somewhat like variables associated with them.
Here is a simple XML example:
This highlight all the features needed for LatMRG.
Each program mode is identified by a tag:
<mk> to search for \(m\) and \(k\) combinations<period> to test full period length<lattest> to test the lattice structure of a generator<seek> to search for new generatorsAll the information for the program must be contained inside the tag, and only the first program mode tag of each file will be read. Below, we present the tags the same way that they need to be nested in the configuration files.
There currently are two tags that are valid for any of the program mode. These tags must be specified at the same level as the mode tag to be recognized.
<out> is a program wide tag that lets the user specify where the program outputs. If it is not specified, the program will print its output in the command line. If it is specified without attribute, it will print in a file in the same directory as the configuration file, but with a .res extension. Otherwise, it will print the output in a file named after the value of the first attribute.
<print_time> is a tag that lets the user control if the program prints the time it took to execute or not. If this tag is ommited, time will be printed. If you want to avoid printing time, simply add <print_time x="false"/> at the end of the configuration. This is mainly used for development purposes. We can run examples files and compare their outputs with what is expected to make sure everything works as expected.
Given k, this mode searches for m such that \(r = (m^k-1)/(m-1)\) is prime. Here is an example parameter file to search for m and k parameters:
This program mode uses 5 tags specific to it:
<power x="x" y="y"/> (no default): When this tag is specified, the program will search for y m smaller than 2^x. This tag is exclusive with range.<range x="x" y="y" z="z"/> (no default): When this tag is specified, the program will search for all m in the range [2^x+y, 2^x+z]. This tag is exclusive with power.<k k="k"/> (no default): The order of the generator for which you want a modulo.<safe x="bool"/> (no default): If this is true, the program will also force \((m-1)/2\) to be prime. Otherwise, this won't be verified.<factor x="bool"/> (default: x="false"): If this is false, the program will factor and print the factorisation of \(m-1\) in its output. This is only usefull if safe is false.Given a generator, this tests if it has full period. Here is an example parameter file to test a if a generator has full period.
This mode takes tags similar to those you will see in the next mode.
<type x="GenType"/> (default: x="MRG"): The type of the generator to be tested. This can be either MRG, LCG, MMRG or MWC. LCG is not for a simple LCG, but rather for generators with a single coefficient with non-zero carry.<modulo basis="b" exponent="e" rest="r"/> (no default): The modulo of the recurrence. Needs to have attributes basis, exponent and rest. Will compute the modulo as m = b^e+r<order k="k"> (no default): The order of the recurrence.<mult x="a1 a2 ... ak"/> (no default): The coefficients of the generator. This is not valid for MMRG type. If type is MWC, the vector must be of the form x="a0 a1 ... ak" (with k+1 coefficients).<matrix a1="a11 a12 ... a1k" ... ak="ak1 ak2 ... akk"/> (no default): contains the multiplier matrix for MMRG generator period check. Must have k attributes that each contain a line of k elements the matrix.We now talk about both the generator testing and generator search specific tags. Here is an example file to test the MRG32k3a [rLEC99b] generator
Searching and testing generators is very similar and most tags repeat between the two modes. There mainly are two differences: generators tests take multipliers in their input but searching takes a description of how you want the multipliers to be, and testing will only test one generator at a time while searching will find and test generators as long as it has time left.
<gen>: A tag to specify generator parameters. By default, generators are considered to be combined. You can nest any combination of the following tags to specify the generator components<mrg>: A MRG/LCG component<modulo basis="b" exponent="e" rest="r"/> (no default): The modulo of the recurrence. Needs to have attributes basis, exponent and rest. Will compute the modulo as m = b^e+r<order k="k"> (default: k="1"): The order of the recurrence. Needs to have an attribute whose value is the order. If none is not given, it is assumed the generator is of order 1. This simplifies LCG specification.<period check="bool"/> (default: true): Indicates wheter or not to verify the full period via its attribute. Nested tags are unecessary if check is false.<m1 method="m" file="filename"/> (default: method="DECOMP", file: a random filename): Indicates how to obtain the factorization of \(m-1\) for full period verification. The options for method are DECOMP will factorize and discard the results afterwards, DECOMP_WRITE will factorize and write to the file filename, DECOMP_READ will try to read the results from the the file filename and DECOMP_PRIME assumes \((m-1)/2\) is prime. The attributes names are fixed for this option.<r m="method" name="filename"/> (default: m="DECOMP", name: a random filename): Same as <m1> but for \(r = (m^k-1)/(m-1)\).<method/> (<seek> only) (no default): This tag indicates which method to use to select the coefficients of the generators. It also needs to have an attribute, specifying the method by its name, with a value describing how to use it. The options are:random="a[1] a[2] ... a[k-1]" the coefficients are searched randomly between 0 and the value of a[i]. a[i] can take the value m and the program will give it the value of the modulo.a[1,i] and a[2,i].<coeff a="a1 a2 ... ak"/> (<lattest> only) (no default): The coefficients of the generator. "a1 a2 ... ak" are the numerical values for the coefficients.<mmrg>: A MMRG component<modulo basis="b" exponent="e" rest="r"/>: See modulo in <mrg><order k="k"> (no default): See order in <mrg><period check="bool"/>: See period in <mrg><mwc>: A MWC component<modulo basis="b" exponent="e" rest="r"/>: See modulo in <mrg><order k="k"> (no default): See order in <mrg><period check="bool"/>: See period in <mrg><coeff a="a0 a1 ... ak"/> (<lattest> only) (no default): The coefficients of the generator. "a0 a1 ... ak" are the numerical values for the coefficients.<spectral>: Contains the parameters to perform a spectral test. Here, we consider every test based on the inverse of the length of the shortest non-zero lattice vector.<reduction m="method"/> (default: FULL): The reduction to use on the lattice vectors before computing the merit. The options are FULL, the program searches for the shortest non-zero lattice vector, BKZ, the program uses the shortest lattice vector found after BKZ reduction to compute the merit, and LLL, the program uses the shortest lattice vector found after LLL reduction to compute the merit.<nodesBB n="num"/> (default: 100000000): The number of nodes the branch and bound algorithm will explore. This is only read when reduction is FULL.<norma n="normalizer"/> (default: NONE): The normalizer used by the spectral test. The spectral test will compute \(\ell_t/\ell_t^*\) if this has a value, it will otherwise compute \(1/\ell_t\). The options are: ROGERS, to use Rogers's bounds [mROG51a], BESTLAT, to use the length of the shortest vector in the densest known lattice and LAMINATED, to use the length of the shortest vector in the densest laminated lattice.<dual d="bool"/> (default: true): A boolean switch to use the dual. If d is true, the program will use the dual. Otherwise, it will use the primal.<length>: Contains the parameters to perform tests with the length of the shortest non-zero vector as the merit. This performs the same<reduction m="method"/> (default: FULL): see reduction in <spectral>.<dual d="bool"/> (default: false): see dual in <spectral>.<norm n="norm"/> (default: L2NORM): Can be used to change the norm used to compute the vector length. L2NORM is the default euclidian norm, but L1NORM can also be used as a way to obtain the number of hyperplans spanned by the generator points.<proj>: Contains the parameters of the projections to use.<min min="x">: The minimal dimension. The program will test sequential projection starting with \(\{0, \ldots, x-1\}\), and every non-sequential projection will contain at least one coordinate greater or equal to x. A common value for this is x=k+1.<num d="d">: The dimension up to which we test non sequential projections. x=1 will only test sequential projections, x=d>1 will test non-sequential projections in dimensions 2 to d.<dim max="x1 x2 ... xd">: the value of xi is the maximal coordinate that will be used when test non-sequential projections of dimension i. x1+1 is the maximal dimension of sequential coordinates that will be tested. This needs to contain d values to be valid.<time limit="t"> (seek only) (default: 600): The time that the program will use before timing out.<num_gen n="n"> (seek only) (default: 10): The number of generators the program will keep.<best x="bool"> (seek only) (default: true): If x is true, the program will search for good generators, otherwise, it will search for bad generators. Bad generators search is mainly implemented to search for examples. It is recommended to have <time> be small if <best> is set to false. Unless looking for something with an abysmal spectral test, it is fairly easy to find a generator with bad enough performance in the spectral test for illustration purpose..<detail level="int"> (lattest only) (default: 1): level has to be an integer between 0 and 2. The highest level of detail will print the most information on the tested generator.<function_params> (To come): Re-add options to fine grain functions parameters in the reduction to avoid recompiling if the program fails.Both modes necessitate the following tags to be correctly specified for the program to work:
<gen> along with at least one valid nested <mrg>, <mmrg> or <mwc>.<length> or <spectral> tag<proj> correctly specified. As of now, the program does not do error checking for the values specified in this tag.If the program comes a accross those tags and they contain error, it should exit with a clear enough error message. Any other error in a tag will result in the usage of the default value, but the program will notify you that it contains an error in its configuration file.
1.8.13