sageuser1's profile - activity

@asante Thank you for your update!

Please update us with the final resolution. Beside that, don't you think that the time needed (200 ms) for finding nonlinearity() of one vectorial boolean function (8 x 8) in SageMath 8.1 is too much, too?

I have updated the post with the code I have used to profile the slowdown.

Average time in nonlinearity() in v.8.1. was *200 ms Average time in nonlinearity() in v.8.2 is 5.1 s*

Here is the code I have used in order to track the issue:

sage: for j in range(10):
....:     S = [x for x in range(256)];shuffle(S)
....:     S = sage.crypto.sbox.SBox(S)
....:     %time S.nonlinearity()

Results from Sage 8.1

CPU times: user 237 ms, sys: 1.87 ms, total: 239 ms
Wall time: 236 ms
94
CPU times: user 208 ms, sys: 12.5 ms, total: 220 ms
Wall time: 220 ms
94
CPU times: user 287 ms, sys: 1.41 ms, total: 288 ms
Wall time: 288 ms
92
....

Results from Sage 8.2

CPU times: user 5.12 s, sys: 30.6 ms, total: 5.15 s
Wall time: 5.16 s
92
CPU times: user 5.04 s, sys: 14.3 ms, total: 5.05 s
Wall time: 5.05 s
96
CPU times: user 5.08 s, sys: 13 ms, total: 5.09 s
Wall time: 5.09 s
94
CPU times: user 5.03 s, sys: 8.56 ms, total: 5.04 s
Wall time: 5.04 s
92
.....

Thank you for the update!

I confirm the same behavior under Sage version 7.4

I am using SageMath version 7.2 (EDIT: I confirm the same behavior under Sage version 7.4)

sage: B = random_boolean_function(3)
sage: get_memory_usage()
732.5078125
sage: B.algebraic_normal_form()
x0*x1*x2 + x0*x1 + x0 + x2
sage: get_memory_usage()
743.53125
sage: B.algebraic_normal_form()
x0*x1*x2 + x0*x1 + x0 + x2
sage: get_memory_usage()
749.04296875
sage: B.algebraic_normal_form()
x0*x1*x2 + x0*x1 + x0 + x2
sage: get_memory_usage()
754.6875
sage: B.algebraic_normal_form()
x0*x1*x2 + x0*x1 + x0 + x2
sage: get_memory_usage()
760.19921875

After each ANF call the memory used is rising. Is this a memory leak?

I want to find the Algebraic Normal Form of a boolean function.

For example:

sage: R.<x1,x2,x3> = BooleanPolynomialRing(3, order='degneglex')
sage: x3>x1
True

sage: L = BooleanFunction(x1+x2*x3)

sage: L.truth_table()
(False, True, False, True, False, True, True, False)

sage: L.algebraic_normal_form()
x0 + x1*x2

Unfortunately, Algebraic Normal Form of this specific boolean function is not correct (x0 should be x3, x1 should be x2 and x2 should be x1). The answer of the ANF() method is in order='lex' (not as I desired in order = 'degneglex'). Furthermore, the ANF() form is calculated out of this ring (x0 involved?)

How should I extract the ANF() in correct syntax (where x3>x2>x1)?