Homework Help is Here – Start Your Trial Now!
Math
Advanced Math
1.24. Let N, g, and A be positive integers (note that N need not be prime). Prove that the following algorithm, which is a low-storage variant of the square- and-multiply algorithm described in Section 1.3.2, returns the value gª (mod N). (In Step 4 we use the notation [x] to denote the greatest integer function, i.e., round x down to the nearest integer.) 1. 2. Input. Positive integers N, g, and A. Set a = g and b = 1. Loop while A > 0. 3. If A = 1 (mod 2), set b = b. a (mod N). 4. Set a a² (mod N) and A = = [A/2]. 5. If A > 0, continue with loop at Step 2. 6. Return the number b, which equals gª (mod N).

1.24. Let N, g, and A be positive integers (note that N need not be prime). Prove that the following algorithm, which is a low-storage variant of the square- and-multiply algorithm described in Section 1.3.2, returns the value gª (mod N). (In Step 4 we use the notation [x] to denote the greatest integer function, i.e., round x down to the nearest integer.) 1. 2. Input. Positive integers N, g, and A. Set a = g and b = 1. Loop while A > 0. 3. If A = 1 (mod 2), set b = b. a (mod N). 4. Set a a² (mod N) and A = = [A/2]. 5. If A > 0, continue with loop at Step 2. 6. Return the number b, which equals gª (mod N).

Advanced Engineering Mathematics
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
See similar textbooks
icon
Related questions
Question

1.3.2 also attached 

### Algorithm for Computing g^A (mod N) **Problem Statement:** Given three positive integers \( N \), \( g \), and \( A \) (where \( N \) is not necessarily a prime number), prove that the following algorithm, a low-storage variant of the square-and-multiply algorithm, computes \( g^A \mod N \). **Algorithm:** 1. **Initialization:** - Set \( a = g \) - Set \( b = 1 \) 2. **Loop Condition:** - Repeat while \( A > 0 \) 3. **Steps Inside the Loop:** - If \( A \equiv 1 \mod 2 \) (i.e., if \( A \) is odd) - Set \( b = b \cdot a \mod N \) - Set \( a = a^2 \mod N \) - Update \( A = \left\lfloor \frac{A}{2} \right\rfloor \) (i.e., divide \( A \) by 2 and round down to the nearest integer) - Continue the loop while \( A > 0 \) 4. **Termination:** - When the loop exits, return \( b \), which equals \( g^A \mod N \) **Detailed Explanation of the Algorithm:** The algorithm is designed to efficiently compute the modular exponentiation \( g^A \mod N \) using a low-storage approach. Here's how each step works: 1. **Initialization:** - Begin with `a` set to `g` and `b` set to `1`. 2. **Loop Condition & Process:** - Continue looping as long as \( A \) is greater than 0. 3. **Checking If \( A \) is Odd:** - If \( A \) is odd (remainder of \( A \) divided by 2 is 1), update `b` using multiplication followed by taking modulo \( N \). 4. **Square and Reduce `a`:** - Square `a` and take modulo \( N \) to keep the number manageable in size. 5. **Divide and Floor `A`:** - Update `A` by dividing it by 2 and taking the floor value to ensure it is managed in iterations. 6. **Output the Result:** -
Transcribed Image Text:### Algorithm for Computing g^A (mod N) **Problem Statement:** Given three positive integers \( N \), \( g \), and \( A \) (where \( N \) is not necessarily a prime number), prove that the following algorithm, a low-storage variant of the square-and-multiply algorithm, computes \( g^A \mod N \). **Algorithm:** 1. **Initialization:** - Set \( a = g \) - Set \( b = 1 \) 2. **Loop Condition:** - Repeat while \( A > 0 \) 3. **Steps Inside the Loop:** - If \( A \equiv 1 \mod 2 \) (i.e., if \( A \) is odd) - Set \( b = b \cdot a \mod N \) - Set \( a = a^2 \mod N \) - Update \( A = \left\lfloor \frac{A}{2} \right\rfloor \) (i.e., divide \( A \) by 2 and round down to the nearest integer) - Continue the loop while \( A > 0 \) 4. **Termination:** - When the loop exits, return \( b \), which equals \( g^A \mod N \) **Detailed Explanation of the Algorithm:** The algorithm is designed to efficiently compute the modular exponentiation \( g^A \mod N \) using a low-storage approach. Here's how each step works: 1. **Initialization:** - Begin with `a` set to `g` and `b` set to `1`. 2. **Loop Condition & Process:** - Continue looping as long as \( A \) is greater than 0. 3. **Checking If \( A \) is Odd:** - If \( A \) is odd (remainder of \( A \) divided by 2 is 1), update `b` using multiplication followed by taking modulo \( N \). 4. **Square and Reduce `a`:** - Square `a` and take modulo \( N \) to keep the number manageable in size. 5. **Divide and Floor `A`:** - Update `A` by dividing it by 2 and taking the floor value to ensure it is managed in iterations. 6. **Output the Result:** -
### 1.3.2 The Fast Powering Algorithm In some cryptosystems that we will study, for example the RSA and Diffie–Hellman cryptosystems, Alice and Bob are required to compute large powers of a number \( g \) modulo another number \( N \), where \( N \) may have hundreds of digits. The naive way to compute \( g^A \) is by repeated multiplication by \( g \). Thus \[ g_1 \equiv g \pmod{N}, \] \[ g_2 \equiv g \cdot g_1 \pmod{N}, \] \[ g_3 \equiv g \cdot g_2 \pmod{N}, \] \[ g_4 \equiv g \cdot g_3 \pmod{N}, \] \[ g_5 \equiv g \cdot g_4 \pmod{N}, \ldots \] It is clear that \( g_A \equiv g^A \pmod{N} \), but if \( A \) is large, this algorithm is completely impractical. For example, if \( A \approx 2^{1000} \), then the naive algorithm would take longer than the estimated age of the universe! Clearly, if it is to be useful, we need to find a better way to compute \( g^A \pmod{N} \). The idea is to use the binary expansion of the exponent \( A \) to convert the calculation of \( g^A \) into a succession of squarings and multiplications. An example will make the idea clear, after which we give a formal description of the method.
Transcribed Image Text:### 1.3.2 The Fast Powering Algorithm In some cryptosystems that we will study, for example the RSA and Diffie–Hellman cryptosystems, Alice and Bob are required to compute large powers of a number \( g \) modulo another number \( N \), where \( N \) may have hundreds of digits. The naive way to compute \( g^A \) is by repeated multiplication by \( g \). Thus \[ g_1 \equiv g \pmod{N}, \] \[ g_2 \equiv g \cdot g_1 \pmod{N}, \] \[ g_3 \equiv g \cdot g_2 \pmod{N}, \] \[ g_4 \equiv g \cdot g_3 \pmod{N}, \] \[ g_5 \equiv g \cdot g_4 \pmod{N}, \ldots \] It is clear that \( g_A \equiv g^A \pmod{N} \), but if \( A \) is large, this algorithm is completely impractical. For example, if \( A \approx 2^{1000} \), then the naive algorithm would take longer than the estimated age of the universe! Clearly, if it is to be useful, we need to find a better way to compute \( g^A \pmod{N} \). The idea is to use the binary expansion of the exponent \( A \) to convert the calculation of \( g^A \) into a succession of squarings and multiplications. An example will make the idea clear, after which we give a formal description of the method.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 3 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,
SEE MORE TEXTBOOKS