Loading ...
Sorry, an error occurred while loading the content.

Lucas Sequence modular sqrt help

Expand Messages
  • Phil Carmody
    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
    • Phil Carmody
      ... 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.