estimator.arora_gb

estimator.arora_gb(n, alpha, q, secret_distribution=True, m=<Mock name='mock()' id='139938827128976'>, success_probability=0.99, omega=2)[source]

Arora-GB as described in [AroGe11,ACFP14]_

Parameters:
  • n – LWE dimension n > 0
  • alpha – noise rate 0 ≤ α < 1, noise will have standard deviation αq/sqrt{2π}
  • q – modulus 0 < q
  • secret_distribution – distribution of secret, see module level documentation for details
  • m – number of LWE samples m > 0
  • success_probability – targeted success probability < 1
  • omega – linear algebra constant
[ACFP14]Albrecht, M. R., Cid, C., Jean-Charles Faug`ere, & Perret, L. (2014). Algebraic algorithms for LWE.
[AroGe11]Arora, S., & Ge, R. (2011). New algorithms for learning in presence of errors. In L. Aceto, M. Henzinger, & J. Sgall, ICALP 2011, Part~I (pp. 403–415). : Springer, Heidelberg.