Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie

Maths question

  • 14-01-2007 09:14PM
    #1
    Registered Users, Registered Users 2 Posts: 259 ✭✭


    Can anyone tell me if there is a formula or a quick way( instead of using brute force and trying all combinations) of solving problems like this -

    Find D, where
    e*d mod z = 1 mod z

    where e = 7
    and z = 120

    So in this example it is

    7*d mod 120 = 1 mod 120
    => 7*d mod 120 = 1

    I know the answer for d in this is 103(as I used brute force).

    Thanks


Comments

  • Registered Users, Registered Users 2 Posts: 3,608 ✭✭✭breadmonkey


    What do you mean by brute force? Is this not just simple manipulation?


  • Registered Users, Registered Users 2 Posts: 259 ✭✭cobijones


    What do you mean by brute force? Is this not just simple manipulation?

    Sorry forgot about this - the brute force I was talking about was just going through numbers until the answer is found. It's used in Diffie Hellman encryption. Its Eulers Theorem I think.


  • Registered Users, Registered Users 2 Posts: 861 ✭✭✭Professor_Fink


    Yes, it's called the extended euclidean algorithm:

    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

    It appears in virtually all introductory number theory texts.


Advertisement