# Faster arithmetic with function field ideals

Reported by: Owned by: klee major sage-9.5 algebra Kwankyu Lee Travis Scrimshaw N/A 0a77fa5 0a77fa52ca71ec76aca7ad9a7867b66828e6c761

We make ideal arithmetic faster for ideals with two-generators representation.

```sage: K.<x> = FunctionField(GF(2)); _.<Y> = K[]
....: L.<y> = K.extension(Y^7 - x^3*Y - x)
....: O = L.maximal_order()
....: I = O.ideal(y)
....: J = O.ideal(x + y)
sage: def naive_power(i, n):
....:     j = i
....:     for s in range(n - 1):
....:         j *= i
....:     return j
....:
sage: n = 100
sage: i = I / J
sage: %timeit naive_power(i, n)
683 ms ± 8.82 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit i^n
34.3 ms ± 454 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: p, q = i.gens_two()
sage: %timeit naive_power(i, n)  # faster multiplication
147 ms ± 4.08 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit i^n                # faster powering
16.2 ms ± 149 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: naive_power(i, n) == i^n
True
```

### comment:1 Changed 10 months ago by klee

• Authors set to Kwankyu Lee
• Branch set to u/klee/32615

### comment:2 Changed 10 months ago by git

• Commit set to a16530020d7b48e53616880f4987139d1fac749c

Branch pushed to git repo; I updated commit sha1. New commits:

 ​a165300 `Speed up ideal multiplication`

### comment:3 Changed 10 months ago by klee

• Status changed from new to needs_review

### comment:4 follow-up: ↓ 8 Changed 10 months ago by tscrim

• Reviewers set to Travis Scrimshaw

One trivial little change:

```      def _gens_two(self):
-         """
+         r"""
```

Once done, you can set a positive review on my behalf.

I do find this line

```if len(self._gens_two.cache) == 2:
```

to be a little strange though.

### comment:5 Changed 10 months ago by git

• Commit changed from a16530020d7b48e53616880f4987139d1fac749c to 5d190dd754444367f9728bc24d0f1616502aa3a2

Branch pushed to git repo; I updated commit sha1. New commits:

 ​5d190dd `Use raw docstring to prevent invalid escape warning`

### comment:6 Changed 10 months ago by klee

• Description modified (diff)

### comment:7 Changed 10 months ago by git

• Commit changed from 5d190dd754444367f9728bc24d0f1616502aa3a2 to 0a77fa52ca71ec76aca7ad9a7867b66828e6c761

Branch pushed to git repo; I updated commit sha1. New commits:

 ​0a77fa5 `Drop use of _gens_two.cache`

### comment:8 in reply to: ↑ 4 Changed 10 months ago by klee

Sorry for the mess. I somehow lost a commit that I thought I uploaded.

One trivial little change:

```      def _gens_two(self):
-         """
+         r"""
```

Once done, you can set a positive review on my behalf.

Done now.

I do find this line

```if len(self._gens_two.cache) == 2:
```

to be a little strange though.

I had deleted this in the lost commit. Now done again.

I will wait for a green bot. Thank you for quick review.

### comment:9 Changed 10 months ago by tscrim

Thanks. Sounds good. Green bot => positive review.

### comment:10 Changed 10 months ago by klee

• Status changed from needs_review to positive_review

### comment:11 Changed 10 months ago by vbraun

• Branch changed from u/klee/32615 to 0a77fa52ca71ec76aca7ad9a7867b66828e6c761
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.