Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

asked 2016-01-03 19:18:57 +0100

A.Alharbi gravatar image

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(1042581697795350988926375176023147567119634654525968384680064458805236495557780186336768321198680378827882923866690089649068437728564380119971343897249733757180088154026480449177119491716013304499492130858244810907376593879710509787)


sage: bet = K(555780511850336599590213333717318815910873825538052251610340319714352106225826998876713496327750311385082389857312090818482139320119124693186033344647111179528404852638310198274804551640237429724147046130759135433389268219707958469)

sage: K(2).multiplicative_order()

1042581697795350988926375176023147567119634654525968384680064458805236495557780186336768321198680378827882923866690089649068437728564380119971343897249733757180088154026480449177119491716013304499492130858244810907376593879710509786

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!

Hints would be appreciated.

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(1042581697795350988926375176023147567119634654525968384680064458805236495557780186336768321198680378827882923866690089649068437728564380119971343897249733757180088154026480449177119491716013304499492130858244810907376593879710509787)
IntegerModRing(170105614024288730080534932284438889283915362533105079405708531244397007382373065644323359440168891115028688155796209240525852365277829421681328386791392246695036645057638022446250013789591527999940334485768929906363644007315425771754703250375664803466636053933683807019651127293211599350458256866324942160707)


sage: bet = K(555780511850336599590213333717318815910873825538052251610340319714352106225826998876713496327750311385082389857312090818482139320119124693186033344647111179528404852638310198274804551640237429724147046130759135433389268219707958469)

sage: K(2).multiplicative_order()

1042581697795350988926375176023147567119634654525968384680064458805236495557780186336768321198680378827882923866690089649068437728564380119971343897249733757180088154026480449177119491716013304499492130858244810907376593879710509786
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!

Hints would be appreciated.

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.

Hints would be appreciated.

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.

Hints would 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 appreciated.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+n[s])
        if mut:
            x.set_immutable()
        # look for collisions
        if x in H:
            ay,by=H[x]
            if bx == by:
                break
            else:
                res = sage.rings.integer.Integer((ay-ax)/(bx-by))
                if power(base,res) == a:
                    return res
                else:
                    break
        itereator += 1#By Triviality
        if itereator == Integer(reset_bound):#By Triviality
            break#By Triviality
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59