mq_problem¶

class cryptographic_estimators.MQEstimator.mq_problem.MQProblem(n: int, m: int, q: int, **kwargs)¶

Bases: BaseProblem

Construct an instance of MQProblem.

Parameters:

n (int) – The number of variables.
m (int) – The number of polynomials.
q (int) – The order of the finite field (default: None).
theta (float, optional) – The exponent of the conversion factor. - If 0 <= theta <= 2, every multiplication in GF(q) is counted as log2(q) ^ theta binary operation. - If theta = None, every multiplication in GF(q) is counted as 2 * log2(q) ^ 2 + log2(q) binary operation.
nsolutions (int, optional) – The number of solutions in logarithmic scale (default: max(expected_number_solutions, 0)).
memory_bound (float, optional) – The maximum allowed memory to use for solving the problem (default: inf).

expected_number_solutions()¶: Returns the logarithm of the expected number of existing solutions to the problem.

get_parameters()¶: Return the optimizations parameters.

get_problem_parameters()¶: Returns the problem parameters n, m, and q.

is_defined_over_finite_field()¶

Determine if the algorithm is defined over a finite field.

Returns:: True if the algorithm is defined over a finite field, False otherwise.
Return type:: bool

is_overdefined_system()¶

Determines if the system is overdefined.

Returns:: True if the system is overdefined, False otherwise.
Return type:: bool

Tests:

>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> MQProblem(n=10, m=15, q=4).is_overdefined_system()
True
>>> MQProblem(n=10, m=5, q=4).is_overdefined_system()
False
>>> MQProblem(n=10, m=5, q=4).is_overdefined_system()
False

is_square_system()¶

Determines if the system is underdefined, i.e. there are an equal number of variables and polynomials.

Returns:: True if the system is square.
Return type:: bool

Tests:

>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> MQProblem(n=10, m=10, q=4).is_square_system()
True
>>> MQProblem(n=10, m=5, q=4).is_square_system()
False

is_underdefined_system()¶

Determines if the system is underdefined.

Returns:: True if the system is underdefined, False otherwise.
Return type:: bool

Tests:

>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> MQProblem(n=10, m=5, q=4).is_underdefined_system()
True
>>> MQProblem(n=5, m=10, q=4).is_underdefined_system()
False
>>> MQProblem(n=10, m=10, q=4).is_underdefined_system()
False

npolynomials()¶

Return the number of polynomials.

Tests:

>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> MQProblem(n=10, m=5, q=4).npolynomials()
5

nvariables()¶

Return the number of variables.

Tests:

>>> from cryptographic_estimators.MQEstimator.mq_problem import MQProblem
>>> MQProblem(n=10, m=5, q=4).nvariables()
10

order_of_the_field()¶: Return the order of the field.

property theta¶: Returns the runtime of the algorithm.

to_bitcomplexity_memory(elements_to_store: float)¶

Returns the memory bit-complexity associated with a given number of elements to store.

Parameters:: elements_to_store (float) – The number of basic memory operations (logarithmic).

to_bitcomplexity_time(basic_operations: float)¶

Returns the bit-complexity corresponding to basic_operations field multiplications.

Parameters:: basic_operations (float) – The number of field additions (logarithmic).