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: 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) 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)

trac_9401.patch (2.1 KB) - added by zimmerma 7 years ago.

Download all attachments as: .zip

Change History (15)

comment:1 Changed 9 years ago by mjo

  • Cc mjo added
sage: pari(3).isprime()
True
sage: pari(3).isprime(1)
False
sage: pari(3).isprime(2)
True

...what?

comment:2 Changed 9 years ago by zimmerma

  • Priority changed from minor to 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 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 7 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 7 years ago by zimmerma

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

Changed 7 years ago by zimmerma

comment:6 Changed 7 years ago by zimmerma

  • 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 pbruin

  • 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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:9 Changed 7 years ago by rws

  • 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 rws

  • Authors set to Paul Zimmermann, Peter Bruin, Ralf Stephan
  • Commit set to 0974f9d33ca0c938823fd02f5de90ee94648cebf
  • Status changed from needs_work to needs_review

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


New commits:

9d8a0ebskeleton interface
70a29e1core functionality
6df1fc6guess(), random_element(), some refactoring
9095be0ref doc completed; coefficients(), slicing added
f73e11ehandle ogf > 1
e7958b0Merge branch 'ticket/15714' into develop
597b22eTrac #9401: pari(n).isprime(1) does not give the primality certificate to the user
0974f9dTrac #9401: use pari_catch_sig* and new_gen (pbruin's code in comment:7)

comment:11 Changed 7 years ago by rws

  • 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?

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

comment:12 Changed 7 years ago by pbruin

  • Branch set to u/pbruin/9401-pari_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 rws

  • Authors changed from Paul Zimmermann, Peter Bruin, Ralf Stephan to Paul Zimmermann, Peter Bruin
  • 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 vbraun

  • Branch changed from u/pbruin/9401-pari_isprime to ed15dffe245f7f8306895500fe619c1be5bd22c3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.