Primalty Test

[rogue]

What is the generic form for the numbers you are testing? You might be able to use an existing sieving program to shorten your list.

I would suggest WinPFGW for PRP or primality testing of most numbers. LLR is faster for some forms and Proth is faster for others, but WinPFGW can handle any form for PRP testing and is fastest for forms not covered by LLR and Proth. For primality testing that LLR, Proth and WinPFGW cannot do, Primo is your next choice. It uses ECPP to test the primality of numbers of any form, but ECPP is slow it can only handle numbers a few thousands bits in length in a reasonable time.

[Cyclamen Persicum]

No I wrote this program myself.
What is a PRP-Program by the way? and what does the program do you mentioned?

That is great!!! I also have written a probable-prime prog:
http://persicum.front.ru/purgen_07.zip
It would be interesting to bench yours and mine...
BTW, I don't use any libraries such as GMP and my prog is written in
Pascal-Delphi. However, it can attach fftw3.dll to speed up fast fourier transform about 3 times. It also can find Proth Primes using Jacoby Symbol and check if they to be Fermat divisors. So I also interested in implementation
the fast compositeness proof another than trial division or fermat-Euler-small-little theorem. And I don't use a sieve, just trial division by small first primes from table.

Now about world famous progs mentioned above:
NewPGen - Eratothphenes sieve for various kinda primes, you may very
fast rull out candidates by factors even much greater then 2^32.

PRP.EXE - Probable prime check for already sieved candidates, written by His Majesty George woltman, who also wrote Prime95exe. Increadibly fast fft multiplication-squaring, usually 5-10 times faster then all another progs (until they begin use his libraries).

[juergen]

Originally Posted by rogue

What is the generic form for the numbers you are testing? You might be able to use an existing sieving program to shorten your list.

I would suggest WinPFGW for PRP or primality testing of most numbers. LLR is faster for some forms and Proth is faster for others, but WinPFGW can handle any form for PRP testing and is fastest for forms not covered by LLR and Proth. For primality testing that LLR, Proth and WinPFGW cannot do, Primo is your next choice. It uses ECPP to test the primality of numbers of any form, but ECPP is slow it can only handle numbers a few thousands bits in length in a reasonable time.

The generic form is:

p*n+1

where p is a prime and n any natural number smaller than p.
I guess that doesn't help a lot :o(

Juergen

[R.D. Silverman]

Originally Posted by juergen

The generic form is:

p*n+1

where p is a prime and n any natural number smaller than p.
I guess that doesn't help a lot :o(

Juergen

May I suggest that all of you who are involved in this discussion actually
go out and READ about it? See David Bressoud's book, for example.
I get the feeling that this entire discussion is a case of "the blind leading
the blind". Please make at least *some* effort to study the subject before
making random pronouncements.

If one knows that N = np + 1, where p is prime and n < p, then one
may quickly PROVE that N is prime. You know all the factors of N-1 up
to sqrt(N) and may hence use the theorem of Brillhart, Lehmer, & Selfridge.
Indeed, by results of Pomerance and Konyagin, you may take n to be as
large as N^(7/10) and still prove primality. If you know any factors of N+1,
or indeed any factors of phi_k(N) where phi_k is the k'th cyclotomic polynomial, you many take n to be even larger.

Knowing that N = np+1 for known p, p large, helps a LOT.

Also, look up the Shawe-Taylor algorithm.

[juergen]

Originally Posted by Bob Silverman

May I suggest that all of you who are involved in this discussion actually
go out and READ about it? See David Bressoud's book, for example.
I get the feeling that this entire discussion is a case of "the blind leading
the blind". Please make at least *some* effort to study the subject before
making random pronouncements.

If one knows that N = np + 1, where p is prime and n < p, then one
may quickly PROVE that N is prime. You know all the factors of N-1 up
to sqrt(N) and may hence use the theorem of Brillhart, Lehmer, & Selfridge.
Indeed, by results of Pomerance and Konyagin, you may take n to be as
large as N^(7/10) and still prove primality. If you know any factors of N+1,
or indeed any factors of phi_k(N) where phi_k is the k'th cyclotomic polynomial, you many take n to be even larger.

