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.