Opened 10 years ago

Closed 7 years ago

# GF() arithmetic slower than IntegerModRing()

Reported by: Owned by: zimmerma AlexGhitza major sage-5.13 basic arithmetic malb, was sage-5.13.beta5 Peter Bruin Jeroen Demeyer N/A

### Description

Consider the following code:

```# tries to find x^2+(y/2^delta)^2 + small = (2z+1)^2
# (2^delta*x)^2 + y^2 + err = (2^delta*(2z+1))^2
def table1_mod2(p,delta,err):
l = [[0,0]]
P = 1 # values in l are mod P
q = 1
twop = 2^p
twodelta = 2^delta
while P<twop:
q = next_prime(q)
R = IntegerModRing(P*q)
newl = []
for t in l:
for hx in range(q):
x = t+hx*P
if x>=twop:
break
u = R((twodelta*x)^2+err)
for hz in range(q):
z = t+hz*P
if z>=twop:
break
y2 = R((twodelta*(2*z+1))^2)-u
if y2.is_square():
newl.append([x,z])
l = newl
P = P * q
return l, P
```

With Sage 4.7 I get:

```sage: time l=table1_mod2(10,0,1)
Time: CPU 2.61 s, Wall: 2.63 s
sage: len(l)
76940
```

If I change `R = IntegerModRing(P*q)` by `R=GF(q)`, which does not change the algorithm (we are lifting modulo 2*3*5*...), then strangely the program is slower:

```sage: time l=table1_mod2(10,0,1)
Time: CPU 19.28 s, Wall: 19.33 s
sage: len(l)
76940
```

Is that normal?

### comment:1 Changed 8 years ago by zimmerma

still true with Sage 5.5: got CPU 2.16s with `R = IntegerModRing(P*q)`, CPU 12.52s with `R=GF(q)`.

Paul

### comment:2 Changed 8 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:3 Changed 7 years ago by pbruin

It still happens in 5.12.beta2, with a similar factor. The difference seems to be in `is_square()`:

```sage: F=GF(1031)
sage: R=IntegerModRing(1031)
sage: a=F(27); b=R(27)
sage: a.is_square()
True
sage: b.is_square()
True
sage: %timeit a.is_square()
10000 loops, best of 3: 79 us per loop
sage: %timeit b.is_square()
100000 loops, best of 3: 2.25 us per loop
```

This is surprising since a and b are of the same type (`IntegerMod_int`) and have the same value; only their parents differ. Now `is_square()` calls the method `factored_order()` of the parent; this is cached in `IntegerModRing` but not in `FiniteField_base`.

Indeed, the slowness of `a.is_square()` is essentially explained by the slowness of constructing a `Factorization` object:

```sage: %timeit Factorization([(1031,1)])
10000 loops, best of 3: 72.2 us per loop
```

I guess the solution is either to speed up construction of a `Factorization`, or to use caching in `FiniteField_base.factored_order()`.

### comment:4 Changed 7 years ago by pbruin

• Authors set to Peter Bruin

Here is a patch; now testing...

### Changed 7 years ago by pbruin

cache factored order in FiniteField_base

### comment:5 Changed 7 years ago by pbruin

• Status changed from new to needs_review

With the patch, the `GF(q)` version is now slightly faster on my system.

The line that this patch removes in `finite_field_prime_modn.py` was redundant because `FiniteField_prime_modn` inherits `factored_order()` from `FiniteField_base`, not from `IntegerModRing`.

### comment:6 Changed 7 years ago by jdemeyer

• Merged in set to sage-5.13.beta5
• Resolution set to fixed
• Reviewers set to Jeroen Demeyer
• Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.