Opened 10 years ago
Closed 7 years ago
#9401 closed defect (fixed)
pari(n).isprime(1) does not give the primality certificate to the user
Reported by:  zimmerma  Owned by:  AlexGhitza 

Priority:  major  Milestone:  sage6.2 
Component:  basic arithmetic  Keywords:  prime number 
Cc:  cremona, mjo, wstein, robertwb  Merged in:  
Authors:  Paul Zimmermann, Peter Bruin  Reviewers:  Peter Bruin, Ralf Stephan 
Report Upstream:  N/A  Work issues:  
Branch:  ed15dff (Commits)  Commit:  ed15dffe245f7f8306895500fe619c1be5bd22c3 
Dependencies:  Stopgaps: 
Description
The Pari isprime
function is able to return a primality
certificate:
gp: isprime(2^311,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^311).isprime(1) True
Attachments (1)
Change History (15)
comment:1 Changed 9 years ago by
 Cc mjo added
comment:2 Changed 9 years ago by
 Priority changed from minor to major
apparently something changed (in worse) since I reported this, since indeed we now get:
sage: pari(2^311).isprime(1) False
I change the priority to "major".
Paul
comment:3 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:4 Changed 7 years ago by
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 illformed in the terminal version.
Paul
comment:5 Changed 7 years ago by
for the illformed documentation of get_flag
, see #15096.
Changed 7 years ago by
comment:6 Changed 7 years ago by
 Cc wstein robertwb added
 Status changed from new to 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)
Comments are welcome.
Paul
comment:7 Changed 7 years ago by
 Status changed from needs_review to 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 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:9 Changed 7 years ago by
 Branch set to u/rws/ticket/9401
 Modified changed from 01/30/14 21:20:52 to 01/30/14 21:20:52
comment:10 Changed 7 years ago by
 Commit set to 0974f9d33ca0c938823fd02f5de90ee94648cebf
 Status changed from needs_work to 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 7 years ago by
 Branch u/rws/ticket/9401 deleted
 Commit 0974f9d33ca0c938823fd02f5de90ee94648cebf deleted
Only the last two commits apply. If I create a new branch without the first stray commits, will trac handle this?
comment:12 Changed 7 years ago by
 Branch set to u/pbruin/9401pari_isprime
 Commit set to ed15dffe245f7f8306895500fe619c1be5bd22c3
 Reviewers set to 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 7 years ago by
 Reviewers changed from Peter Bruin to Peter Bruin, Ralf Stephan
 Status changed from needs_review to positive_review
comment:14 Changed 7 years ago by
 Branch changed from u/pbruin/9401pari_isprime to ed15dffe245f7f8306895500fe619c1be5bd22c3
 Resolution set to fixed
 Status changed from positive_review to closed
...what?