Opened 10 years ago

Closed 10 years ago

#11430 closed defect (fixed)

is_pseudoprime_small_power has bugs with get_data=True

Reported by: itolkov Owned by: itolkov
Priority: major Milestone: sage-4.7.1
Component: basic arithmetic Keywords:
Cc: Merged in: sage-4.7.1.alpha4
Authors: Igor Tolkov Reviewers: Mariah Lenox
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by mariah)

sage: is_pseudoprime_small_power(31^2, get_data=True)
[(31, 2)]
sage: is_pseudoprime_small_power(31, get_data=True)
True

Also, code can be written much better.

Apply: trac_11430_pseudoprime.patch

Attachments (2)

11430-arith.patch (949 bytes) - added by itolkov 10 years ago.
trac_11430_pseudoprime.patch (1.2 KB) - added by itolkov 10 years ago.
Updated with commit message, do not use 11430-arith.patch

Download all attachments as: .zip

Change History (8)

Changed 10 years ago by itolkov

comment:1 Changed 10 years ago by itolkov

  • Status changed from new to needs_review

Timing (ispsp is a more compact version, ispsp2 is this version, is_pseudoprime_small_power is the current version):

sage: timeit('ispsp(3^1024, bound=1024)')
sage: timeit('ispsp2(3^1024, bound=1024)')
sage: timeit('is_pseudoprime_small_power(3^1024, bound=1024)')
125 loops, best of 3: 3.29 ms per loop
125 loops, best of 3: 3.29 ms per loop
125 loops, best of 3: 3.29 ms per loop

sage: timeit('ispsp(31, bound=1024)')
sage: timeit('ispsp2(31, bound=1024)')
sage: timeit('is_pseudoprime_small_power(31, bound=1024)')
625 loops, best of 3: 3.45 µs per loop
625 loops, best of 3: 1.8 µs per loop
625 loops, best of 3: 1.47 µs per loop

sage: timeit('ispsp(31^2, bound=1024)')
sage: timeit('ispsp2(31^2, bound=1024)')
sage: timeit('is_pseudoprime_small_power(31^2, bound=1024)')
625 loops, best of 3: 6.41 µs per loop
625 loops, best of 3: 5.92 µs per loop
625 loops, best of 3: 15.1 µs per loop

sage: timeit('ispsp(31^5, bound=1024)')
sage: timeit('ispsp2(31^5, bound=1024)')
sage: timeit('is_pseudoprime_small_power(31^5, bound=1024)')
625 loops, best of 3: 9.45 µs per loop
625 loops, best of 3: 8.92 µs per loop
625 loops, best of 3: 22 µs per loop

comment:2 Changed 10 years ago by itolkov

  • Priority changed from minor to major

comment:3 Changed 10 years ago by mariah

  • Status changed from needs_review to needs_work

Changed 10 years ago by itolkov

Updated with commit message, do not use 11430-arith.patch

comment:4 Changed 10 years ago by itolkov

  • Status changed from needs_work to needs_review

Got it. Done.

comment:5 Changed 10 years ago by mariah

  • Authors set to Igor Tolkov
  • Description modified (diff)
  • Reviewers set to Mariah Lenox
  • Status changed from needs_review to positive_review

I applied the patch to sage-4.7.1.alpha2, did 'sage -b', and verified that the patch fixed the reported problem. I then did 'make testlong'. All tests passed. Positive review!

comment:6 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.1.alpha4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.