This code is has been written Gregory Landais, 2014.
It is released under the GPL v3 (cf. the LICENSE file).

The interested reader should consult Gregory's PhD thesis (https://hal.archives-ouvertes.fr/tel-01097806).



# What this program does : 
This program takes as input a binary matrix M, target symdromes and a integer w (see Input file format), and looks for w rows in M that once XORed give one the syndromes. Current implementation takes into account only the first syndrome.

# Building the program :
You need the m4ri lib with version >= 20130416 (m4ri.sagemath.org). This in turn requires libpng. Building the code lastly require the gengetopt program.

You can find packages for this version on most linux distributions (from 13.10 on Ubuntu for example).
http://packages.ubuntu.com/trusty/libm4ri-0.0.20130416

Building is done this way (from the root folder) :
$ autoreconf --install
$ ./configure
$ make

# Binaries built :
Several binaries are created by the build process. dumerX and mmtX are the Dumer and the MMT variants where the parameter p is hardcoded to X. generic_dumer is a less efficient version of dumer where parameter p has to be specified on the command line.

# Input file format :
Input file are pure ASCII files. They are formatted this way 
The first line must match the "%d %d %d %d" scanf input. The integers are (in this order) : the number of rows n, the number of columns r, the researched weight w and the number of target syndromes N. From this point, characters different from ASCII 0 and 1 will be ignored. The N*r following characters are the N target syndromes. The n*r following characters are the element of the matrix, one row after another. See src/small_challenge.txt for an example and io.c for implementation.

# Choosing parameters :
Use the binary workfactor to compute optimal parameters for your problem.
Script myworkfactor.sh is a wrapper that runs workfactor against a file respecting the Input file format (see preceding section).

Example : 
$ ./myworkfactor.sh easy_challenge.txt 
414
2	3	32.674
3	10	30.2838
4	15	28.6122
5	20	28.3021
6	23	28.9669
7	26	30.0021
8	29	31.2488
9	31	32.6898
10	34	34.3352
11	37	36.2083
12	40	38.3317
13	44	40.7461
14	51	43.5149
15	93	46.4043
16	144	48.5419
length: 414
dimension: 270
codimension: 144
errors: 16
log_wf: 28.3021		(p=5,l=20)

Here optimal parameters are p=5,l=20. Since we don't have tools for odds values of p we should use Dumer with (p,l)=(4,15) or (p,l)=(6,23) or MMT with (p,l)=(4,15). You should consider trying a value slighty higher than suggested for l as it will compensate an approximation made when computing the optimal parameters (but higher l means higher memory comsumption).

# Using the program :
Put your program in the file format used by the program and choose wether you want to use the Dumer or the MMT variant and parameters p and l.
Parameters -S -I and -T define the stop conditions of the program. The program will stop when one of them is satisfied (respectively number of solutions, number of iterations and seconds spent). If their value is 0, the stop condition is disabled.
The algorithm parameter p is hard coded in the binaries; the parameter l is specified via the -l parameter.
A generic version of Dumer variant is provided as the generic_dumer binary. The parameter p has then to be specified using the -p parameter.
Input will be read from the file specified with the -i parameter or stdin if omited.

Example : ./dumer4 -i small_challenge.txt -l 15 -S 1

# Modifying the program :
The program should be usable as a libray with few modifications. See the main function to set up the parameters of the isd function. The variant to use is specified by the linked file (see src/Makefile.am).