basic questions

[Greenbank]

Hello,

Been reading around and playing around with the bignum stuff in the ssl library on linux (to implement some simple programs).

The more questions that are answered here, the better position I'd be in to write a few pages for the Wiki...

I'll skip the project descriptions, as some have already done that. Questions are marked with a Q: at the start of the line. Probably best not to quote the entire article when replying to the questions. We'll see how it goes, this is mainly a test of my understanding of the project.
--

OK. The purpose of the project is to find the minimum value of n for a specific k so N=k*2^n+1 is prime.

We want to know if N is prime or composite but, more importantly, we want to be able to prove that they are either prime or composite.

Proth testing for Primality.

Q: Is this the same thing as PRP that someone else referred to?

Proth's theorem states that for N = k.2^n+1 with k odd and 2^n > k, if there
exists an integer a such that
a^(N-1)/2 \equiv -1 (mod N)
then N is prime.

Q: Does a have an upper bound? I can't see it referenced anywhere. I've seen that the sb client seems to test values of a up to and slightly above n.

Q: If there is an upper bound, does a proth test that fails to prove primality prove that the number is composite? Or does it just leave the door open for a larger bound for a?

The proth test is a lengthy process and for n values in the 9M range it can take up to 24 hours on average PC hardware. (Ignore the timings for now!)

The problem is that if no value of a is found in the proth test, we still cannot prove that N is composite.

The best way to prove that a number is composite is to factorise it, or at least provide one factor. This is where sieving comes in.

Even if the proth test can prove that the number is composite (see Q: above) it still doesn't provide us with a factor, and a factor is required to provide absolute proof that a specific k,n pair is composite. See Factoring below.

Sieving

Sieving is the process of eliminating k,n pairs by trial division by known primes.

Consider k=46157, n=698206. The resulting number has 210186 digits!

If the proth test was run it would not find a value for a to show the number was prime. And there would be no 'proof' that the number was composite. The proth
test would never prove the number to be prime, because it is not.

However, this number, and many many others, can be eliminated early on by simple trial division.

The 210186 digit number (k=46157,n=698206) is divisible by 3.

This check can be performed in less than a hundredth of a second on the same hardware as above.

The sieving process checks every k,n pair and eliminates each pair that produces a number with a certain factor.

By starting low, i.e. 3, a large number of k,n pairs can be ruled out.

Infact 50% of all k,n pairs are be divisible by 3.

For the next prime number (5) 25% of all k,n pairs will be divisible by 5. Although some of these will have already been ruled out as being divisible by 3.

Progressively larger and larger prime numbers are used to remove more k,n pairs from the list of possibilities.

More importantly, a known factor of these k,n pairs can be recorded, to prove that the numbers are composite.

Two-pronged attack: Sieving and Proth testing

So without Sieving we could waste a large amount of time performing Proth tests on k,n pairs that are trivially composite (i.e. they have a small factor).

But sieving can never prove that a specific number is prime. Only the Proth test can do that.

Also only the Proth test can give us the value for a that we can provide as proof that N (the value of the k,n Proth number) is prime.

The current sieving process is checking remaining k,n pairs for factors around 8E14.

If we square this (if we've searched for every factor up x then the largest number we can be sure we've searched every factor for is x^2), we're looking at a 30 digit number.

Now remember that k=46157,n=698206 has 210186 digits.

I'm sure that the universe will have suffered its own heat death before sieving could get anywhere near 0.0001% of the way towards sieving the required range for numbers like the above.

Obviously the larger the test factor used, the fewer k,n pairs it will remove from the list of possible primes.

Sieving at the 8E14 range is still providing some useful factors though. In my own range (880000G to 881000G) I've already found 3 factors in 24 hours. This means that the Proth test need not be performed for 3 seperate k,n pairs. At 24 hours each, that's a useful contribution.

At the time of writing the siever is still applying the test factor to each and every possible k,n pair, and there are 10 k values for which no prime has been found.

However, imagine those 24 hours had been devoted to Proth testing and I'd luckily been assigned a k,n pair for which the Proth test popped out a provable prime.

Suddenly there's (assuming an even distribution of k,n pairs over the k values) 10% less work for the sievers (there's no need to check for factors for any pairs that share the k value of the recent prime.

Everyone would now be concentrating on only 9 possible values of k instead of 10. It would also remove lots of work from the second-pass queue (checking the residues from previous proth tests to ensure accuracy and veracity).

Factoring

But we still need to prove that we know some numbers are composite. This is where factoring comes in.

If the Proth test does prove that a number is composite, we need at least one factor to show this.

I'm sure someone can knock something up for factoring. I only know a tiny amount about Elliptic Curve Factorisation and nothing about the other algorithms used.

--

Hope this was useful.

[Greenbank]

Argh, this should really have been in the main forum.

Can one of the admins please move it up please!

And it looks like someone has just beaten me to it. *goes off to read theirs*

[royanee]

Ok, now I'm not sure how they choose A, but the according to our math whiz people we can show that the numbers are composite with a PRP test. If it returns a number that isn't an expected value, then it is composite. We have a double check to check the residues which removes any likely possibility that we incorrectly identified the number as composite. We DO sieve. We DO factor. The main problem with direct factorization is that it is SLOW! To try and factor the number up to a certain bounds can save a lot of time, but finding the actual factor can be next to impossible (more a waste of CPU time, but you know what I mean). To give you a good example, that smallest k/n pair for which we have no factor has withstood extremely high bounds and lots of factoring time (even though the n is less that 1000). At this point, I think I've answered all the questions I could answer. Anybody with the math background that can answer the other questions?