THE IMUNAL API FOR DEVELOPERS

NAME

imunal.h - a library for computing algebraic immunity of boolean functions

SYNOPSIS

#include <imunal.h>

DESCRIPTION

The imunal library is a research library for implementing algorithms that computes the algebraic immunity (AI) of boolean functions.

The imunal.h file defines several structures that shall not be modified directly. Functions to manipulates these structures are provided by imunal, see the function reference below.

struct bool_func;: Represents a boolean function.
struct points;: Rpresents a set of points of GF(2)^n.

The last defined structure in imunal.h has members that shall be used directly.

struct bool_func_ai_stats {
  clock_t fiber,ai;
};

Fiber and ai contains the time used to compute respectively the fiber over 1 and the AI of a given boolean function.

The maximum number of variables supported by the library is given by IMUNAL_NVAR_MAX. Note that for optimization reasons this number is usually 30. If you need to compute AIs for functions with more that 30 variables (which should be unlikely) you must recompile the library with make WORD=long. The maximum number of variables will then be 62 on 64-bits machines. Note that on compilers supporting 128 bits types (__int128 on recent versions of gcc) you can use boolean functions with at most 126 variables.

In order to abstract the number of variables supported by the library, imunal.h defines the following types.

tuple: Represents an element of GF(2)^n. Each bit of a tuple is a component. Note that tuple is usually a unsigned long int but do not assume that. Note however that a tuple can be safely casted into unsigned long int.
bit: Represents a single bit or element of GF(2). Note that bit may not be a typedef for unsigned char and do not assume that. Note however that a bit can be safely casted into tuple.

FUNCTION REFERENCE

void bool_func_print(FILE *out,struct bool_func *f);

Print the boolean function f to out.

struct bool_func *bool_func_read(FILE *in);

Read from in a boolean function and return a pointer to it. If an error occur NULL is returned.

void bool_func_free(struct bool_func *f);

Free the memory occupied by the boolean function f.

bit bool_func_eval(struct bool_func *f,tuple a);

Return the evaluation of the boolean function f at a.

int bool_func_get_ai(struct bool_func_ai_stats *t,struct bool_func *f,int order);

Return the algebraic immunity of the boolean function f using the order order for the monomials. If t is not NULL then the structure pointed to by t will be filled. Its fiber member will contain the time used to compute the fiber over 1 of f while ai will contain the time used to actually compute the AI of f. On error this function will return -1 and the members of t will have undefined values.

The possible values for order are listed below.

IMUNAL_GRLEX: Graded lexical ordering.

Note that bool_func_get_ai will choose the appropriate algorithm to use for the computation according to its arguments and the amount of RAM detected on your system.

int bool_func_get_ai_ex(struct bool_func_ai_stats *t,struct bool_func *f,int order,int algo,unsigned long mem);

This function behaves exactly as the bool_func_get_ai above except that it let you choose which algorithm is to be used via algo. The extra argument mem is used to limit the amount of memory during the computation.

The possible values for algo are listed below.

IMUNAL_NAIVE_ALGO: The naive algorithm uses one char per bit and does not take into account mem.
IMUNAL_GREEDY_ALGO: The greedy algorithm uses one char for 4 bits and does not take into account mem.
IMUNAL_NOSWAP_ALGO: The noswap algorithm uses one char for 4 bits and takes into account mem. The amount of memory used during the computation will be limited to a maximum of mem bytes. Note that this can drastically slow the computation. It is recommanded not to use bool_func_get_ai_ex but bool_func_get_ai instead as the latter will choose the appropriate algorithm according to its arguments and the amount of RAM detected on your system.

int bool_func_get_ai_pts(struct bool_func_ai_stats *t,struct points *pts,int order);

Return the algebraic immunity of the boolean function whose fiber over 1 is the set of points pts using the order order for the monomials. If t is not NULL then the structure pointed to by t will be filled as for the bool_func_get_ai function. On error this function will return -1 and the members of t will have undefined values. The values that order can take are exactly the ones given above for the bool_func_get_ai function.

int bool_func_get_ai_pts_ex(struct bool_func_ai_stats *t,struct points *pts,int order,int algo,unsigned long mem);

This function behaves exactly as the bool_func_get_ai_pts above except that it let you choose which algorithm is to be used via algo. The extra argument mem is used to limit the amount of memory during the computation. The meaning of these arguments are exactly the same as for bool_func_get_ai_ex.

struct points *majority_function(int nvar);

Return the fiber of 1 of the majority function in nvar variables. On error NULL is returned.

void points_free(struct points *pts);

Free the memory occupied by pts.

LICENSE

The documentation of imunal and imunal are placed under the GPL.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

AUTHOR

This man page was written by Guillaume Quintin <quintin@lix.polytechnique.fr>.