[with positive reviews] Bug in discrete_log_generic

[JohnCremona]

Marshall Buck reports (email to sage-support 2008-02-29):

Problem 1. Fails because the list sizes in the baby step giant step method are too small.

Example. [NB This particular example does not fail with 2.10.2]

F.<w> = GF(121)
v = w^120
v.log(w)

bombs with:

File "/usr/local/sage/local/lib/python2.5/site-packages/sage/rings/
arith.py", line 2164, in discrete_log_generic
   raise ValueError, "Log of %s to the base %s does not exist."%(a,b)
ValueError: Log of 2*w + 10 to the base w does not exist.

This can be fixed by changing the append loop to make "g" to {{{range(m +1)}}} instead of range(m). This makes g m+2 long and S2 m-long. Then {{{(m +2)*m >= ord}}}.

   m = ord.isqrt()
   g = [a]
   c = b**(-m)
   S2 = [1]
   for i in range(m+1):  # suggested line change   ---  was range(m)
       g.append(g[i]*c)
       if i < m-1:
           S2.append(S2[i]*b)
   for y in g:
       if y in S2:
           x = S2.index(y)
           return Z(m*(g.index(y)) + x)

2. The other problem is the inefficiency in the lookup " {{{for y in g: if y in S2:}}} ". The work is proportional to "ord", insead of proportional to "m" as intended by BSGS method. It is quicker to do a set lookup:

 S2set = set(S2)
 for y in g:
     if y in S2set:
         x = S2.index(y)...

---

Coments by John Cremona:

1. Note that this is related to #277

2. I already suggested using a dict for the lookup instead of using lists or sets

I will post a patch.

CC: marshbuck@gmail.com

Component: group theory

Issue created by migration from https://trac.sagemath.org/ticket/2356

[JohnCremona]

comment:1

Attachment: 8682.patch.gz

Attached patch 8682 fixes both issues: increases m by 1 and uses a dict() for fast lookup of the table.

[wdjoyner]

comment:3

Applied cleanly to 2.10.3.rc0 and passed sage -testall. Also,

sage: F.<w> = GF(121)
sage: v = w^120
sage: v.log(w)
0

works as it should. Recommend acceptance.

[JohnCremona]

comment:4

The two new patches to #2356 -- which have a positive review! -- need to be applied after this one. They do in fact supercede this one, there therefore this one gets another positive review by default. I'm sure I am breaking protocol by adding that myself but seriously!

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:5

Replying to @JohnCremona:

The two new patches to #2356 -- which have a positive review! -- need to be applied after this one. They do in fact supercede this one, there therefore this one gets another positive review by default. I'm sure I am breaking protocol by adding that myself but seriously!

Hi John,

I assume you refer to the two patches at #277 instead of "The two new patches to #2356 -- which have a positive review!". The positive review is fine in this case and not a breaking of protocol - we shouldn't and don't enforce rules for the sake of rules :)

I will merge both patches shortly and close the tickets assuming the patches apply.

Cheers,

Michael

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:6

Merged both in Sage 2.10.3.rc2

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:7

Merged the only patch in Sage 2.10.3.rc2 - sorry for the confusion - I meant ticket #277.