Ask Your Question
2

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

asked 2016-01-03 12:18:57 -0600

A.Alharbi gravatar image

updated 2016-01-09 04:29:32 -0600

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 ...
(more)
edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2016-01-03 12:22:41 -0600

tmonteil gravatar image

updated 2016-01-03 12:26:43 -0600

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 ?

edit flag offensive delete link more

Comments

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.

A.Alharbi gravatar imageA.Alharbi ( 2016-01-03 13:02:36 -0600 )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.

tmonteil gravatar imagetmonteil ( 2016-01-03 13:49:29 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-01-03 12:18:57 -0600

Seen: 1,638 times

Last updated: Jan 09 '16