|
A modification of Shanks' baby-step giant-step algorithm
Author(s):
David
C.
Terr.
Journal:
Math. Comp.
69
(2000),
767-773.
MSC (1991):
Primary 68P10, 20C40
Posted:
March 4, 1999
MathSciNet review:
1653994
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
I describe a modification to Shanks' baby-step giant-step algorithm for computing the order of an element of a group , assuming is finite. My method has the advantage of being able to compute quickly, which Shanks' method fails to do when the order of is infinite, unknown, or much larger than . I describe the algorithm in detail. I also present the results of implementations of my algorithm, as well as those of a similar algorithm developed by Buchmann, Jacobson, and Teske, for calculating the order of various ideal classes of imaginary quadratic orders.
References:
- [1]
- J. Buchmann, M.J. Jacobson, Jr., and E. Teske, ``On Some Computational Problems in Finite Abelian Groups", Math. Comp. 66 (1997), pp. 1663-1687. MR 98a:11185
- [2]
- D. E. Knuth, ``The Art of Computer Programming", vol. 3 (1973), pp. 1-99 (prob. 17). MR 56:4281
- [3]
- ``Dave's Cool Java Home Page", http://www.geocities.com/CapeCanaveral /LaunchPad/5318 (1998).
Similar Articles:
Retrieve articles in Mathematics of Computation
with
MSC (1991):
68P10, 20C40
Retrieve articles in all Journals with
MSC (1991):
68P10, 20C40
Additional Information:
David
C.
Terr
Affiliation:
2614 Warring St. #7, Berkeley, CA 94704
Email:
davidcterr@aol.com
DOI:
10.1090/S0025-5718-99-01141-2
PII:
S 0025-5718(99)01141-2
Received by editor(s):
September 4, 1996
Received by editor(s) in revised form:
May 30, 1998
Posted:
March 4, 1999
Copyright of article:
Copyright
2000,
American Mathematical Society
|