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
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
1.3.2 also attached
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.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F5c5ad030-3ec8-4fd2-8d64-821b0d0d0877%2Ff774c1de-5c44-4fed-86d7-704dbb69c708%2F6h8feui_processed.png&w=3840&q=75)
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
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 3 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
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…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
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…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
