#19814: Number Theory::random_prime(n) generating composite numbers for large
values of n
-------------------------------------------------+-------------------------
Reporter: DayneSorvisto | Owner:
Type: defect | DayneSorvisto
Priority: major | Status: new
Component: number theory | Milestone: sage-7.0
Keywords: prime numbers | Resolution:
Authors: | Merged in:
Report Upstream: Reported upstream. No | Reviewers:
feedback yet. | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
-------------------------------------------------+-------------------------
Description changed by DayneSorvisto:
Old description:
> Hi,
>
> First time posting a bug report on trac. The bug I'd like to report is
> "random_prime" returns composite numbers for large integers. For example
>
> {{{
> random_prime(100000000000000000000000000000000000000000000000000000000000000000000000000)
> }}}
>
> returned
> 71944724797690175157403755256108218794891687825722145298657347991279721529
> which is a composite number ending in 9. I am using the SageMath cloud
> notebook but believe it's reproducible on other implementations of Sage.
New description:
Hi,
First time posting a bug report on trac. The bug I'd like to report is
"random_prime" returns composite numbers for large integers. For example
{{{
random_prime(100000000000000000000000000000000000000000000000000000000000000000000000000)
}}}
returned
71944724797690175157403755256108218794891687825722145298657347991279721529
which is a composite number ending in 9. I am using the SageMath cloud
notebook but believe it's reproducible on other implementations of Sage.
Looking at the source in rings.arith.py it seems that the problem is this
line which generates a probable prime for large numbers.
{{{
smallest_prime = ZZ(lbound-1).next_probable_prime()
}}}
Suggestions: Perhaps there could be some more error checking for large
numbers so Sage doesn't return obviously composite numbers? Or at the very
least checking small prime factors? If this function were being used in
Cryptography, the Handbook of Applied Cryptography recommends the Miller
Rabin test for random large primes.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/19814#comment:6>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
