Numerical Result Out of Range

[Pro7ech]

The following parameters returned a (34, numerical result out of range) error after a few hours of computation :

n = 1<<16
q = next_prime(2^121)
alpha = 8/q
hybrid_primal(n, alpha, q, secret_distribution=((-1,1),32), reduction_cost_model = BKZ.sieve)

[yonghaason]

My laptop (MacOS, SageMath 9.0) outputs different error, and I presume that you're using different OS or version. Anyway I correct the script to remove my-side error, and would you please try again ? If the same error occurs again, it would be helpful to see the error log.

[Pro7ech]

I'm using Window 10 and SageMath 9.2. I'll try again with the previous version of the script to give you the full error log, try the updated version and get back to you as soon as I have the results.

[Pro7ech]

This is the full log of the error :

NOTE: Hybrid-Primal estimation may takes LONG LONG time (even few hours) for large HE parameters.

Please Wait Until "Final result" is printed.
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-1-ea84b77a54a4> in <module>
      6 #hybrid_dual(n, alpha, q, secret_distribution=((-1,1), 128), reduction_cost_model = BKZ.sieve)
      7 print("Primal")
----> 8 hybrid_primal(n, alpha, q, secret_distribution=((-Integer(1),Integer(1)),Integer(32)), reduction_cost_model = BKZ.sieve)

~/Desktop/Extimator Updated/estimator_sparseLWE.py in hybrid_primal(n, alpha, q, secret_distribution, m, success_probability, reduction_cost_model, init_delta_P, opt_GSA, verbose)
   3060         current_post = cost_function_delta(n, q, alpha, h, best["delta_0"] + delta_step, m_max,
   3061                                           reduction_cost_model=reduction_cost_model,
-> 3062                                           opt_GSA=opt_GSA, verbose=verbose)
   3063 
   3064         delta_step /= 2

~/Desktop/Extimator Updated/estimator_sparseLWE.py in cost_function_delta(n, q, alpha, h, delta_P, m_max, reduction_cost_model, opt_GSA, verbose)
   2924 
   2925     best_delta = my_binary_search(cost_function_r, start = 0, stop = n, param="r", 
-> 2926                                 predicate=lambda x, best: RR(x["rop"])<=RR(best["rop"]), **kwds)
   2927 
   2928 

~/Desktop/Extimator Updated/estimator_sparseLWE.py in my_binary_search(f, start, stop, param, predicate, *arg, **kwds)
   2819         if b not in D:
   2820             kwds[param] = b
-> 2821             D[b] = f(*arg, **kwds)
   2822         if b == start:
   2823             best = D[start]

~/Desktop/Extimator Updated/estimator_sparseLWE.py in cost_function_r(n, q, alpha, h, r, delta_P, m_max, reduction_cost_model, opt_GSA, verbose)
   2943 
   2944     p_NP, m, dim, R = my_binary_search(prob_NP_and_GSA, start = 50, stop = 2*n, param="m", 
-> 2945                                 predicate=lambda x, best: RR(x[0])>=RR(best[0]), **kwds)
   2946 
   2947     current = lattice_reduction_cost(reduction_cost_model, delta_P, dim, B=log(q, 2))

~/Desktop/Extimator Updated/estimator_sparseLWE.py in my_binary_search(f, start, stop, param, predicate, *arg, **kwds)
   2812     kwds[param] = stop
   2813     D = {}
-> 2814     D[stop] = f(*arg, **kwds)
   2815     best = D[stop]
   2816     b = ceil((start+stop)/2)

~/Desktop/Extimator Updated/estimator_sparseLWE.py in prob_NP_and_GSA(m, n, alpha, q, r, delta_0, opt_GSA, h, h_M)
   2890         R = Mod_GSA(m, q, dim, delta_0, scale)
   2891     else:
-> 2892         R = GSA(m, q, dim, delta_0, scale)
   2893 
   2894     probs = [RR(R[i] * scaling_factor).erf() for i in range(len(R))]

~/Desktop/Extimator Updated/estimator_sparseLWE.py in GSA(m, q, dim, delta_0, scale)
   2900 def GSA(m, q, dim, delta_0, scale):
   2901     det = RR((q**m * scale**(dim-m))**(1/dim))
-> 2902     b = [delta_0**(dim-2*i) * det for i in range(dim)]
   2903     return b
   2904 

~/Desktop/Extimator Updated/estimator_sparseLWE.py in <listcomp>(.0)
   2900 def GSA(m, q, dim, delta_0, scale):
   2901     det = RR((q**m * scale**(dim-m))**(1/dim))
