Opened 15 months ago

Last modified 8 weeks ago

#31634 new defect

discrete_log may fail when valid "order" parameter is provided although log exists

Reported by: gh-eduenez Owned by:
Priority: major Milestone: sage-9.7
Component: group theory Keywords: discrete_log, babystep-giantstep
Cc: Merged in:
Authors: Eduardo Dueñez Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

When discrete_log is called with an order parameter (i.e., in the form discrete_log(a, b, order)), it can fail throwing an exception triggered by the call to Babystep-Giantstep bsgs, even though the provided order is valid according to the documentation (being equal to a proper multiple of the exact order of b), and the log itself exists.

If the order parameter is omitted or equal to the exact order of b, the bug does not seem to be triggered.

sage: version()                                                                                                                                
'SageMath version 9.2, Release Date: 2020-10-24'
sage: p = 3571                                                                                                                                 
sage: p in Primes()                                                                                                                            
True
sage: F = GF(p)                                                                                                                                
sage: a = F(2213)                                                                                                                              
sage: b = F(650)                                                                                                                               
sage: discrete_log(a, b)                                                                                                                       
319
sage: b.multiplicative_order()                                                                                                                 
510
sage: discrete_log(a, b, 510)                                                                                                                  
319
sage: discrete_log(a, b, 4*510)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/groups/generic.py in discrete_log(a, base, ord, bounds, operation, identity, inverse, op)
    828                 if operation in multiplication_names:
--> 829                     c=bsgs(base**(ord//pi),(a/base**l[i])**(ord//pi**(j+1)),(0,pi),operation=operation)
    830                     l[i] += c*(pi**j)

/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/groups/generic.py in bsgs(a, b, bounds, operation, identity, inverse, op)
    485             d = op(a,d)
--> 486         raise ValueError("No solution in bsgs()")
    487 

ValueError: No solution in bsgs()

During handling of the above exception, another exception occurred:

ValueError                                Traceback (most recent call last)
<ipython-input-13-d289f24fe9c3> in <module>
----> 1 discrete_log(a, b, Integer(4)*Integer(510))

/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/groups/generic.py in discrete_log(a, base, ord, bounds, operation, identity, inverse, op)
    835         return  CRT_list(l,[pi**ri for pi,ri in f])
    836     except ValueError:
--> 837         raise ValueError("No discrete log of %s found to base %s"%(a,base))
    838 
    839 

ValueError: No discrete log of 2213 found to base 650
sage:   

Change History (5)

comment:1 Changed 15 months ago by gh-eduenez

  • Summary changed from discrete_log may fail when valid "ord" parameter is provided although log exists to discrete_log may fail when valid "order" parameter is provided although log exists

comment:2 Changed 14 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Moving to 9.4, as 9.3 has been released.

comment:3 Changed 10 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:4 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:5 Changed 8 weeks ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.