Opened 13 years ago
Closed 9 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: | sage-6.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, GitHub, GitLab) | Commit: | ed15dffe245f7f8306895500fe619c1be5bd22c3 |
Dependencies: | Stopgaps: |
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
Attachments (1)
Change History (15)
comment:1 Changed 11 years ago by
Cc: | mjo added |
---|
comment:2 Changed 11 years ago by
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
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:4 Changed 9 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 ill-formed in the terminal version.
Paul
Changed 9 years ago by
Attachment: | trac_9401.patch added |
---|
comment:6 Changed 9 years ago by
Cc: | wstein robertwb added |
---|---|
Status: | 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)
Comments are welcome.
Paul
comment:7 Changed 9 years ago by
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
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:9 Changed 9 years ago by
Branch: | → u/rws/ticket/9401 |
---|---|
Modified: | Jan 30, 2014, 9:20:52 PM → Jan 30, 2014, 9:20:52 PM |
comment:10 Changed 9 years ago by
Authors: | → Paul Zimmermann, Peter Bruin, Ralf Stephan |
---|---|
Commit: | → 0974f9d33ca0c938823fd02f5de90ee94648cebf |
Status: | 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
Branch: | u/rws/ticket/9401 |
---|---|
Commit: | 0974f9d33ca0c938823fd02f5de90ee94648cebf |
Only the last two commits apply. If I create a new branch without the first stray commits, will trac handle this?
comment:12 Changed 9 years ago by
Branch: | → u/pbruin/9401-pari_isprime |
---|---|
Commit: | → ed15dffe245f7f8306895500fe619c1be5bd22c3 |
Reviewers: | → 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
Authors: | Paul Zimmermann, Peter Bruin, Ralf Stephan → Paul Zimmermann, Peter Bruin |
---|---|
Reviewers: | Peter Bruin → Peter Bruin, Ralf Stephan |
Status: | needs_review → positive_review |
comment:14 Changed 9 years ago by
Branch: | u/pbruin/9401-pari_isprime → ed15dffe245f7f8306895500fe619c1be5bd22c3 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
...what?