Opened 5 years ago
Closed 5 years ago
#24282 closed defect (fixed)
BooleanFunction.truth_table(format="hex") returns wrong values
Reported by: | pleopardi | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.2 |
Component: | cryptography | Keywords: | |
Cc: | Merged in: | ||
Authors: | Paul Leopardi | Reviewers: | Dima Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | eeaebe3 (Commits, GitHub, GitLab) | 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 5 years ago by
Attachment: | boolean_function-correct_truth_table_hex.patch added |
---|
comment:1 Changed 5 years ago by
Description: | modified (diff) |
---|---|
Milestone: | sage-8.1 → sage-8.2 |
Thanks. Could you provide a test example and a git branch for the fix, too?
comment:2 Changed 5 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 5 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 5 years ago by
Branch: | → u/pleopardi/fix_boolean_function_truth_table_hex |
---|---|
Commit: | → d22ccd3ccd1e79d5f6153e54c0dbefa89bf93139 |
Status: | new → 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 5 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 5 years ago by
Commit: | d22ccd3ccd1e79d5f6153e54c0dbefa89bf93139 → 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 5 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 5 years ago by
Reviewers: | → Dima Pasechnik |
---|---|
Status: | needs_review → positive_review |
Looks good to me; however, it probably needs testing on a 32-bit machine. Hopefully a patchbot will do.
PS. Please enter the author's name in Authors.
comment:10 Changed 5 years ago by
Branch: | u/pleopardi/fix_boolean_function_truth_table_hex → eeaebe309317a0df13b561db53384d5b758a61af |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Patch to boolean_function.pyx to retrun correct value for truth_table(format='hex')