LLR test starting values

[kuratkull]

Hello, I am in the process of rewriting some primality check proggies for myself.
Rabin-Miller is finished.
Lucas-Lehmer is almost finished...only needs a rewrite in GMP(GNU BigNum lib) to support large integers.

But now I am on Lucas-Lehmer-Riesel tests. The ordinary LL test is easy on the starting value, but for LLRs I could only find this on Wikipedia:

• If k is equal to 1, and n is odd, then we are dealing with Mersenne numbers, and can take u0 = 4.
• If n = 3 (mod 4), then we can take u0 = 3.
• If k = 3, and n = 0 or 3 mod 4 then u0 = 5778.
• If k = 1 or 5 mod 6 and 3 does not divide N, then we take u0 = (2+sqrt(3))^k + (2-sqrt(3))^k.
• Otherwise, we are in the case where k is a multiple of 3, and it is more difficult to select the right value of u0

Since I intend my proggie to be compatible with all inputs, it would be nice to know how to calculate the correct numbers.

Any help?

Thanks in advance,
kuratkull

[henryzz]

can someone rewrite that thing on wikipedia
there have been a few wondering about this
unfortunately i cant find the thread of the last conversation on thiss subject

[m_f_h]

Originally Posted by henryzz

can someone rewrite that thing on wikipedia
there have been a few wondering about this
unfortunately i cant find the thread of the last conversation on thiss subject

hum, I'd have said to look at the source of llr and found a link,
http://www.mersenne.org/gimps/llrsource.zip
on
http://forums.amd.com/forum/messagev...&enterthread=y

but that file has disappeared... is there a (c) issue?

anyway, in
Lucasian Criteria for the Primality of $\mathcal{N} = h \cdot 2^n - 1$
Hans Riesel
Mathematics of Computation, Vol. 23, No. 108 (Oct., 1969), pp. 869-875
doi:10.2307/2004975

it is suggested to take (for odd k < 2^n >= 4)
u0 = alpha^k+alpha^-k with alpha=(a+b sqrt(D))^2/r, (r/N)(a^2-b^2 D)/r=(D/N)=-1, r=|a^2-b^2 D|, N=k 2^n-1.

PS: D is squarefree, (D/N) is the Legendre symbol. Riesel himself says that he tries out values of D to find a suitable one.

[kuratkull]

Thanks m_f_h,
It's not very clear to me when I look it now, but I will give it another look tomorrow...it's late now :)
Thanks again!

[m_f_h]

Originally Posted by kuratkull

It's not very clear (...)

That's basically what is written on wikipedia... ;-)
I'm kidding - one could add these criteria from Riesel's Thm.5 of the cited article, but would this be useful/adequate for WP? I'll put a ref. to Riesel's article, though.

PS: Finally I also found the src of llr - if I looked at the right place, there it is also done using a loop that essentially checks all possibilities until finding one verifying the criteria.

PPS: the thread: http://www.mersenneforum.org/showthread.php?p=123605#12 - the issue ended with
"...(and to help me understand what starting numbers to use)"...

[kuratkull]

Ok, I looked at it now...and with a bit of fiddling, I'm sure I'd get it to work.
Your post hinted me to go to Jean's original page, and there was the source ;)
Thanks.

[kuratkull]

Originally Posted by m_f_h

it is suggested to take (for odd k < 2^n >= 4)
u0 = alpha^k+alpha^-k with alpha=(a+b sqrt(D))^2/r, (r/N)(a^2-b^2 D)/r=(D/N)=-1, r=|a^2-b^2 D|, N=k 2^n-1.

PS: D is squarefree, (D/N) is the Legendre symbol. Riesel himself says that he tries out values of D to find a suitable one.

Ok, as I understand, I will loop through increasing values of D(while I check if D is square-free and legendre(D/N) == -1), until one fits.
Besides D, I have the value N, k and n.
But how do I get the values a, b and r? I cracked myself over this for some time, but I couldn't figure it out :(

Thanks for any further help :)

-kuratkull