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:

GitHub link to the corresponding issue

Description (last modified by dimpase)

Sometimes, especially with functions of 8 variables, the method BooleanFunction.truth_table(format='hex") returns incorrect values that are also too long.


sage: from sage.rings.integer_ring import ZZ
sage: from sage.crypto.boolean_function import BooleanFunction
sage: hex_str = "0123456789112345678921234567893123456789412345678951234567896123"
sage: len(hex_str)
sage: bf = BooleanFunction(hex_str)
sage: bf.nvariables()
sage: bf_tt_hex = bf.truth_table(format="hex")
sage: bf_tt_hex
sage: len(bf_tt_hex)
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
sage: len(tt_hex)

The example also shows how the code in 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)

boolean_function-correct_truth_table_hex.patch (844 bytes) - added by pleopardi 5 years ago.
Patch to boolean_function.pyx to retrun correct value for truth_table(format='hex')

Download all attachments as: .zip

Change History (11)

Changed 5 years ago by pleopardi

Patch to boolean_function.pyx to retrun correct value for truth_table(format='hex')

comment:1 Changed 5 years ago by dimpase

Description: modified (diff)
Milestone: sage-8.1sage-8.2

Thanks. Could you provide a test example and a git branch for the fix, too?

comment:2 Changed 5 years ago by pleopardi

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 pleopardi

Also, I am new at providing Git branches for Sage. I will carefully read the instructions at and use them to provide a Git branch. This may have to wait until the weekend.

comment:4 Changed 5 years ago by pleopardi

Branch: u/pleopardi/fix_boolean_function_truth_table_hex
Commit: d22ccd3ccd1e79d5f6153e54c0dbefa89bf93139
Status: newneeds_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 dimpase

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 git

Commit: d22ccd3ccd1e79d5f6153e54c0dbefa89bf93139eeaebe309317a0df13b561db53384d5b758a61af

Branch pushed to git repo; I updated commit sha1. New commits:

eeaebe3Remove some len expressions from doctest for BooleanFunction.truth_table

comment:7 Changed 5 years ago by pleopardi

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 dimpase

Reviewers: Dima Pasechnik
Status: needs_reviewpositive_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:9 Changed 5 years ago by pleopardi

Authors: Paul Leopardi

I have added my name to Authors.

comment:10 Changed 5 years ago by vbraun

Branch: u/pleopardi/fix_boolean_function_truth_table_hexeeaebe309317a0df13b561db53384d5b758a61af
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.