Advertisement
Help Keep Boards Alive. Support us by going ad free today. See here: https://subscriptions.boards.ie/.
If we do not hit our goal we will be forced to close the site.

Current status: https://keepboardsalive.com/

Annual subs are best for most impact. If you are still undecided on going Ad Free - you can also donate using the Paypal Donate option. All contribution helps. Thank you.
https://www.boards.ie/group/1878-subscribers-forum

Private Group for paid up members of Boards.ie. Join the club.

Maths question

  • 14-01-2007 09:14PM
    #1
    cobijones
    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

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


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


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


    breadmonkey wrote:
    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.


  • #4
    Professor_Fink
    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