Knowing that N = np+1 for known p, p large, helps a LOT.

Also, look up the Shawe-Taylor algorithm.

Thank you very much for your hint. But if you suggest something like this with a faint hint of a raised index finger then please make sure, that you also read all of the previous postings. I already wrote that I can proove primalty in as few steps as it takes to perform 1.5 times the regular fermat check.
And I of course know that this form is very special. That is btw. what I found out myself without any help and any studies.
So what I need is not a method to proof primalty, but I need a fast method which is faster than my proof to reduce the number of unnecessary attempts to proof a composite number. That is what I wrote above.

There are some little hints in your posting which you probably should try to avoid in your postings. I don't feel that I am blind and I also make no random announcements. I proofed my algorithm mathematically btw. I only want to speed it up. That is a big difference!

But thank you for your hints, I will check if they really help. Since I know that the fermat check is indeed very fast. But if what you suggest is really faster, then it would be great.

[Cyclamen Persicum]

How do you perform your trial division?
You can use modular arithmetic or sieve technique.
Let your number has a form: k*p+1, you can calculate only once
z=p mod s, then k*p+1 = k*z+1 (mod s).
This will speed up your trial division.
Or you can use a sieve, if k*p+1=0 (mod s), then
you should strike out all k+i*s.
Of course, these speed-ups are trivial, and you have already known about them.

[juergen]

Originally Posted by Cyclamen Persicum

How do you perform your trial division?
You can use modular arithmetic or sieve technique.
Let your number has a form: k*p+1, you can calculate only once
z=p mod s, then k*p+1 = k*z+1 (mod s).
This will speed up your trial division.
Or you can use a sieve, if k*p+1=0 (mod s), then
you should strike out all k+i*s.
Of course, these speed-ups are trivial, and you have already known about them.

I perform the trial divisions without further optimizations, but from the result I build a sieve. So I only perform the trial divisions on one candidate and build a sieve on the result of this divisions. The sieving is relatively fast. Okay of course if I can speed it up a bit I can do much more trial divisions in the same time.
But I guess that this would only reduce the unnecessary trial divisions by not more than 10%. That is just a guess, but the ratio of Pi(n)/n doesn't decrease very fast :o(
I'll think about this suggestion. Thank you :o)

[Cyclamen Persicum]

You have not said the main thing!
How long prime are you looking for?
How fast is your Modular Power?
Is it as fast as mine (if you downloaded my prog),
or it is as fast as PRP.EXE, or you don't use FFT at all,
or what ???

[juergen]

Originally Posted by Cyclamen Persicum

You have not said the main thing!
How long prime are you looking for?
How fast is your Modular Power?
Is it as fast as mine (if you downloaded my prog),
or it is as fast as PRP.EXE, or you don't use FFT at all,
or what ???

I use the GMP-Routine to perform the modular power calculation.
This is pretty fast. It takes about 5 to 10 seconds on a Pentium III machine (666 Mhz) for a number which is about 3000 digits long. I don't want to find new implementations of such basic things like mod powers, because i think they are already tested well and optimized to the max. My systems runs on linux, so i guess it is not possible to run your prog :o(

[Cyclamen Persicum]

I use the GMP-Routine to perform the modular power calculation.
This is pretty fast. It takes about 5 to 10 seconds on a Pentium III machine (666 Mhz) for a number which is about 3000 digits long.

That is good! My prog takes 20s for general modulus and 5s for k*2^n+1 on
the same conditions.
And what is length of your prime? If it is only 3000 digits long, it should take only one minute to find it.

[juergen]

Originally Posted by Cyclamen Persicum

I use the GMP-Routine to perform the modular power calculation.
This is pretty fast. It takes about 5 to 10 seconds on a Pentium III machine (666 Mhz) for a number which is about 3000 digits long.

That is good! My prog takes 20s for general modulus and 5s for k*2^n+1 on
the same conditions.
And what is length of your prime? If it is only 3000 digits long, it should take only one minute to find it.

I don't know the current size precisely, but it should be a little bit larger than 3000.
The time it takes to find a larger one is not constant. But it is more than a minute. The sieving already takes longer than one minute.
What machine are you using?