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