Opened 12 years ago

Closed 11 years ago

#5496 closed defect (fixed)

fix bugs in is_prime

Reported by: was Owned by: was
Priority: major Milestone: sage-4.3.1
Component: number theory Keywords:
Cc: Merged in: sage-4.3.1.rc1
Authors: Kevin Stueve Reviewers: Sebastian Pancratz
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

This is not good:

sage: is_prime(GF(5)(3))
True
sage: is_prime(GF(5)(4))
False

The fix is to totally 100% rewrite is_prime in arith.py so that it first calls x.is_prime() and if that isn't defined, then in some special cases (e.g., python ints) converts to Integer and calls is_prime. Otherwise, it raises a NotImplementedError?.

Attachments (6)

5496.patch (2.8 KB) - added by kevin.stueve 11 years ago.
changed delegation of is_prime calculation to n.is_prime()
5496.2.patch (2.6 KB) - added by kevin.stueve 11 years ago.
trac5496_rationals_to_int.patch (1.3 KB) - added by spancratz 11 years ago.
Three small changes throughout the Sage library
trac5496_symbolic_expressions.patch (1.6 KB) - added by spancratz 11 years ago.
Second addendum, for symbolic expressions
trac5496_lucas.patch (796 bytes) - added by spancratz 11 years ago.
Third addendum, for one character change for lucas numbers
trac5496_symbolic_expressions2.patch (1.2 KB) - added by spancratz 11 years ago.
Fourth addendum, for symbolic expressions

Download all attachments as: .zip

Change History (16)

comment:1 Changed 11 years ago by kevin.stueve

  • Report Upstream set to N/A

Right now finite fields don't seem to have an is_prime function, so I believe that currently, is_prime(GF(5)(3)) should raise NotImplementedError?. I'm going to try to fix is_prime so that it raises NotImplementedError? for is_prime(GF(5)(3)).

Kevin Stueve

comment:2 Changed 11 years ago by kevin.stueve

  • Status changed from new to needs_review

Changed 11 years ago by kevin.stueve

changed delegation of is_prime calculation to n.is_prime()

comment:3 Changed 11 years ago by kevin.stueve

  • Summary changed from fix bugs in is_prime (EASY) to fix bugs in is_prime

Changed 11 years ago by kevin.stueve

comment:4 Changed 11 years ago by kevin.stueve

Apply only 5496.2.patch.

Changed 11 years ago by spancratz

Three small changes throughout the Sage library

Changed 11 years ago by spancratz

Second addendum, for symbolic expressions

comment:5 Changed 11 years ago by spancratz

  • Authors set to kstueve
  • Reviewers set to spancratz
  • Status changed from needs_review to positive_review

Applying Kevin's second patch 5496.2.patch and the two small changes I added, this now passes all doctests done with sage -t devel/sage/sage, and can get a positive review.

comment:6 Changed 11 years ago by was

  • Status changed from positive_review to needs_work
if type(n) == int or type(n)==long: 

should be

if isinstance(n, (int, long)):

comment:7 Changed 11 years ago by was

Also, use obj.pyobject() in some cases for symbolics...

Changed 11 years ago by spancratz

Third addendum, for one character change for lucas numbers

comment:8 Changed 11 years ago by spancratz

  • Status changed from needs_work to needs_review

I've now incorporated the handling of symbolic expressions as suggested by Burcin. The sequence of patches should be applied in the order

  • 5496.2.patch
  • trac5496_rationals_to_int.patch
  • trac5496_symbolic_expressions.patch
  • trac5496_lucas.patch
  • trac5496_symbolic_expressions2.patch

I am running doctests now, but if they pass this should get positive review again.

Changed 11 years ago by spancratz

Fourth addendum, for symbolic expressions

comment:9 Changed 11 years ago by spancratz

  • Status changed from needs_review to positive_review

This is to confirm that all doctests have been passed, checked with "./sage -t devel/sage/sage".

comment:10 Changed 11 years ago by rlm

  • Authors changed from kstueve to Kevin Stueve
  • Merged in set to sage-4.3.1.rc1
  • Resolution set to fixed
  • Reviewers changed from spancratz to Sebastian Pancratz
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.