#10277: random_prime() fails to work for values > 2^40 if a lower bound is set
-----------------------------+----------------------------------------------
Reporter: drkirkby | Owner: was
Type: defect | Status: new
Priority: major | Milestone: sage-4.6.1
Component: number theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
{{{random_prime()}}} appears to handle quite large numbers
{{{
sage: random_prime(10^100)
7980458528200352285375353724908005160633013691189804269781978682382158576820070695791880087837726879
}}}
in fact, it appears to as though it will work to at least 10^1000000000^,
though it fails for 10^10000000000^.
But if a lower bound is set, the upper limit of {{{random_prime}}} is
restricted to 2^40^, which is around 10^12^.
{{{
sage: random_prime(2^40+1,lbound=12)
---------------------------------------------------------------------------
NotImplementedError Traceback (most recent call
last)
/export/home/drkirkby/qq/sage-4.6.1.alpha1/<ipython console> in <module>()
/export/home/drkirkby/qq/sage-4.6.1.alpha1/local/lib/python2.6/site-
packages/sage/rings/arith.pyc in random_prime(n, proof, lbound)
1159 return n
1160 lbound = max(2, lbound)
-> 1161 if lbound > 2 and prime_pi(n) <= prime_pi(lbound-1):
1162 raise ValueError, "There are no primes between %s and %s
(inclusive)" % (lbound, n)
1163 else:
/export/home/drkirkby/qq/sage-4.6.1.alpha1/local/lib/python2.6/site-
packages/sage/functions/prime_pi.so in
sage.functions.prime_pi.PrimePi.__call__
(sage/functions/prime_pi.c:1125)()
NotImplementedError: computation of prime_pi() greater 2**40 not
implemented
}}}
If I compare this with Mathematica 7.01, I find Mathematica has no such
problems generating random primes up to large values, even if a lower
bound is set. Here's a random prime in the range 1000 to 10^1000^
{{{
In[1]:= RandomPrime[{1000,10^1000}]
Out[1]=
113385181521900468164191823243380715126145463788185407100720218734056\
>
479220211608218084498402183236351542265593400216896042171731891088681371\
>
031933937779910290752183096697533115893317148489651228723855774549826488\
>
609183869775506555260353444625540357377478392480383926781924074661958405\
>
927348714375837006129760795638915099524015590322046363160083139499201107\
>
644734466583958699690474658383854230153477004091701453047153516742596851\
>
834894247750217438643934960127478251140350389220934422153161054330077533\
>
489023104217807807159360316591672041363249441395509536046012375037619063\
>
643233350748848129475142877253717443233362740964522093581092785244209404\
>
408239930373701630354570762373539217835019703894617890496967417800477778\
>
280004392636751979356175924773816944978114099526161921816188057377506083\
>
674761134810672819835357486060679152139402595701113409894341135150001602\
>
855079098938140261704512228583255998916339884372871399317049545813648006\
> 9788852836452583334765209656025537275350871626318478286244659000299
}}}
BTW, Mathematica is '''much''' faster too. I gave up trying to get a
random prime in Sage up to 10^1000^
{{{
sage: time random_prime(10^1000)
}}}
after spending more than 16 minutes of CPU time, whereas Mathematica can
generate such a random prime in 7 seconds.
(Part of this might be due to the fact this is a 32-bit version of Sage vs
a 64-bit version of Mathematica, but I doubt that explains a factor of
more than 130)
Dave
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10277>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
