## proth sieving optimisations

Expand Messages
• 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
Message 1 of 3 , Jul 14, 2005
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'.

-Alex
• Hi Alex, ... If you save away the factors of p-1 when you producd them from your sieve it will help you. ... You are right to think about the Jacobi/Legendre
Message 2 of 3 , Jul 19, 2005
Hi Alex,

> I'm just reading up on Silver-Pohlig-Hellman and how that can
> help when p-1 is smooth.

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

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

You are right to think about the Jacobi/Legendre symbol, as that is the
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.
• ... I haven t though about this for a long time, but, of course, we don t need the inverses on the RHS, since we can rewrite this to say that (2^m)^(-2) = -1.k
Message 3 of 3 , Jul 19, 2005
> 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 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.
Your message has been successfully submitted and would be delivered to recipients shortly.