-> 2902     b = [delta_0**(dim-2*i) * det for i in range(dim)]
   2903     return b
   2904 

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/integer.pyx in sage.rings.integer.Integer.__pow__ (build/cythonized/sage/rings/integer.c:15222)()
   2206             return coercion_model.bin_op(left, right, operator.pow)
   2207         # left is a non-Element: do the powering with a Python int
-> 2208         return left ** int(right)
   2209 
   2210     cpdef _pow_(self, other):

OverflowError: (34, 'Numerical result out of range')

[Pro7ech]

I run in this error (for all secrets, uniform or sparse) with the updated version (that I solved by adding secret_distribution=secret_distribution to duald):

from estimator_sparseLWE import *
n = 1<<16
q = next_prime(2^121)
alpha = 8/q
hybrid_primal(n, alpha, q, secret_distribution=((-1,1), 64), reduction_cost_model = BKZ.sieve)

NOTE: Hybrid-Primal estimation may takes LONG LONG time (even few hours) for large HE parameters.

Please Wait Until "Final result" is printed.
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-5-5021d03f83d3> in <module>
      3 q = next_prime(Integer(2)**Integer(121))
      4 alpha = Integer(8)/q
----> 5 hybrid_primal(n, alpha, q, secret_distribution=((-Integer(1),Integer(1)), Integer(64)), reduction_cost_model = BKZ.sieve)

~/Desktop/SparseLWE-estimator-main/estimator_sparseLWE.py in hybrid_primal(n, alpha, q, secret_distribution, m, success_probability, reduction_cost_model, init_delta_P, opt_GSA, verbose)
   3043     if init_delta_P == None:
   3044         duald = partial(drop_and_solve, dual_scale)
-> 3045         best = duald(n=n, alpha=alpha, q=q, m=m, reduction_cost_model=reduction_cost_model)
   3046         init_delta_P = (best["delta_0"] + 1) / 2
   3047     delta_step = min(0.005, (init_delta_P - 1)/2)

~/Desktop/SparseLWE-estimator-main/estimator_sparseLWE.py in drop_and_solve(f, n, alpha, q, secret_distribution, success_probability, postprocess, decision, rotations, **kwds)
   1798 
   1799     if not SDis.is_bounded_uniform(secret_distribution):
-> 1800         raise NotImplementedError("Only bounded uniform secrets are currently supported.")
   1801 
   1802     a, b = SDis.bounds(secret_distribution)

NotImplementedError: Only bounded uniform secrets are currently supported.

[Pro7ech]

I tried

from estimator_sparseLWE import *
n = 1<<16
q = next_prime(2^121)
alpha = 8/q
hybrid_primal(n, alpha, q, secret_distribution=((-1,1), 64), reduction_cost_model = BKZ.sieve)

After 5 hours and a memrory of about 27GB, it returned this error :

NOTE: Hybrid-Primal estimation may takes LONG LONG time (even few hours) for large HE parameters.
Please Wait Until "Final result" is printed.
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-1-5021d03f83d3> in <module>
      3 q = next_prime(Integer(2)**Integer(121))
      4 alpha = Integer(8)/q
----> 5 hybrid_primal(n, alpha, q, secret_distribution=((-Integer(1),Integer(1)), Integer(64)), reduction_cost_model = BKZ.sieve)

~/Desktop/SparseLWE-estimator-main/estimator_sparseLWE.py in hybrid_primal(n, alpha, q, secret_distribution, m, success_probability, reduction_cost_model, init_delta_P, opt_GSA, verbose)
   3063         current_post = cost_function_delta(n, q, alpha, h, best["delta_0"] + delta_step, m_max,
   3064                                           reduction_cost_model=reduction_cost_model,
-> 3065                                           opt_GSA=opt_GSA, verbose=verbose)
   3066 
   3067         delta_step /= 2

~/Desktop/SparseLWE-estimator-main/estimator_sparseLWE.py in cost_function_delta(n, q, alpha, h, delta_P, m_max, reduction_cost_model, opt_GSA, verbose)
   2924 
   2925     best_delta = my_binary_search(cost_function_r, start = 0, stop = n, param="r", 
-> 2926                                 predicate=lambda x, best: RR(x["rop"])<=RR(best["rop"]), **kwds)
   2927 
   2928 

~/Desktop/SparseLWE-estimator-main/estimator_sparseLWE.py in my_binary_search(f, start, stop, param, predicate, *arg, **kwds)
   2819         if b not in D:
   2820             kwds[param] = b
-> 2821             D[b] = f(*arg, **kwds)
   2822         if b == start:
   2823             best = D[start]

~/Desktop/SparseLWE-estimator-main/estimator_sparseLWE.py in cost_function_r(n, q, alpha, h, r, delta_P, m_max, reduction_cost_model, opt_GSA, verbose)
   2982         else:
   2983             R = GSA(m, q, dim, delta_P, scale)
