Browse Groups

(2)
• NextPrevious
Message 1 of 2 , Jul 15
View Source
On Thu, 6/27/13, Norman Luhn <n.luhn@...> wrote:
"""
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.