Fastest sieving program?

[paulunderwood]

Originally Posted by PawnProver44

Any other forms available? The only test that I think would Work is Lucas's Test (N-1), I do not know where I am going to calculate large exponents. Are there any mathematics libraries that would allow me to do large exponent and modular computation?

PFGW uses the fastest library on the planet.

[science_man_88]

Originally Posted by PawnProver44

Also, which value: k, b, n, or c would be the easiest to (substitute) find primes for

the pairings k and c, and b and c have to be coprime ( aka not share a divisor) for the form to have a chance at being prime. also all primes greater than 3 have to have remainder 1 or 5 when dividing by 6.

[PawnProver44]

Originally Posted by paulunderwood

PFGW uses the fastest library on the planet.

Are there any other forms I could use to prove large primes besides k*b^n+-1? Just Curious.

[paulunderwood]

Originally Posted by PawnProver44

Are there any other forms I could use to prove large primes besides k*b^n+-1? Just Curious.

In general: no. As long as you know >12.5% factorisation of N^2-1, you can prove something prime in a reasonable amount of time. For example this prime.

If k (and c) are small the underlying library is faster.

[PawnProver44]

Originally Posted by paulunderwood

In general: no. As long as you know >12.5% factorisation of N^2-1, you can prove something prime in a reasonable amount of time. For example this prime.

If k (and c) are small the underlying library is faster.

What test would you apply?

[paulunderwood]

Originally Posted by PawnProver44

What test would you apply?

I am not sure about what you are asking. With 33.333...% of N-1 or N+1 one can use BLS; for 16.666...% of N^2-1 one can use the combined test; with 15% of the factors of N^2-1 one can prove with KP and with >12.5% of N^2-1 one can apply CHG. All can be done in a "reasonable" amount of time.

In prime searching all things are equal... for maximum speed choose k (and c) small, so that the library operates most quickly. Then run a sieve so that the elimination rate is equal to the average PRP test time of the range -- for varying n, this is about 80% of the range. Finally, run PFGW on what the sieve leaves.

[PawnProver44]

Originally Posted by paulunderwood

I am not sure about what you are asking. With 33.333...% of N-1 or N+1 one can use BLS; for 16.666...% of N^2-1 one can use the combined test; with 15% of the factors of N^2-1 one can prove with KP and with >12.5% of N^2-1 one can apply CHG. All can be done in a "reasonable" amount of time.

In prime searching all things are equal... for maximum speed choose k (and c) small, so that the library operates most quickly. Then run a sieve so that the elimination rate is equal to the average of of the range -- for varying n, this is about 80% of the range. Finally, run PFGW on what the sieve leaves.

Well in that case, here is an example: say we had large enough n for a probable prime of the form k*149^n +1 (k is large, say 3,000 digits), however we cannot factor k. Is there a way to prove k*149^n+1 prime?

[paulunderwood]

Originally Posted by PawnProver44

Well in that case, here is an example: say we had large enough n for a probable prime of the form k*149^n +1 (k is large, say 3,000 digits), however we cannot factor k. Is there a way to prove k*149^n+1 prime?

N-1 = k*149^n. So we know some of the factorisation of N-1. Apply what I said above. For k=3,000 digits, any problem numbers can be done with Primo.

[PawnProver44]

Originally Posted by paulunderwood

N-1 = k*149^n. So we know some of the factorisation of N-1. Apply what I said above. For k=3,000 digits, any problem numbers can be done with Primo.

Do we have to factor k or not in order to prove k*149^n+1 prime? Factoring k would take a long time.

[paulunderwood]

Originally Posted by PawnProver44

Do we have to factor k or not in order to prove k*149^n+1 prime? Factoring k would take a long time.

[PawnProver44]

Originally Posted by paulunderwood

Ok, I'll do some of the work to fix the variable n. The k value I am trying to find. That shouldn't be too hard, right