# OverflowError: Python int too large to convert to C long in computing discrete logarithm

I was trying to compute Discrete logarithm using sage built in method (Don't worry I am not breaking anyone encryption :))

Firstly I defined:

sage: K = IntegerModRing(170105614024288730080534932284438889283915362533105079405708531244397007382373065644323359440168891115028688155796209240525852365277829421681328386791392246695036645057638022446250013789591527999940334485768929906363644007315425771754703250375664803466636053933683807019651127293211599350458256866324942160707)

sage: bet = K(299196491040445553241951165617051874716829217278833896612973261174009330283715758515678905940210529602777565330455982982515099414428556955210176266584330790683846384281907046378906396818048462302829007217996998618862125614365444917802988738452913630023327621067471115458034040074393242514516474485808146482025)


Then tried to compute:

sage: %time discrete_log_rho(bet, K(2), K(2).order())


After that this irritating error appeared:

sage: %time discrete_log_rho(bet, K(2), K(2).order())
---------------------------------------------------------------------------
OverflowError Traceback (most recent call last)
<ipython-input-16-02136e0a9c28> in <module>()
----> 1 get_ipython().magic(u'time discrete_log_rho(bet, K(2), K(2).order())')

    /home/PRIVATE/sage-6.9-x86_64-Linux/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in magic(self, arg_s)
2334         magic_name, _, magic_arg_s = arg_s.partition(' ')
2335         magic_name = magic_name.lstrip(prefilter.ESC_MAGIC)
-> 2336         return self.run_line_magic(magic_name, magic_arg_s)
2337
2338     #-------------------------------------------------------------------------

/home/PRIVATE/sage-6.9-x86_64-Linux/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in run_line_magic(self, magic_name, line)
2255                 kwargs['local_ns'] = sys._getframe(stack_depth).f_locals
2256             with self.builtin_trap:
-> 2257                 result = fn(*args,**kwargs)
2258             return result
2259

/home/PRIVATE/sage-6.9-x86_64-Linux/local/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in time(self, line, cell, local_ns)

/home/PRIVATE/sage-6.9-x86_64-Linux/local/lib/python2.7/site-packages/IPython/core/magic.pyc in <lambda>(f, *a, **k)
191     # but it's overkill for just that one bit of state.
192     def magic_deco(arg):
--> 193         call = lambda f, *a, **k: f(*a, **k)
194
195         if callable(arg):

/home/PRIVATE/sage-6.9-x86_64-Linux/local/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in time(self, line, cell, local_ns)
1161         if mode=='eval':
1162             st = clock2()
-> 1163             out = eval(code, glob, local_ns)
1164             end = clock2()
1165         else:

<timed eval> in <module>()

/home/PRIVATE/sage-6.9-x86_64-Linux/local/lib/python2.7/site-packages/sage/groups/generic.pyc in discrete_log_rho(a, base, ord, operation, hash_function)
627         i0=0
628         nextsigma = 0
--> 629         for i in xrange(reset_bound):
630                     #random walk, we need an efficient hash
631             s=hash_function(x) % partition_size

OverflowError: Python int too large to convert to C long


I can't get my head around this problem, I've tried to edit groups.py replacing xrange by itertools as suggested in hxxp://stackoverflow.com/questions/22114088/overflowerror-python-int-too-large-to-convert-to-c-long but the same problem still there!

Detailed solution: to be written here soon.

First of all as error suggests that xrange function cause some problem, the file /home/your_home/sage-6.9-x86_64-Linux/local/lib/python2.7/site-packages/sage/groups/generic.py need to be edited.

add the line import itertools in the beginning of that file, then go direct to the function discrete_log_rho, look up for the last loop for, its location should be in line 631.Next, Define a new variable iterator = 1, replace "xrange(reset_bound):" by "itertools.count(1):" Finally, make sure to increase iterator by with each iteration, and to terminate for loop if the condition is satisfied. In the end you will have something like:

    itereator = 1 #By Triviality
for i in itertools.count(1):
#random walk, we need an efficient hash
s=hash_function(x) % partition_size
(x,ax,bx) = (mult(M[s],x), ax+m[s], bx ...
edit retag close merge delete

Sort by ยป oldest newest most voted

When you modified the Sage source code in /home/PRIVATE/sage-6.9-x86_64-Linux/src/sage/groups/generic.py did you run sage -b (from a terminal) afterwards so that Sage knows about your changes ?

more

It never occurred me, since sage shows original script which has been already edited. I think it works perfectly now(waiting for the numerical result). Thank you very much for your quick response, I wish that I can up vote your post.

( 2016-01-03 20:02:36 +0200 )edit
1

That said, i hope (in the probabilistic sense) that the rho method will find a collision earlier, because it is unlikely that such a huge loop will end before you die.

( 2016-01-03 20:49:29 +0200 )edit