2 Iterative EGCD (a) Convert the subtractive form of the recursive EGCD algorithm into an iterative form involving a while loop. Your algorithm should involve only a single pass, not a pass up and then a pass down. (HINT: First do this for the subtractive form of the GCD. Then think about what you want to keep track of as you descend into the EGCD so that you are able to return the desired answer at the end without having to go back up.) (b) Show that the subtractive form of your iterative EGCD outputs the correct answer for the following. (Write the updated values computed by the algorithm after each iteration). gcd(54,17)=1, egcd(54, 17) (d=1, a=-11,35)=1=(-11). 54+(35). 17. or ((d=1, a=6, -19)=1= (6-54+(-19). 17. Feel free to collect steps together for things that seem repetitive. Do you see now why we teach you the mod form of the EGCD? 2 Iterative EGCD (a) Convert the subtractive form of the recursive EGCD algorithm into an iterative form involving a while loop. Your algorithm should involve only a single pass, not a pass up and then a pass down. (HINT: First do this for the subtractive form of the GCD. Then think about what you want to keep track of as you descend into the EGCD so that you are able to return the desired answer at the end without having to go back up.) (b) Show that the subtractive form of your iterative EGCD outputs the correct answer for the following. (Write the updated values computed by the algorithm after each iteration). gcd(54,17)=1, egcd(54, 17) (d=1, a=-11,35)=1=(-11). 54+(35). 17. or ((d=1, a=6, -19)=1= (6-54+(-19). 17. Feel free to collect steps together for things that seem repetitive. Do you see now why we teach you the mod form of the EGCD