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

Re: [PrimeNumbers] I have a question,please...

Expand Messages
  • Phil Carmody
    On Thu, 6/27/13, Norman Luhn wrote: Subject: [PrimeNumbers] I have a question,please... To: primenumbers@yahoogroups.com
    Message 1 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.