mr_problem¶

class cryptographic_estimators.MREstimator.mr_problem.MRProblem(q: int, m: int, n: int, k: int, r: int, **kwargs)¶

Bases: BaseProblem

Construct an instance of MRProblem.

Contains the parameters to optimize over.

Parameters:

q (int) – Order of the finite field
m (int) – Number of rows of the input matrices
n (int) – Number of columns of the input matrices
k (int) – Length of the solution vector
r (int) – Target rank
theta (float, optional) – Exponent of the conversion factor. Defaults to 2.
nsolutions (int, optional) – Number of solutions in logarithmic scale. Defaults to max(expected_number_solutions, 0).
memory_bound (float, optional) – Maximum allowed memory to use for solving the problem. Defaults to inf.

Note

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.

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

get_parameters()¶: Return the optimizations parameters.

length_solution_vector()¶

Return the length of the solution vector.

Tests:

>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> MRP = MRProblem(q=7, m=9, n=10, k=15, r=4)
>>> MRP.length_solution_vector()
15

ncolumns()¶

Return the number of columns of the input matrix.

Tests:

>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> MRP = MRProblem(q=7, m=9, n=10, k=15, r=4)
>>> MRP.ncolumns()
10

nmatrices()¶

Return the number of input matrices.

Tests:

>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> MRP = MRProblem(q=7, m=9, n=10, k=15, r=4)
>>> MRP.nmatrices()
16

nrows()¶

Return the number of rows of the input matrix.

Tests:

>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> MRP = MRProblem(q=7, m=9, n=10, k=15, r=4)
>>> MRP.nrows()
9

order_of_the_field()¶

Return the order of the field.

Tests:

>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> MRP = MRProblem(q=7, m=9, n=10, k=15, r=4)
>>> MRP.order_of_the_field()
7

target_rank()¶

Return the target rank.

Tests:

>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> MRP = MRProblem(q=7, m=9, n=10, k=15, r=4)
>>> MRP.target_rank()
4

property theta¶: Returns the value of theta.

to_bitcomplexity_memory(elements_to_store: float)¶

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

Parameters:: elements_to_store (float) – Number of memory operations (logarithmic)

Tests:

>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> MRP = MRProblem(q=7, m=9, n=10, k=15, r=4)
>>> MRP.to_bitcomplexity_memory(100)
101.58496250072116

to_bitcomplexity_time(basic_operations: float)¶

Return the bit-complexity corresponding to a certain amount of basic_operations.

Parameters:: basic_operations (float) – Number of basic operations (logarithmic)

Tests:

>>> from cryptographic_estimators.MREstimator.mr_problem import MRProblem
>>> MRP = MRProblem(q=7, m=9, n=10, k=15, r=4)
>>> MRP.to_bitcomplexity_time(200)
202.97842293847626