random_prime does not handle erroneous input gracefully - it hangs

[sagetrac-drkirkby]

As noted at #10111 and

http://groups.google.com/group/sage-devel/browse_thread/thread/6e8d6f28c915830d?hl=en

random_prime() is not well documented.

But random_prime() is also broken for some erroneous input. Programs should always handle poor input properly, which is the case of Sage probably means generating an error message.

sage: random_prime(0,True,-1) # Hangs
sage: random_prime(0,False,-1) # Hangs
sage: random_prime(1,0,-23) # Hangs
sage: random_prime(-12,0,-12) # Hangs
sage: random_prime(0, proof=False, lbound=-12) # Hangs

Having a negative lower bound can cause the function to hang, but this is not always the case, as the example below shows. Here an error message is generated.

sage: random_prime(-12,0,-4)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

/export/home/drkirkby/sage-4.6.alpha3/<ipython console> in <module>()

/export/home/drkirkby/sage-4.6.alpha3/local/lib/python2.6/site-packages/sage/rings/arith.pyc in random_prime(n, proof, lbound)
   1144     n = ZZ(n)
   1145     if n < lbound:
-> 1146         raise ValueError, "n must be greater than lbound: %s"%(lbound)
   1147     elif n == 2:
   1148         return ZZ(n)

ValueError: n must be greater than lbound: -4

Dave

Apply

1. attachment: trac_10112.patch (merged in sage-4.8.alpha1)
2. attachment: trac_10112-replacement-extra.patch (merged in sage-4.8.alpha1)
3. attachment: trac_10112-ascii.patch (merged in sage-4.8.alpha2)
   to the Sage library.

Component: number theory

Author: Mike Hansen, Francis Clarke

Reviewer: David Kirkby, Johan Bosman

Merged: sage-4.8.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/10112

[mwhansen]

Author: Mike Hansen

[sagetrac-drkirkby]

comment:2

Mike,
thank you for fixing this. I'll try this later today, but here's a few comments from reading the patch only - I've not tested it in Sage yet.

Should the example on line 1127 be

random_prime(200, proof=False, lbound=100) ?

Currently it's the same as the previous example.

One thing that would be nice is if you did like John did at #10105 and have doctests for the commands that currently hang Sage. Then if there are any regressions, and the bug(s) get back in, this will be detected.

Perhaps I'll get bored of running my little script that supplies junk to commands to see what ones crash sage (like #10113) or hang Sage like this ticket, #10108 and #10105.

[mwhansen]

comment:3

Attachment: trac_10112.patch.gz

I've updated the patch.

[sagetrac-drkirkby]

comment:4

Thank you, I will take a look later today and test it.

[sagetrac-fwclarke]

comment:5

The patch deals with the cases listed. But there are other cases which hang, like

sage: random_prime(8, lbound=8)

and some that almost do, like

sage: random_prime(3, lbound=-10^8)

They can be very easily dealt with. The additional patch does this.

[sagetrac-fwclarke]

Attachment: trac_10112-extra.patch.gz

to apply after trac_10112.patch

[sagetrac-drkirkby]

comment:6

Those two patches are a definite improvement, so I'm giving it a positive review.

I've opened #10277 for another issue with random_prime

Sage's implementation is also incredibly slow compared to Mathematica. After 20 minutes of CPU time on a 3.33 GHz machine I was unable to generate one up to 10¹⁰⁰⁰ with Sage. Yet Mathematica can do that in 7 seconds!

Dave

[sagetrac-drkirkby]

Reviewer: David Kirkby

[sagetrac-drkirkby]

Changed author from Mike Hansen to Mike Hansen, Francis Clarke

[sagetrac-drkirkby]

comment:8

I'm setting this to 'needs info', as William remarked on sage-devel that he did not see this issue with 4,6 that I get at. It seems highly unlikely, but these patches could just be whats casing that problem for me.

[sagetrac-fwclarke]

