Opened 10 years ago

Closed 10 years ago

# multivariate factorization over finite fields

Reported by: Owned by: zimmerma tbd major sage-4.7.2 factorization malb, SimonKing sage-4.7.2.alpha3 Martin Albrecht Paul Zimmermann N/A

As far as I know, Sage calls Singular for multivariate factorization over finite fields. Currently Singular is limited to primes less than 229:

```sage: R.<x,y> = GF(previous_prime(2^29))[]
sage: factor(x+y+1,proof=False)
x + y + 1
sage: R.<x,y> = GF(next_prime(2^29))[]
sage: factor(x+y+1,proof=False)
...
NotImplementedError: Factorization of multivariate polynomials over prime fields with characteristic > 2^29 is not implemented.
```

However for larger primes we get:

```sage: R.<x,y> = GF(previous_prime(2^31))[]
sage: factor(x+y+1,proof=False)
```

and this seems to hang (when I hit Ctrl-C, it says `Interrupting Singular`)

Apply trac11829_factor_too_large.patch to the Sage library.

### comment:2 Changed 10 years ago by malb

Looks like we raise a NotImplementedError also in the polydict implementation:

```sage -singular                                                                [ 3:32PM]
SINGULAR                             /  Development
A Computer Algebra System for Polynomial Computations   /   version 3-1-1
0<
by: G.-M. Greuel, G. Pfister, H. Schoenemann        \   Feb 2010
FB Mathematik der Universitaet, D-67653 Kaiserslautern    \
> ring r = 2147483647,(x,y),dp;
> poly p = x+y+1;
> factorize(p);
? characteristic 2147483647 is too large(max is 2^29)
Segmentation fault
```

### comment:3 Changed 10 years ago by malb

• Authors set to Martin Albrecht
• Status changed from new to needs_review

The attached patch throws an error if a factorisation with a modulus > 229 is requested.

### comment:4 Changed 10 years ago by zimmerma

Martin, just curious: why did next_prime(229) raise an error and not previous_prime(231)?

Paul, now checking the doctests still pass...

### comment:5 Changed 10 years ago by malb

• Status changed from needs_review to needs_info

Hi Paul,

a multivariate polynomial ring over GF(next_prime(229)) uses libSingular, i.e., Singular via a Cython interface; while a multivariate polynomial ring over GF(previous_prime(231)) uses the generic polynomial implementation in Sage. We followed the Singular manual for the maximum prime allowed (which is 2147483629 < previous_prime(231)), while we apparently don't follow it when converting generic polynomials to Singular via the pexpect interface.

I think this is actually a bug and the Singular developers meant previous_prime(231) when they chose a limit.

### comment:6 Changed 10 years ago by zimmerma

Martin, I asked Hans Schonemann last week at the MAGIX conference about this limit, and he told about a 228 limit. Thus I'm not sure the Singular developers really know what the real limit is...

Paul

### comment:7 Changed 10 years ago by malb

Paul, there's a limit of 229 for factoring, gcds etc. everything that has to do with factory. There is another limit of ~ 231 for Singular itself: polynomial arithmetic, GBs etc.

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

All doctests pass, thus if the limits are ok, I will give a positive review.

Paul

### comment:9 Changed 10 years ago by malb

• Status changed from needs_info to needs_review

Okay, previous_prime(231) is what is correct (confirmed with Hans). Hence, I changed the bound in `ring.pyx`. This means, that the added check in `multi_polynomial_element.py` won't be used (by default), but it doesn't harm to have it there regardless.

### comment:10 follow-up: ↓ 15 Changed 10 years ago by zimmerma

• Reviewers set to Paul Zimmermann
• Status changed from needs_review to positive_review

All doctests pass except the following timeout with sage 4.7.1 (but this timeout also happens before the patch):

```The following tests failed:

sage -t  devel/sage-11829/sage/sandpiles/sandpile.py # Time out
```

Thus a positive review for me.

Paul

### comment:11 Changed 10 years ago by malb

• Status changed from positive_review to needs_work

argh, I screwed up and didn't upload the most recent patch. Sorry! I'll upload the new patch in a second.

### comment:12 Changed 10 years ago by malb

• Status changed from needs_work to needs_review

### comment:13 Changed 10 years ago by zimmerma

• Status changed from needs_review to positive_review

All doctests still pass with the new version (with the same timeout).

Paul

### comment:14 Changed 10 years ago by leif

• Description modified (diff)

### comment:15 in reply to: ↑ 10 Changed 10 years ago by leif

All doctests pass except the following timeout with sage 4.7.1 (but this timeout also happens before the patch):

```The following tests failed:

sage -t  devel/sage-11829/sage/sandpiles/sandpile.py # Time out
```

Guess you're on Ubuntu (10.04.3 for example); this is due to a known issue with its kernel and the PExpect interface. (You'll notice that the doctest idles most of the time.)

### comment:16 Changed 10 years ago by zimmerma

yes I'm on Ubuntu.

Paul

### comment:17 Changed 10 years ago by leif

• Merged in set to sage-4.7.2.alpha3
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.