Opened 13 years ago

Closed 9 years ago

# pari(n).isprime(1) does not give the primality certificate to the user

Reported by: Owned by: zimmerma AlexGhitza major sage-6.2 basic arithmetic prime number cremona, mjo, wstein, robertwb Paul Zimmermann, Peter Bruin Peter Bruin, Ralf Stephan N/A ed15dff ed15dffe245f7f8306895500fe619c1be5bd22c3

### Description

The Pari `isprime` function is able to return a primality certificate:

```gp: isprime(2^31-1,1)

[2 3 1]

[3 5 1]

[7 3 1]

[11 3 1]

[31 2 1]

[151 3 1]

[331 3 1]
```

However when calling this function from Sage, the certificate is lost:

```sage: pari(2^31-1).isprime(1)
True
```

### comment:1 Changed 11 years ago by mjo

```sage: pari(3).isprime()
True
sage: pari(3).isprime(1)
False
sage: pari(3).isprime(2)
True
```

...what?

### comment:2 Changed 11 years ago by zimmerma

Priority: minor → major

apparently something changed (in worse) since I reported this, since indeed we now get:

```sage: pari(2^31-1).isprime(1)
False
```

I change the priority to "major".

Paul

### comment:3 Changed 9 years ago by jdemeyer

Milestone: sage-5.11 → sage-5.12

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

by the way I notice there is no indication on how to access or change the "arithmetic proof flag" mentioned in the documentation of `n.is_prime`.

And the documentation of `get_flag` is ill-formed in the terminal version.

Paul

### comment:5 Changed 9 years ago by zimmerma

for the ill-formed documentation of `get_flag`, see #15096.

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

Cc: wstein robertwb added new → needs_review

the attached patch does several things:

1) it fixes two typos in `gen.pyx`

2) it corrects the behaviour of `pari(n).isprime(1)` which incorrectly was returning `False` for prime n

3) for prime n, now `pari(n).isprime(1)` returns a tuple `(True, cert)` where `cert` is the primality certificate (currently as Pari object, I didn't figure out how to convert it to a Python object)

Paul

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

Status: needs_review → needs_work

In principle OK, but needs to be rebased on #15124.

Also, it would be much cleaner to call `new_gen()` instead of initialising the `gen` and resetting the stack by hand:

```cdef GEN x
pari_catch_sig_on()
x = gisprime(self.g, flag)
if typ(x) != t_INT:
# case flag=1 with prime input: x is the certificate
return True, P.new_gen(x)
else:
pari_catch_sig_off()
return bool(signe(x))
```

### comment:8 Changed 9 years ago by vbraun_spam

Milestone: sage-6.1 → sage-6.2

### comment:9 Changed 9 years ago by rws

Branch: → u/rws/ticket/9401 Jan 30, 2014, 9:20:52 PM → Jan 30, 2014, 9:20:52 PM

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

Authors: → Paul Zimmermann, Peter Bruin, Ralf Stephan → 0974f9d33ca0c938823fd02f5de90ee94648cebf needs_work → needs_review

Rebased on 6.2.base2, applied comment:7 by pbruin

New commits:

 ​9d8a0eb `skeleton interface` ​70a29e1 `core functionality` ​6df1fc6 `guess(), random_element(), some refactoring` ​9095be0 `ref doc completed; coefficients(), slicing added` ​f73e11e `handle ogf > 1` ​e7958b0 `Merge branch 'ticket/15714' into develop` ​597b22e `Trac #9401: pari(n).isprime(1) does not give the primality certificate to the user` ​0974f9d `Trac #9401: use pari_catch_sig* and new_gen (pbruin's code in comment:7)`

### comment:11 Changed 9 years ago by rws

Branch: u/rws/ticket/9401 0974f9d33ca0c938823fd02f5de90ee94648cebf

Only the last two commits apply. If I create a new branch without the first stray commits, will trac handle this?

Last edited 9 years ago by rws (previous) (diff)

### comment:12 Changed 9 years ago by pbruin

Branch: → u/pbruin/9401-pari_isprime → ed15dffe245f7f8306895500fe619c1be5bd22c3 → Peter Bruin

Yes, this is no problem. I did this (using `git rebase -i`) in the branch I just pushed, and made one trivial additional change (in Cython, `s != 0` turns out to be faster than `bool(s)`). You can set this to `positive_review` if you are happy with this branch.

### comment:13 Changed 9 years ago by rws

Authors: Paul Zimmermann, Peter Bruin, Ralf Stephan → Paul Zimmermann, Peter Bruin Peter Bruin → Peter Bruin, Ralf Stephan needs_review → positive_review

### comment:14 Changed 9 years ago by vbraun

Branch: u/pbruin/9401-pari_isprime → ed15dffe245f7f8306895500fe619c1be5bd22c3 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.