Groups > comp.soft-sys.math.maple > #1206

Re: Checking primality of large numbers

From	William Unruh <unruh@invalid.ca>
Newsgroups	comp.soft-sys.math.maple
Subject	Re: Checking primality of large numbers
Date	2015-11-04 18:27 +0000
Organization	A noiseless patient Spider
Message-ID	<n1dind$sf9$1@dont-email.me> (permalink)
References	<d9uii3Fd8c9U1@mid.individual.net> <n1dfia$gqe$1@dont-email.me>

Show all headers | View raw

On 2015-11-04, William Unruh <unruh@invalid.ca> wrote:
> On 2015-11-04, Rainer Rosenthal <r.rosenthal@web.de> wrote:
>> For a problem in recreational math I am testing numbers of
>> magnitude around 10^1400 whether they are prime or not.
>> It takes about two and half an hour per number when I use
>> the standard isprime() Funktion.
>>
>> Are there ways inside Maple (I use V) to get the results faster?
>
> That is fast. Remember that if you were to try testing primality by
> division it would take many many many times longer than that age of the
> universe. There exist probabilistic primality tests-- depends on how
> much probablility you are willing to accept that the number is reported
> as prime but is really not. (the probabillies are verysmall) There is
> also a deterministic polynomial time test. But I think the polynomial is
> quite large.Wikipedia suggests about l^6.
>
> I do not know what Maple uses in the isprime() function. 

Always helps to read the documentation. Doing ? isprime, it tells me it
uses a probabilistic primality tester, but not which one. There is thus
a very small probability that it will say the number is prime when it is
not. The probability of your computer being hit by a meteor is probably larger
than that probability. Probablilistic tests are about as fast as they
get. Remember also that large number ( and you are using at least 1500
digit arithmetic) is also very slow.

Back to comp.soft-sys.math.maple | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Checking primality of large numbers Rainer Rosenthal <r.rosenthal@web.de> - 2015-11-04 15:20 +0100
  Re: Checking primality of large numbers William Unruh <unruh@invalid.ca> - 2015-11-04 17:34 +0000
    Re: Checking primality of large numbers William Unruh <unruh@invalid.ca> - 2015-11-04 18:27 +0000
  Re: Checking primality of large numbers Peter Luschny <peter.luschny@gmail.com> - 2015-11-04 11:28 -0800

csiph-web