Extended Euclidean algorithm

Discussion in 'General Chat' started by sxzbisid, Nov 30, 2018.

  1. sxzbisid

    sxzbisid is a Trusted Warez Postersxzbisid DEV Guild Member DEV Guild Reverser

    Joined:
    Jul 11, 2017
    Messages:
    243
    Likes Received:
    3,112
    I am solving this equitation, looking for the output based on given input. I've been told by one mathematician this can be solved using Extended Euclidean algorithm, but dunno how, anyone (@_peter_ r?) kind to help, please?


    [​IMG]


    BTW, this is Wolfram Alpha solution:
    [​IMG]
     
  2. sxzbisid

    sxzbisid is a Trusted Warez Postersxzbisid DEV Guild Member DEV Guild Reverser

    Joined:
    Jul 11, 2017
    Messages:
    243
    Likes Received:
    3,112
    No mathematician on the board? Or university folk asking math colleague? It looks so easy...
     
  3. sxzbisid

    sxzbisid is a Trusted Warez Postersxzbisid DEV Guild Member DEV Guild Reverser

    Joined:
    Jul 11, 2017
    Messages:
    243
    Likes Received:
    3,112
    Thanks to a friend, solution is quite straightforward.

    [​IMG]
     
  4. RoOkiE JoeY

    RoOkiE JoeY Registered User Reverser

    Joined:
    Feb 10, 2018
    Messages:
    35
    Likes Received:
    326
    you need to solve modular Inverse of (0x2a29,0xfff1)

    getting the ModularInverse you can solve it ModInv(a,b)*Input mod b
    but remember to obtain a valid solution a and b needs to be coprime!!

    [​IMG]

    [​IMG]
     
    Last edited: Dec 5, 2018 at 17:15
  5. sxzbisid

    sxzbisid is a Trusted Warez Postersxzbisid DEV Guild Member DEV Guild Reverser

    Joined:
    Jul 11, 2017
    Messages:
    243
    Likes Received:
    3,112
    @RoOkiE JoeY, WOW! Thank you very much, I am impressed, thank you for an explanation. Can you share gRn Rsa-Donkey, please?
     
  6. RoOkiE JoeY

    RoOkiE JoeY Registered User Reverser

    Joined:
    Feb 10, 2018
    Messages:
    35
    Likes Received:
    326
    i am sorry to disappoint you but this tool will stay private
     
  7. draww

    draww is a Trusted Warez Posterdraww Super Moderator Staff Member Super Moderator DEV Guild Reverser

    Joined:
    Aug 22, 2008
    Messages:
    1,879
    Likes Received:
    43,803
    let's get the basics first ;)



    btw rsa-donkey 1.2.2 beta is on the net but only covers rsa (you won't find above calculator tab)
     
    Challenger likes this.
  8. RoOkiE JoeY

    RoOkiE JoeY Registered User Reverser

    Joined:
    Feb 10, 2018
    Messages:
    35
    Likes Received:
    326
    @draww

    indeed basic are fundamental.

    Yes the RSA-Donkey 1.2.2 was released few years back on exetools board
    but there was no feedback so the project was stopped, in the meantime we added few things that can become handy when dealing with such stuff.
     
    Challenger and draww like this.