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

I have a question,please...

Expand Messages
  • Norman Luhn
    what is the best way to calculate x (via hand) for 1009 is factor of (x * 2333+ 577) 12 years ago I found a way to calculate it fast, but maybe it is not the
    Message 1 of 2 , Jun 27, 2013
    • 0 Attachment
      what is the best way to calculate x (via hand) for

      1009 is factor of (x * 2333+ 577)

      12 years ago I found a way to calculate it fast, but maybe it is not the
      best way.

      For larger ones like

      6309163058327 is factor of ( x * 468126486184 + 687164871), I need maybe
      <<50 steps.

      Best and Thanks.
    • Phil Carmody
      On Thu, 6/27/13, Norman Luhn wrote: Subject: [PrimeNumbers] I have a question,please... To: primenumbers@yahoogroups.com
      Message 2 of 2 , Jul 15, 2013
      • 0 Attachment
        On Thu, 6/27/13, Norman Luhn <n.luhn@...> wrote:
        """
        Subject: [PrimeNumbers] I have a question,please...
        To: "primenumbers@yahoogroups.com" <primenumbers@yahoogroups.com>
        Date: Thursday, June 27, 2013, 5:50 PM

        what is the best way to calculate x
        (via hand) for

        1009 is factor of (x * 2333+ 577)

        12 years ago I found a way to calculate it fast, but maybe
        it is not the
        best way.

        For larger ones like

        6309163058327 is factor of ( x * 468126486184 + 687164871),
        I need maybe
        <<50 steps.

        Best and Thanks.
        """

        1009 is factor of (x * 2333+ 577)
        =>
        x * 2333 + 577 == 0 (mod 1009)
        =>
        x * 2333 == -577 (mod 1009)
        =>
        x == -577 * (2333^-1) (mod 1009)

        The calculation of the modular inverse can be done by nothing apart from addition and subtraction using the (extended) Euclidean algorithm, as it will give you a.s + b.t = 1, and when s=2333 and t=1009, that gives you 2333.a == 1 (mod 1009).

        Phil
        --
        () ASCII ribbon campaign () Hopeless ribbon campaign
        /\ against HTML mail /\ against gratuitous bloodshed

        [stolen with permission from Daniel B. Cristofani]
      Your message has been successfully submitted and would be delivered to recipients shortly.