BooleanSolve doctest failing with Python

[Dioprz]

@fmerino21 had shared with me some days ago that one of the UOVEstimator doctest was failing when running with Python instead of Sage.

The failing doctest is this one: https://github.com/Crypto-TII/CryptographicEstimators/blob/9637e57a61f381fabba94dedbc3da7d82fccfee6/cryptographic_estimators/UOVEstimator/uov_estimator.py#L130-L141

Steps to reproduce

1. make docker-run

2. In a python3 REPL, run:

   from cryptographic_estimators.UOVEstimator import UOVEstimator
   A = UOVEstimator(n=184, m=72, q=256, theta=None)
   A.table(show_all_parameters=1) # long time

   You will get:

   ...
   File "/home/cryptographic_estimators/cryptographic_estimators/MQEstimator/MQAlgorithms/booleansolve_fxl.py", line 184, in _compute_time_complexity
     time_complexity = q**k * m * binomial(n - k + wit_deg, wit_deg) ** w
   OverflowError: int too large to convert to float

3. If you run the same in a sage REPL, everything works normally (this will take some minutes).

Solution:

The error comes from the file cryptographic_estimators/MQEstimator/MQAlgorithms/booleansolve_fxl.py, specifically from this lines of the _compute_time_complexity method:

https://github.com/Crypto-TII/CryptographicEstimators/blob/9637e57a61f381fabba94dedbc3da7d82fccfee6/cryptographic_estimators/MQEstimator/MQAlgorithms/booleansolve_fxl.py#L169-L189

Specifically, from the expression q**k * m * binomial(n - k + wit_deg, wit_deg) ** w

The issue can likely be solved by integrating the log2 directly into the if/elif blocks, so logarithms properties help us lowering the powers.

Did you agree? Could any of you help me ensuring this will not break anything (or implementing the patch) please? @Memphisd @Javierverbel @floydz

[Javierverbel]

@Dioprz I pushed a fix for this here