- aldrich617 wrote:

> Trial division can be an easy and predictable way to verify

I don't have any commercial factoring program but here is the free

> 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.

> My little homemade program takes about 160 seconds on a

> 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.

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 - aldrich617 wrote:
> Trial division can be an easy and predictable way to verify

Is your program dividing by all numbers up to sqrt[n] or just the

> 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.

> My little homemade program takes about 160 seconds on a

> 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.

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

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.

> My little homemade program takes about 160 seconds on a

> 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]