-> 2984         p_s = prob_s(R, alpha, q, m)
   2985         if Wsize * p_c * p_s < 1:
   2986             L = Wsize

~/Desktop/SparseLWE-estimator-main/estimator_sparseLWE.py in prob_s(R, alpha, q, m)
   2872     scaling_factor = RR(sqrt(pi) / (2*alpha*q))
   2873     probs = [RR(2 * R[i] * scaling_factor).erf() for i in range(len(R))]
-> 2874     results = [probs[i] + (exp(-(2 * R[i] *scaling_factor)**2) - 1) / (2 * sqrt(pi) * R[i] * scaling_factor) for i in range(len(R))]
   2875     return prod(results)
   2876 

~/Desktop/SparseLWE-estimator-main/estimator_sparseLWE.py in <listcomp>(.0)
   2872     scaling_factor = RR(sqrt(pi) / (2*alpha*q))
   2873     probs = [RR(2 * R[i] * scaling_factor).erf() for i in range(len(R))]
-> 2874     results = [probs[i] + (exp(-(2 * R[i] *scaling_factor)**2) - 1) / (2 * sqrt(pi) * R[i] * scaling_factor) for i in range(len(R))]
   2875     return prod(results)
   2876 

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/symbolic/function.pyx in sage.symbolic.function.BuiltinFunction.__call__ (build/cythonized/sage/symbolic/function.cpp:12299)()
   1145                 if callable(method):
   1146                     try:
-> 1147                         res = method(*method_args[1:])
   1148                     except (TypeError, ValueError, ArithmeticError):
   1149                         pass

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression.exp (build/cythonized/sage/symbolic/expression.cpp:48118)()
   8958         """
   8959         return new_Expression_from_GEx(self._parent,
-> 8960                 g_hold_wrapper(g_exp, self._gobj, hold))
   8961 
   8962     def log(self, b=None, hold=False):

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/libs/pynac/pynac.pyx in sage.libs.pynac.pynac.py_float (build/cythonized/sage/libs/pynac/pynac.cpp:15713)()
   1351         else:
   1352             try:
-> 1353                 return p(n)
   1354             except (TypeError,ValueError):
   1355                 return p.complex_field()(n)

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9337)()
    898         if mor is not None:
    899             if no_extra_args:
--> 900                 return mor._call_(x)
    901             else:
    902                 return mor._call_with_args(x, args, kwds)

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.NamedConvertMap._call_ (build/cythonized/sage/structure/coerce_maps.c:6043)()
    285             raise TypeError("Cannot coerce {} to {}".format(x, C))
    286         cdef Map m
--> 287         cdef Element e = method(C)
    288         if e is None:
    289             raise RuntimeError("BUG in coercion model: {} method of {} returned None".format(self.method_name, type(x)))

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/complex_arb.pyx in sage.rings.complex_arb.ComplexBall._mpfr_ (build/cythonized/sage/rings/complex_arb.c:15294)()
   1630         """
   1631         if acb_is_real(self.value):
-> 1632             return parent(self.real())
   1633         else:
   1634             raise ValueError("nonzero imaginary part")

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9337)()
    898         if mor is not None:
    899             if no_extra_args:
--> 900                 return mor._call_(x)
    901             else:
    902                 return mor._call_with_args(x, args, kwds)

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.NamedConvertMap._call_ (build/cythonized/sage/structure/coerce_maps.c:6043)()
    285             raise TypeError("Cannot coerce {} to {}".format(x, C))
    286         cdef Map m
--> 287         cdef Element e = method(C)
    288         if e is None:
    289             raise RuntimeError("BUG in coercion model: {} method of {} returned None".format(self.method_name, type(x)))

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/real_arb.pyx in sage.rings.real_arb.RealBall._mpfr_ (build/cythonized/sage/rings/real_arb.c:14300)()
   1604                 field.rnd == MPFR_RNDZ and arb_contains_zero(self.value)):
   1605             mid = RealNumber(field, None)
-> 1606             sig_str("unable to convert to MPFR (exponent out of range?)")
   1607             arf_get_mpfr(mid.value, arb_midref(self.value), field.rnd)
   1608             sig_off()

RuntimeError: unable to convert to MPFR (exponent out of range?)

[gong-cr]

I have the same issue (OverflowError: (34, 'Numerical result out of range')) when trying the hybrid primal example from README file. The log also shows the error is raised from /opt/sagemath-9.3/local/lib/python3.7/site-packages/sage/rings/integer.pyx in sage.rings.integer.Integer.pow (build/cythonized/sage/rings/integer.c:15219)() 2206 return coercion_model.bin_op(left, right, operator.pow) 2207 # left is a non-Element: do the powering with a Python int -> 2208 return left ** int(right) 2209 2210 cpdef pow(self, other):