## Lucas Sequence modular sqrt help

Expand Messages
• I ve never coded anything to do with Lucas sequences before, forgive my naivete, but I m avin a spo of bovva. I m using a hybrid between Riesel A3.24 and
Message 1 of 2 , Dec 2, 2001
• 0 Attachment
I've never coded anything to do with Lucas sequences before, forgive my naivete, but I'm 'avin' a spo' of bovva.
I'm using a hybrid between Riesel A3.24 and Crandall/Pomerance 2.3.8.

Let's take the simplest Lucas example, p=17. Say I want sqrt(15 mod 17). Here are the parameters to the Lucas Sequence I've calculated:
<<<
Lucas sqrt(15) mod 17 - P=1 Q=15 desc=10, want v[9]
>>>
That looks right. 10 is a quadratic non-residue mod 19.

By hand/mathematica I've created the Lucas sequence:
<<<
v[0]=2, 1, 5, 7, 0, 14, 14, 8, 2, v[9]=1
>>>

In my code I have generated the lucas sequence
<<<
v[2]=5 v[3]=7
v[4]=0 v[5]=14
v[9]=1
>>>
Which agrees with the hand calculation at every point.

However according to Riesel it should be that
v[(p+1)/2]^2 == 4.c (mod p)
i.e. v[9]^2 == 9 (mod 17)
Which is patently not the case.

Are my parameters wrong? Or my Lucas Sequence generated therefrom? Or have I made some other incorrect assumtion somewhere?

Any help would be appreciated.
Cheers,
Phil

Don't be fooled, CRC Press are _not_ the good guys.
They've taken Wolfram's money - _don't_ give them yours.
http://mathworld.wolfram.com/erics_commentary.html

Find the best deals on the web at AltaVista Shopping!
http://www.shopping.altavista.com
• ... A short and simple answer, thank you. Bleary-eyed, I incorrectly changed my code just now, and the code spewed out the correct answers, but on checking
Message 2 of 2 , Dec 3, 2001
• 0 Attachment
On Sun, 02 December 2001, Marcel Martin wrote:
> Phil,
>
> >Lucas sqrt(15) mod 17 - P=1 Q=15 desc=10, want v[9]
>
> desc = P^2 - 4Q = 1 - 4x15 = -59, but -59 mod 17 = 9. This is a
> square!

A short and simple answer, thank you.

Bleary-eyed, I incorrectly changed my code just now, and the code spewed out the correct answers, but on checking back, I noticed the code was now certainly wrong. So I changed it back to what I believe it was at first, and it now works???? Heaven knows where the descriptor being 10 came from, but that was certainly the root of the problem.

I shall of course run with sanity checking to re-square anything I take the root of, but apart from that, I think my modular square root code is finally complete (you don't want to know how long it took...).

Thanks again Marcel,
Phil
(Right, lets go smash a few records... :-) )

Don't be fooled, CRC Press are _not_ the good guys.
They've taken Wolfram's money - _don't_ give them yours.
http://mathworld.wolfram.com/erics_commentary.html

Find the best deals on the web at AltaVista Shopping!
http://www.shopping.altavista.com
Your message has been successfully submitted and would be delivered to recipients shortly.