Opened 11 years ago
Closed 11 years ago
#4777 closed defect (fixed)
[with patch; with positive review] Sage is_prime_power is seriously buggy, because pari's ispower is BROKEN
Reported by: | was | Owned by: | somebody |
---|---|---|---|
Priority: | critical | Milestone: | sage-3.2.2 |
Component: | basic arithmetic | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
18:18 < wstein> sage: n = 3089265681159475043336839581081873360674602365963130114355701114591322241990483812812582393906477998611814245513881 18:18 < wstein> sage: factor(n) 18:18 < wstein> 150607571^14 18:18 < wstein> sage: sage.rings.arith.is_prime_power(n)False 18:18 < wstein> sage: n.is_prime_power() 18:18 < wstein> False 18:18 < wstein> sage: is_prime(150607571) 18:18 < wstein> True 18:19 < wstein> Yep, Sage's is_prime_power function is just plain wrong. 18:19 < wstein> Great. 18:19 < wstein> I wrote that, I think... :-( 18:20 < wstein> sage: k = pari(n); k.ispower() 18:20 < wstein> (2, 1757630701017558763141032341047742794506161527817537960891) 18:20 < wstein> Oh, it's a bug in pari, actually. 18:20 < wstein> Since pari's ispower is guaranteed to give the maximal k such that x=n^k according 18:20 < wstein> to the docs. 18:20 < wstein> But it doesn't.
Pari's docs say this:
ispower(x,{k},{&n}): true (1) if x is a k-th power, false (0) if not. If n is given and a k-th root was computed in the process, put that in n. If k is omitted, return the maximal k >= 2 such that x = n^k is a perfect power, or 0 if no such k exist.
So this is a bug in pari. The short-term solution is to I think just factor that damned number at the end. This obviously could be slow in general, but at least it will be right. Plus add a note to the docs and post a bugreport upstream (but check latest svn pari first, since we use an ancient pari). I've reported bugs in this ispower function in pari before, by the way, so it's a known offender.
Attachments (1)
Change History (6)
comment:1 Changed 11 years ago by
- Summary changed from Sage is_prime_power is seriously buggy, because pari's ispower is BROKEN to [with patch; needs review] Sage is_prime_power is seriously buggy, because pari's ispower is BROKEN
Changed 11 years ago by
comment:2 Changed 11 years ago by
In the line See trac #4777
, you should put a backslash before the #.
comment:3 Changed 11 years ago by
- Summary changed from [with patch; needs review] Sage is_prime_power is seriously buggy, because pari's ispower is BROKEN to [with patch; with positive review (pending one character change)] Sage is_prime_power is seriously buggy, because pari's ispower is BROKEN
Patch looks good, except for the missing backslash noted by John Palmieri above. Beyond that, we just need to make sure that someone makes a note to test this in pari 2.4.2, and send a bug report upstream if it's really broken ...
comment:4 Changed 11 years ago by
- Summary changed from [with patch; with positive review (pending one character change)] Sage is_prime_power is seriously buggy, because pari's ispower is BROKEN to [with patch; with positive review] Sage is_prime_power is seriously buggy, because pari's ispower is BROKEN
I am taking care of the problem pointed out by John.
Cheers,
Michael
comment:5 Changed 11 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged in Sage 3.2.2.alpha2
BEFORE patch:
AFTER patch:
And I'm making this a blocker, since it is a situation where one can silently get very wrong answers.