## trial division

Expand Messages
• Trial division can be an easy and predictable way to verify primality if the number is not too large. I am hoping that someone who has a commercial factoring
Message 1 of 4 , May 1, 2007
Trial division can be an easy and predictable way to verify
primality if the number is not too large. I am hoping that
someone who has a commercial factoring program will check
the time it takes to verify that 1986619529684749961 is prime.
pentium3 866 Dell. This prime is only special in that it
appears on a proved +1 mod 10 sequence. If this were not known
it would take my program 640 seconds to resolve.

aldrich
• ... I don t have any commercial factoring program but here is the free PrimeForm/GW: C: Users Jens pfgw -f -e2000000000 -q1986619529684749961 PFGW Version
Message 2 of 4 , May 1, 2007
aldrich617 wrote:

> Trial division can be an easy and predictable way to verify
> primality if the number is not too large. I am hoping that
> someone who has a commercial factoring program will check
> the time it takes to verify that 1986619529684749961 is prime.
> pentium3 866 Dell. This prime is only special in that it
> appears on a proved +1 mod 10 sequence. If this were not known
> it would take my program 640 seconds to resolve.

I don't have any commercial factoring program but here is the free
PrimeForm/GW:

C:\Users\Jens>pfgw -f -e2000000000 -q1986619529684749961
PFGW Version 1.2.0 for Windows [FFT v23.8]

trial factoring to 1409474912
1986619529684749961 factors prime!: 1986619529684749961

That took 7 seconds on one core of a 2.4 GHz Core 2 Duo.

The free PARI/GP proves primality in a small fraction of a second without
using trial factoring:

? isprime(1986619529684749961)
time = 0 ms.
%209 = 1
? for(i=1,5000,isprime(1986619529684749961))
time = 860 ms.

That is 860 ms / 5000 = 0.00017 second for one proof on a 2.4 GHz core.

Both programs are for arbitrary number sizes.
Similar programs optimized for 64-bit numbers would probably be faster.

--
Jens Kruse Andersen
• ... Is your program dividing by all numbers up to sqrt[n] or just the prime ones? Admittedly, it s a lot more complicated and can be quite memory-intensive to
Message 3 of 4 , May 1, 2007
aldrich617 wrote:
> Trial division can be an easy and predictable way to verify
> primality if the number is not too large. I am hoping that
> someone who has a commercial factoring program will check
> the time it takes to verify that 1986619529684749961 is prime.
> pentium3 866 Dell. This prime is only special in that it
> appears on a proved +1 mod 10 sequence. If this were not known
> it would take my program 640 seconds to resolve.

Is your program dividing by all numbers up to sqrt[n] or just the
prime ones? Admittedly, it's a lot more complicated and can be quite
memory-intensive to build a naive sieve of the primes up to about 1.4
billion in this case, so I'm guessing you might just divide by all of
the smaller numbers (at least the odd ones) up to sqrt[n]? Or do you
have a cleverer sieve to generate all the primes?

As you may know, as a next step, you might consider doing a test like
the Rabin-Miller test on your numbers, which can very rapidly give you
at least a probabilistic result that a number is prime or not. If the
Rabin-Miller test says that a number is composite, it's definitely
composite. If it says that it's prime, it's very likely prime, and it's
easy to run enough rounds of the test that the probability of it
returning a false result are far, far less than the probability of your
hardware failing during the test and returning an incorrect result, or
even you testing billions of numbers each second continuously for the
life of the universe, and never getting a wrong answer. It will also be
immensely faster than trial division for numbers of this size (although
your tests may also consist of trial division for small primes, which,
as a practical matter, tends to reduce the size of large numbers
somewhat rapidly when factoring.) In addition, the Rabin-Miller test
tends to become more and more reliable as the numbers get larger,
greatly improving the probability that a number is indeed prime even if
tested against a smaller number of bases.

In addition, it is known for numbers up to the smaller number
341550071728321 which bases you need to test against in a Rabin-Miller
test to *prove* primality, although this limit is not large enough for
the numbers you're working with. Does anyone know if this limit has
been improved?

What would those here recommend as a somewhat efficient and, perhaps
more importantly, easy-to-implement algorithm for *proving* primality
for numbers of a general form?

--
Alan Eliasen | "Furious activity is no substitute
eliasen@... | for understanding."
http://futureboy.us/ | --H.H. Williams
• The small Darío Alpern s applet in this page: http://www.alpertron.com.ar/ECM.HTM also certifies it is a prime in a fraction of second. (On a 1.13 GHz
Message 4 of 4 , May 2, 2007

http://www.alpertron.com.ar/ECM.HTM

also certifies it is a prime in a fraction of second. (On a 1.13 GHz
Pentium.)

Josechu

On 5/2/07, aldrich617 <aldrich617@...> wrote:
>
> Trial division can be an easy and predictable way to verify
> primality if the number is not too large. I am hoping that
> someone who has a commercial factoring program will check
> the time it takes to verify that 1986619529684749961 is prime.
> pentium3 866 Dell. This prime is only special in that it
> appears on a proved +1 mod 10 sequence. If this were not known
> it would take my program 640 seconds to resolve.
>
> aldrich
>
>
>

[Non-text portions of this message have been removed]
Your message has been successfully submitted and would be delivered to recipients shortly.