comment:9

The issue raised in #10277 (which surely arises from using random_prime as patched here) shows the weakness of using prime_pi. There is a much better way of checking that there are some primes in the range in question. A replacement alternative patch will be posted very soon.

[sagetrac-fwclarke]

comment:10

A replacement patch is attached.  It uses Betrand's postulate and refinements due to Nakura and Schoenfield.  Only when the ratio of the upper and lower bounds is quite close to one is the smallest prime in the interval computed.

[burcin]

comment:11

Can we create a fast but unsafe function random_prime_unsafe() and make the random_prime() function exposed to the users call that?

ATM, the random_prime() function is used in speed critical code. See sage/ext/multi_modular.pyx for example. In this use case, the checks are unnecessary and they would cause a dramatic slow down. We should be able to bypass the checks when we know the input makes sense. I suggest separating the core of the function from the code that makes it idiot-proof, and using the core directly in places like sage/ext/multi_modular.pyx.

When this change is made, there should be a clear and loud warning in the release notes to notify people who rely on the current behavior of random_prime() to switch to this unsafe version in their personal codebase as well.

[sagetrac-fwclarke]

Attachment: trac_10112-replacement-extra.patch.gz

Apply after trac_10112.patch INSTEAD of trac_10112-extra.patch

[sagetrac-fwclarke]

comment:12

Replying to @burcin:

Can we create a fast but unsafe function random_prime_unsafe() and make the random_prime() function exposed to the users call that? ATM, the random_prime() function is used in speed critical code. See sage/ext/multi_modular.pyx for example. In this use case, the checks are unnecessary and they would cause a dramatic slow down. [... ...]

A good idea. But the slowdown is, for most cases, far less significant with the new patch.

[sagetrac-fwclarke]

comment:13

Probably the way forward would be to have a "check" option. But to quantify my earlier remark, I note that for the default bounds used in sage/ext/multi_modular.pyx (10^15 and 10^10), the code checking that there are primes in that interval adds, on my machine, about 50 microseconds to the 1325 microseconds taken to find a random prime.

[sagetrac-drkirkby]

comment:14

Is there any reason this should not be changed to positive review if the slowdown is very small?

Unless there's universal agreement on this, I suggest the changes in documentation, are put on #10111. That ticket was supposed to address the deficiencies in the documentation. The only comment on that ticket is from Mike, and is See the patch at #10112. But if Mikes patch here, which changes both the documentation and the code is going to stall, we might as well just fix the documentation for now on #10111. The changes needed to the documentation appear to be

• The example random_prime(200, lbound=100) is added
• The example random_prime(200, proof=False, lbound=100) is added.
• The error message in the code (which I guess is code not documentation), which changes n must be greater than lbound to n must be at least lbound. Clearly looking at the code, fwclarke's change is correct, since the test before the error message is if n < lbound. Therefore n=lbound is permitted by the code, so the correct error message should be n must be at least lbound

If there is no agreement to merge the two patches here, I'll create one patch which just fixes the above 3 documentation problems and add that to #10111. Does that make sense?

Dave

[sagetrac-johanbosman]

comment:15

Replying to @sagetrac-drkirkby:

Is there any reason this should not be changed to positive review if the slowdown is very small?

I don't think so. The code looks okay, is well documented, and passes all tests.

[sagetrac-johanbosman]

Changed reviewer from David Kirkby to David Kirkby, Johan Bosman

[jdemeyer]

Merged: sage-4.8.alpha1

[jdemeyer]

comment:18

The patch contains non-ASCII characters which Sphinx 1.1.2 (#10620) rejects.

[jhpalmieri]

comment:19

We could put # -*- coding: utf-8 -*- at the top of the file arith.py -- I think the sagenb project has done this with all of their files -- but I prefer the attached patch.

[jhpalmieri]

apply on top of other patches

[jhpalmieri]

comment:20

Attachment: trac_10112-ascii.patch.gz