Two seeming inconsistencies in BooleanFunction - should I report these as bugs?
Paul Leopardi
A few months ago i wrote a large SageMathCloud worksheet based on BooleanFunction, e.g.
https://cloud.sagemath.com/projects/80f4c9e7-8a37-4f59-82e7-aa179ec0b652/files/public/bent-functions-duals-Cayley-graphs.sagews
(This SageMathCloud worksheet is much too long, and badly needs refactoring.)
I am now attempting to put the code into a more usable form, and am finding some seeming inconsistencies in BooleanFunction. Should I use Trac to report these as bugs?
(1) You can create a BooleanFunction of 0 variables (a constant), but you cannot save it to a file. Same with a BooleanFunction of 1 variable.
sage: save_file=os.path.join(SAGE_TMP,'save_file.sobj')
sage: print save_file
/home/leopardi/.sage/temp/catawba/8109/save_file.sobj
sage: b0=BooleanFunction([0])
sage: print b0.truth_table()
(False,)
sage: print b0.nvariables()
0
sage: save(b0,save_file)
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-51-0ddfad8f6d36> in <module>()
----> 1 save(b0,save_file)
sage/structure/sage_object.pyx in sage.structure.sage_object.save (/usr/lib/sagemath//src/build/cythonized/sage/structure/sage_object.c:12085)()
sage/structure/sage_object.pyx in sage.structure.sage_object.SageObject.save (/usr/lib/sagemath//src/build/cythonized/sage/structure/sage_object.c:3631)()
sage/structure/sage_object.pyx in sage.structure.sage_object.SageObject.dumps (/usr/lib/sagemath//src/build/cythonized/sage/structure/sage_object.c:3922)()
sage/crypto/boolean_function.pyx in sage.crypto.boolean_function.BooleanFunction.__reduce__ (/usr/lib/sagemath//src/build/cythonized/sage/crypto/boolean_function.c:16901)()
sage/crypto/boolean_function.pyx in sage.crypto.boolean_function.BooleanFunction.truth_table (/usr/lib/sagemath//src/build/cythonized/sage/crypto/boolean_function.c:11727)()
sage/rings/integer.pyx in sage.rings.integer.Integer.__lshift__ (/usr/lib/sagemath//src/build/cythonized/sage/rings/integer.c:37039)()
ValueError: negative shift count
sage: b1.truth_table()
(False, True)
sage: b1.nvariables()
1
sage: save(b1,save_file)
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-55-f5c8864359bd> in <module>()
----> 1 save(b1,save_file)
sage/structure/sage_object.pyx in sage.structure.sage_object.save (/usr/lib/sagemath//src/build/cythonized/sage/structure/sage_object.c:12085)()
sage/structure/sage_object.pyx in sage.structure.sage_object.SageObject.save (/usr/lib/sagemath//src/build/cythonized/sage/structure/sage_object.c:3631)()
sage/structure/sage_object.pyx in sage.structure.sage_object.SageObject.dumps (/usr/lib/sagemath//src/build/cythonized/sage/structure/sage_object.c:3922)()
sage/crypto/boolean_function.pyx in sage.crypto.boolean_function.BooleanFunction.__reduce__ (/usr/lib/sagemath//src/build/cythonized/sage/crypto/boolean_function.c:16901)()
sage/crypto/boolean_function.pyx in sage.crypto.boolean_function.BooleanFunction.truth_table (/usr/lib/sagemath//src/build/cythonized/sage/crypto/boolean_function.c:11727)()
sage/rings/integer.pyx in sage.rings.integer.Integer.__lshift__ (/usr/lib/sagemath//src/build/cythonized/sage/rings/integer.c:37039)()
ValueError: negative shift count
sage: b2.truth_table()
(False, True, True, False)
sage: b2.nvariables()
2
sage: save(b2,save_file)
This causes a problem for me, because I am trying to generate and save lists of Boolean functions of 2*m variables for m from 0 to some fixed number, and cannot save the list because I can't save the first element.
My work around would be to start from m=1.
(2) You cannot evaluate the algebraic normal form of a BooleanFunction of 0 variables. In addition, the error message incorrectly says that the number of variables must be greater than 1, but you *can* evaluate the algebraic normal form of a function of 1 variable.
sage: b0.algebraic_normal_form()
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-60-8dd0bae0cd3a> in <module>()
----> 1 b0.algebraic_normal_form()
sage/crypto/boolean_function.pyx in sage.crypto.boolean_function.BooleanFunction.algebraic_normal_form (/usr/lib/sagemath//src/build/cythonized/sage/crypto/boolean_function.c:11074)()
sage/rings/polynomial/pbori.pyx in sage.rings.polynomial.pbori.BooleanPolynomialRing.__init__ (/usr/lib/sagemath//src/build/cythonized/sage/rings/polynomial/pbori.cpp:5976)()
ValueError: Number of variables must be greater than 1.
sage: b1.algebraic_normal_form()
x
sage: b2.algebraic_normal_form()
x0 + x1
Nils Bruin
(1) You can create a BooleanFunction of 0 variables (a constant), but you cannot save it to a file. Same with a BooleanFunction of 1 variable.
<BooleanFunction>.truth_table(format="hex")
which uniquely determines the function for n>=2 variables (since then the number of bits in the truth table is a multiple of 4 and hence lines up with the length of hex numbers), but fails to uniquely determine the number of variables uniquely if n<2. The pickle format would need adjustment to reliably handle the n=0,1 cases.
We could get the right result by changing
sage.crypto.boolean_function.BooleanFunction
to
def __reduce__(self):
if self.nvariables() <2:
return unpickle_BooleanFunction, (self.truth_table(format='int'),)
else
unpickle_BooleanFunction, (self.truth_table(format='hex'),)
(2) You cannot evaluate the algebraic normal form of a BooleanFunction of 0 variables. In addition, the error message incorrectly says that the number of variables must be greater than 1, but you *can* evaluate the algebraic normal form of a function of 1 variable.
This functionality is provided by PolyBoRi, which started as an independently maintained library but currently does not have an independent maintainer. I don't know what the process is to change/fix things there. Certainly it would seem a lot of work for not much benefit to add support for GF(2) in PolyBoRi itself.
Would it be OK to represent 0-variable normal forms just as elements of GF(2)? In that case we could just add at the start of algebraic_normal_form the lines:
if self._nvariables==0:
return GF(2)(self._truth_table[0])
and leave PolyBoRi alone. This would deserve special mention in the documentation because it would be an anomalous return type.
Paul Leopardi
Hi Nils,
I have now done a small amount of investigation, and my results and replies are below.
All the best, Paul
On Thursday, 14 July 2016 8:15:35 AM AEST you wrote:
> On Thursday, July 14, 2016 at 6:18:16 AM UTC-7, Paul Leopardi wrote:
> > (1) You can create a BooleanFunction of 0 variables (a constant), but you
> > cannot save it to a file. Same with a BooleanFunction of 1 variable.
> >
> > This seems to be connected with the truth-table problems: The "pickling"
>
> essentially stores
>
> <BooleanFunction>.truth_table(format="hex")
>
> which uniquely determines the function for n>=2 variables (since then the
> number of bits in the truth table is a multiple of 4 and hence lines up
> with the length of hex numbers), but fails to uniquely determine the number
> of variables uniquely if n<2. The pickle format would need adjustment to
> reliably handle the n=0,1 cases.
>
> We could get the right result by changing
>
> sage.crypto.boolean_function.BooleanFunction
>
> to
>
> def __reduce__(self):
> if self.nvariables() <2:
> return unpickle_BooleanFunction, (self.truth_table(format='int'),)
> else
> unpickle_BooleanFunction, (self.truth_table(format='hex'),)
If that could be done cleanly without breaking existing code, I can't see why not.
> > (2) You cannot evaluate the algebraic normal form of a BooleanFunction of
> > 0 variables. In addition, the error message incorrectly says that the
> > number of variables must be greater than 1, but you *can* evaluate the
> > algebraic normal form of a function of 1 variable.
> >
> > As your traceback shows, this error originates in the
>
> BooleanPolynomialRing parent (which is also returned). It is documented as
> needing n>1, but as you point out it does seem to handle n=1 more or less
> correctly as well (perhaps other functionality breaks).
The case n=1 seems OK using Sage 7.2 Ubuntu PPA:
sage: b0 = BooleanFunction([0,0])
sage: b0.algebraic_normal_form()
0
sage: b1 = BooleanFunction([1,0])
sage: b1.algebraic_normal_form()
x + 1
sage: b2 = BooleanFunction([0,1])
sage: b2.algebraic_normal_form()
x
sage: b3 = BooleanFunction([1,1])
sage: b3.algebraic_normal_form()
1
> This functionality is provided by PolyBoRi, which started as an
> independently maintained library but currently does not have an independent
> maintainer. I don't know what the process is to change/fix things there.
> Certainly it would seem a lot of work for not much benefit to add support
> for GF(2) in PolyBoRi itself.
>
> Would it be OK to represent 0-variable normal forms just as elements of
> GF(2)? In that case we could just add at the start of algebraic_normal_form
> the lines:
>
> if self._nvariables==0:
> return GF(2)(self._truth_table[0])
>
> and leave PolyBoRi alone. This would deserve special mention in the
> documentation because it would be an anomalous return type.
With n=1 and n=2, it is possible to create constant polynomials, but the constant 1 for n-1 does not equal the constant 1 for n=2:
sage: b3 = BooleanFunction([1,1])
sage: an3 = b3.algebraic_normal_form()
sage: an3
1
sage: an3.constant()
True
sage: an3.deg()
0
sage: bf = BooleanFunction([1,1,1,1])
sage: anf = bf.algebraic_normal_form()
sage: anf
1
sage: anf.constant()
True
sage: anf.deg()
0
sage: anf == an3
False
As for what you decide to do for n=0, it is up to you. I will work around it for now.
--
Paul Leopardi - https://sites.google.com/site/paulleopardi/