Opened 3 years ago
Closed 3 years ago
#24282 closed defect (fixed)
BooleanFunction.truth_table(format="hex") returns wrong values
Reported by:  pleopardi  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  cryptography  Keywords:  
Cc:  Merged in:  
Authors:  Paul Leopardi  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  eeaebe3 (Commits)  Commit:  eeaebe309317a0df13b561db53384d5b758a61af 
Dependencies:  Stopgaps: 
Description (last modified by )
Sometimes, especially with functions of 8 variables, the method BooleanFunction.truth_table(format='hex")
returns incorrect values that are also too long.
Example:
sage: from sage.rings.integer_ring import ZZ sage: from sage.crypto.boolean_function import BooleanFunction sage: hex_str = "0123456789112345678921234567893123456789412345678951234567896123" sage: len(hex_str) 64 sage: bf = BooleanFunction(hex_str) sage: bf.nvariables() 8 sage: bf_tt_hex = bf.truth_table(format="hex") sage: bf_tt_hex '123456789112345678921234567893123456789412345670123456789112345678921234567893123456789412345678951234567896123' sage: len(bf_tt_hex) 111 sage: S = ZZ(bf.truth_table(), 2).str(16) sage: padding = "0" * ((1 << (bf.nvariables()  2))  len(S)) sage: tt_hex = padding + S sage: tt_hex '0123456789112345678921234567893123456789412345678951234567896123' sage: len(tt_hex) 64
The example also shows how the code in https://github.com/sagemath/sage/blob/develop/src/sage/crypto/boolean_function.pyx lines 566 to 576 should be fixed. A suggested patch is attached.
The example can also be used as the basis for a test case once the patch has been applied.
Attachments (1)
Change History (11)
Changed 3 years ago by
comment:1 Changed 3 years ago by
 Description modified (diff)
 Milestone changed from sage8.1 to sage8.2
Thanks. Could you provide a test example and a git branch for the fix, too?
comment:2 Changed 3 years ago by
A working test example may take me a little time as I have not yet built Sage from Git. I could mock up a test example for someone else to test, if that is acceptable.
comment:3 Changed 3 years ago by
Also, I am new at providing Git branches for Sage. I will carefully read the instructions at http://doc.sagemath.org/html/en/developer/manual_git.html and use them to provide a Git branch. This may have to wait until the weekend.
comment:4 Changed 3 years ago by
 Branch set to u/pleopardi/fix_boolean_function_truth_table_hex
 Commit set to d22ccd3ccd1e79d5f6153e54c0dbefa89bf93139
 Status changed from new to needs_review
As far as I can tell, I have pushed my recommended changes to the branch u/pleopardi/fix_boolean_function_truth_table_hex
This is the first time I have created a branch in trac, so I may have made a mistake that I'm not aware of.
comment:5 Changed 3 years ago by
I would have cut most of these
sage: len(T) ...
from the example in your branch. Have you tried building the documentation with this branch applied?
comment:6 Changed 3 years ago by
 Commit changed from d22ccd3ccd1e79d5f6153e54c0dbefa89bf93139 to eeaebe309317a0df13b561db53384d5b758a61af
Branch pushed to git repo; I updated commit sha1. New commits:
eeaebe3  Remove some len expressions from doctest for BooleanFunction.truth_table

comment:7 Changed 3 years ago by
I have now cut some of the len expressions from the doctest, have retested sage/crypto, and have tried rebuilding the documentation. All seems fine to me.
comment:8 Changed 3 years ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
Looks good to me; however, it probably needs testing on a 32bit machine. Hopefully a patchbot will do.
PS. Please enter the author's name in Authors.
comment:10 Changed 3 years ago by
 Branch changed from u/pleopardi/fix_boolean_function_truth_table_hex to eeaebe309317a0df13b561db53384d5b758a61af
 Resolution set to fixed
 Status changed from positive_review to closed
Patch to boolean_function.pyx to retrun correct value for truth_table(format='hex')