My values for p, e, and q are as follows:
p = 150, e = 18,565, and q = 140
- Observe that there are three question tabs (sheets) for Q1, Q2, and Q3. - Do not modify this document in any way, except to fill in cells that are highlighted in yellow. Any other modifications may affect your grade negatively since your responses are expected to be in particular locations. - Do not input formulas into your answers. Input exact numerical answers where applicable. - Complete all three questions as instructed. Each question is described briefly below. Ensure you have completed all three questions before submitting. Name: U#: Q1: You will compute gcd($(n), e) and find integers x and y such that the GCD is equal to ax+by where a=(n) and b=e. From y, you will find d, the inverse of e modulo d(n), reducing modulo d(n) if necessary. Q2: You will compute the reduced inverse d of e modulo (n), in a different way, using the method of repeated squaring. This method is justified by a particular theorem. Q3: Using the d you found from Q1 and Q2 (which should be the same), you will digitally sign your U# as instructed. Warning: Be careful when computing remainders involving negative numbers. Some calculators may compute -x mod n (or -x % n) as something equivalent to x rather than -x, which are not generally equivalent. Verify all of your calculations before you submit! (a) Input your p, q, and e below. Ensure that these are correct. q= e- (b) Let n=pq and input the numeric values of n and (n) (The Euler Phi Function) na (n)-1 (c) Write down the definition of E(x) according to your assigned values. Substitute numeric values for e and n where appropriate. The symbol can be used to indicate exponentiation. E(x)=1 (d) Compute ged($(n), e) using the Extended Euclidean Algorithm below. Replace +(n) and e with the correct numeric values below. Leave unused cells blank. The last row should contain the GCD, and values x and y such that ged("(n), e) = ax+by where a=(n) and b=e. Xi lai -1 0 n on) e ly 1 ol 0 1 From your results, compute d, the inverse of e as a reduced residue modulo (n), i.e. Os doin). Note: Reducing may or may not be necessary. It is certainly necessary if the result is negative. da To check your work, verify that de = 1 (mod (n)) Remember to replace (n) and e with the actual numbers. Make sure to verify your results before you submit!!! - Observe that there are three question tabs (sheets) for Q1, Q2, and Q3. - Do not modify this document in any way, except to fill in cells that are highlighted in yellow. Any other modifications may affect your grade negatively since your responses are expected to be in particular locations. - Do not input formulas into your answers. Input exact numerical answers where applicable. - Complete all three questions as instructed. Each question is described briefly below. Ensure you have completed all three questions before submitting. Name: U#: Q1: You will compute gcd($(n), e) and find integers x and y such that the GCD is equal to ax+by where a=(n) and b=e. From y, you will find d, the inverse of e modulo d(n), reducing modulo d(n) if necessary. Q2: You will compute the reduced inverse d of e modulo (n), in a different way, using the method of repeated squaring. This method is justified by a particular theorem. Q3: Using the d you found from Q1 and Q2 (which should be the same), you will digitally sign your U# as instructed. Warning: Be careful when computing remainders involving negative numbers. Some calculators may compute -x mod n (or -x % n) as something equivalent to x rather than -x, which are not generally equivalent. Verify all of your calculations before you submit! (a) Input your p, q, and e below. Ensure that these are correct. q= e- (b) Let n=pq and input the numeric values of n and (n) (The Euler Phi Function) na (n)-1 (c) Write down the definition of E(x) according to your assigned values. Substitute numeric values for e and n where appropriate. The symbol can be used to indicate exponentiation. E(x)=1 (d) Compute ged($(n), e) using the Extended Euclidean Algorithm below. Replace +(n) and e with the correct numeric values below. Leave unused cells blank. The last row should contain the GCD, and values x and y such that ged("(n), e) = ax+by where a=(n) and b=e. Xi lai -1 0 n on) e ly 1 ol 0 1 From your results, compute d, the inverse of e as a reduced residue modulo (n), i.e. Os doin). Note: Reducing may or may not be necessary. It is certainly necessary if the result is negative. da To check your work, verify that de = 1 (mod (n)) Remember to replace (n) and e with the actual numbers. Make sure to verify your results before you submit
