Sorry, an error occurred while loading the content.

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

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