Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 8796
1
2
#*****************************************************************************
3
# Copyright (C) 2016 Paul Leopardi [email protected]
4
#
5
# Distributed under the terms of the GNU General Public License (GPL)
6
# as published by the Free Software Foundation; either version 2 of
7
# the License, or (at your option) any later version.
8
# http://www.gnu.org/licenses/
9
#*****************************************************************************
10
11
def linear_mapf(boolf, A):
12
"""
13
Given the `BooleanFunction` `boolf` and the `GF(2)` matrix $A$, the function `linear_mapf` returns the function $x \mapsto \mathtt{boolf}(A x)$, where $x$ is a positive integer, and its binary expansion is used in the `GF(2)` matrix multiplcation by $A$.
14
"""
15
m = boolf.nvariables()
16
return lambda x: boolf(list(A * vector(base2(m, x),GF(2))))
17
18
def list_to_int(blist):
19
"""
20
Given the list `blist` representing the binary expansion of a positive integer $n$, the function `list_to_int` returns $n$.
21
"""
22
return sum([blist[k] * 2 ** k for k in range(len(blist))])
23
24
def enumerate_linear_maps(boolf, certify=False):
25
"""
26
Given the `BooleanFunction` `boolf`, the function `enumerate_linear_maps` returns a list of unique truth tables obtained by enumerating all Boolean functions of the form `linear_mapf(boolf,A)`,
27
where $A$ is a matrix in the general linear group `GL(m, GF(2))`.
28
29
The optional parameter `certify` defaults to `False`. If `certify` is true then the function `enumerate_linear_maps` prints each value of $c$ and $A$ for which `linear_mapf(boolf,A) == mapf(boolf,b,c,boolf(b))`,
30
that is, $\mathtt{boolf}(A x) = \mathtt{boolf}(x+b) + \langle c, x \rangle + \mathtt{boolf}(b)$.
31
"""
32
m = boolf.nvariables()
33
v = 2 ** m
34
mapped_ittdict = {}
35
if certify:
36
for b in range(v):
37
for c in range(v):
38
mapped_f = mapf(boolf, b, c, boolf(b))
39
mapped_tt = [mapped_f(x) for x in range(v)]
40
mapped_itt = list_to_int(mapped_tt)
41
if mapped_itt in mapped_ittdict:
42
mapped_ittdict[mapped_itt].append((b,c))
43
else:
44
mapped_ittdict[mapped_itt] = [(b,c)]
45
G = GL(m, GF(2))
46
ittset = set()
47
ttlist = []
48
for A in G.list():
49
tt = [int(linear_mapf(boolf, A)(x)) for x in range(v)]
50
itt = list_to_int(tt)
51
if not itt in ittset:
52
ittset.add(itt)
53
ttlist.append(tt)
54
if certify:
55
if itt in mapped_ittdict:
56
print(mapped_ittdict[itt], ':')
57
print(A)
58
sys.stdout.flush()
59
return ttlist
60
61