Loading...
Please wait, while we are loading the content...
Similar Documents
Optimized baby step-giant step methods (2005).
| Content Provider | CiteSeerX |
|---|---|
| Author | Stein, Andreas Teske, Edlyn |
| Abstract | Shanks’ baby step-giant step algorithm is known to be a generic method for computing element orders and discrete logarithms in any finite abelian group. We show how this method can be optimized in various applications where more is known about the underlying group than just the group operation itself. Additional information includes situations when the distribution of the solution in a given search interval is known, when symmetries in the search interval or less expensive inversions exist, and when baby steps are less expensive than giant steps. In each case, this additional information can be readily used to obtain a speed-up of the algorithm. We apply the optimized methods to the computation of invariants of hyperelliptic function fields. Hereby, we are able to verify the speed-up in an important application. |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Baby Step-giant Step Method Search Interval Additional Information Group Operation Generic Method Giant Step Step-giant Step Algorithm Mathematics Subject Classification Discrete Logarithm Important Application Hyperelliptic Function Field Finite Abelian Group Baby Step Optimized Method Various Application Expensive Inversion Element Order |
| Content Type | Text |
