- Hello,

New to the list and I've got a few questions about sieving Proth

numbers in relation to the Sierpinski conjecture.

I know Mikael Klasson and Paul Jobling have written an insanely

fast siever for x86 via lots of optimisations and hand hackery

of assembly. I'm using this very program to contribute to the

SeventeenOrBust.com project.

I'm looking to get something done in C (although I am using the

GMP library which does use assembly for some processors). The

biggest 'problem' with this library is a lack of a modmul

operation. I might have to grab Knuth and see what I can magic

up.

I've 'stolen' lots of good ideas from what I can see in the output

of proth_sieve during initialisation (finding the optimal mod value

of n's for each k and combining this into one large group).

I then implement the baby-steps giant-steps algorithm for solving

the discrete log (right now it picks 15840 for m instead of using

sqrt(p) which can be huge).

I'm just reading up on Silver-Pohlig-Hellman and how that can

help when p-1 is smooth.

My main question though, is about removing k or p candidates

before I even bother trying to calculate the discrete log to

solve for n. I've noticed that the stat.txt value from

proth_sieve claims that roughly 1/4 of all p's were 'whacked'

along with 1/2 of the k values for each p.

Under what conditions is a k or p not even tested?

Right now I only have 2 possible conditions, based on requirements

of Baby-Steps Giant-Steps, but they rarely ever stop a k or p

being tested.

1) a whole p is untested if (2^-1 mod p) doesn't exist.

2) an individial k is untested if (k^-1 mod p) doesn't exist.

Is it something to do with the Jacobi symbols that are computed

during initialisation, and I'd guess it has to do with the

k-values but I just can't see what it could be.

I had previously looked at the problem a different way, that is

making me think that there must be a way to detect it:-

Compute initial_r = k*2+1 mod p.

If initial_r == 1 then stop, p will never factor k

set r=initial_r

set n=1

while( n < 50000000 ) {

if( r == 0 ) {

stop. p is a factor for n

}

r=((2*r)+1) mod p

n=n+1

if( r == initial_r ) {

stop. p will never be a factor. cyclic loop of r.

}

}

Many k,p values will enter loops (of a size which is a factor of

p-1) and r will never equal 0. I could never work out whether it

was possible to detect this 'in advance'.

Thanks in advance,

-Alex - Hi Alex,

> I'm just reading up on Silver-Pohlig-Hellman and how that can

If you save away the factors of p-1 when you producd them from your sieve it

> help when p-1 is smooth.

will help you.

> My main question though, is about removing k or p candidates

You are right to think about the Jacobi/Legendre symbol, as that is the

> before I even bother trying to calculate the discrete log to

> solve for n. I've noticed that the stat.txt value from

> proth_sieve claims that roughly 1/4 of all p's were 'whacked'

> along with 1/2 of the k values for each p.

>

> Under what conditions is a k or p not even tested?

reason. For Proth numbers, we are interested in whether, for a given k, the

values k.2^n+1 are 0 mod p, for a range of values of n.

Consider the even values of n. For these, we want to know if

k.2^n = -1 (mod p)

ie that

k.2^(2m) = -1 (mod p)

so 2^(2m) = -1.k^(-1) (mod p)

ie (2^m)^2 = -1.k^(-1) (mod p)

The LHS is a square, so this can only happen if the RHS is a quadratic

residue mod p. Similarly, for the odd values of n, it is a question of

whether -1.(2k)^-1 (mod p) is a quadratic residue mod p. This explains why

about 1/4 of all p's can be completely ignored - both are quadratic

non-residues mod p. In some cases, it turns out that we can ignore the odd

values of n but not the even ones, or vice versa.

Regards,

Paul.

__________________________________________________

Virus checked by MessageLabs Virus Control Centre. > Consider the even values of n. For these, we want to know if

I haven't though about this for a long time, but, of course, we don't need

>

> k.2^n = -1 (mod p)

>

> ie that

>

> k.2^(2m) = -1 (mod p)

>

> so 2^(2m) = -1.k^(-1) (mod p)

>

> ie (2^m)^2 = -1.k^(-1) (mod p)

the inverses on the RHS, since we can rewrite this to say that

(2^m)^(-2) = -1.k (mod p)

and since the LHS is still a square, we just see if -k is a QR mod p or not.

Regards,

Paul.

__________________________________________________

Virus checked by MessageLabs Virus Control Centre.