#2356 closed defect (fixed)
[with patch, with positive reviews] Bug in discrete_log_generic
Reported by: | cremona | Owned by: | cremona |
---|---|---|---|
Priority: | major | Milestone: | sage-2.10.3 |
Component: | group theory | Keywords: | |
Cc: | marshbuck@… | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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)
- 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:
- Note that this is related to #277
- I already suggested using a dict for the lookup instead of using lists or sets
I will post a patch.
Attachments (1)
Change History (8)
Changed 12 years ago by
comment:1 Changed 12 years ago by
- Summary changed from Bug in discrete_log_generic to [with patch, needs review] Bug in discrete_log_generic
comment:2 Changed 12 years ago by
- Milestone set to sage-2.10.3
- Owner changed from joyner to cremona
- Status changed from new to assigned
comment:3 Changed 12 years ago by
- Summary changed from [with patch, needs review] Bug in discrete_log_generic to [with patch, positive review] Bug in discrete_log_generic
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.
comment:4 follow-up: ↓ 5 Changed 12 years ago by
- Summary changed from [with patch, positive review] Bug in discrete_log_generic to [with patch, with positive reviews] Bug in discrete_log_generic
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!
comment:5 in reply to: ↑ 4 Changed 12 years ago by
Replying to cremona:
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
comment:6 Changed 12 years ago by
- Resolution set to fixed
- Status changed from assigned to closed
Merged both in Sage 2.10.3.rc2
comment:7 Changed 12 years ago by
Merged the *only* patch in Sage 2.10.3.rc2 - sorry for the confusion - I meant ticket #277.
Attached patch 8682 fixes both issues: increases m by 1 and uses a dict() for fast lookup of the table.