In many cryptographic applications the Modular Inverse is a key operation. This programming problem involves finding the modular inverse of a number. Given 0

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

Pls help and code in java!!!! Thank you so much!

### Understanding and Finding the Modular Inverse

In many cryptographic applications, the Modular Inverse is a key operation. This programming problem involves finding the modular inverse of a number.

#### Definition

Given \(0 < x < m\), where x and m are integers, the modular inverse of x is the unique integer n, \(0 < n < m\), such that the remainder upon dividing \(x \times n\) by m is 1. That is,

\[x \times n \mod m = 1\]

The modular inverse is a concept that extends the arithmetic inverse. For example, the inverse of 2 is \( \frac{1}{2} \) because \( 2 \times \frac{1}{2} = 1 \) with decimal operation. Here the inverse number can be a fraction.

In modular inverse, we only allow integers, no fractions. So not all integers have an inverse.

#### Examples

- For example, \(m = 26, x = 3\): The modular inverse of 3 is 9 because \(3 \times 9 \mod 26 = 1\).
- However, \(m = 26, x = 2\): The modular inverse of 2 does not exist because you cannot find a number y so that \(2 \times y \mod 26 = 1\).
- Another example, \(m = 17, x = 4\): \(4 \times 13 = 52\). \(52 \mod 17 = 1\), so the remainder when 52 is divided by 17 is 1, and thus 13 is the inverse of 4 modulo 17.

#### Problem Statement

You are to write a method `modularInverse()` which accepts as input the two integers x and m, and outputs either the modular inverse n, or -1 to indicate "No such integer exists" if there is no such integer n.

You may assume that \(m \leq 100\), x and m are non-negative.

#### Example Code

```java
public class ModInverse {

    public static void main(String[] args) {
        int m = 26;

        for (int x = 0; x < m; x++) {
            int n = modularInverse(x, m);

            if (n == -1) {
                System.out.println("The modular inverse of x " + x +
Transcribed Image Text:### Understanding and Finding the Modular Inverse In many cryptographic applications, the Modular Inverse is a key operation. This programming problem involves finding the modular inverse of a number. #### Definition Given \(0 < x < m\), where x and m are integers, the modular inverse of x is the unique integer n, \(0 < n < m\), such that the remainder upon dividing \(x \times n\) by m is 1. That is, \[x \times n \mod m = 1\] The modular inverse is a concept that extends the arithmetic inverse. For example, the inverse of 2 is \( \frac{1}{2} \) because \( 2 \times \frac{1}{2} = 1 \) with decimal operation. Here the inverse number can be a fraction. In modular inverse, we only allow integers, no fractions. So not all integers have an inverse. #### Examples - For example, \(m = 26, x = 3\): The modular inverse of 3 is 9 because \(3 \times 9 \mod 26 = 1\). - However, \(m = 26, x = 2\): The modular inverse of 2 does not exist because you cannot find a number y so that \(2 \times y \mod 26 = 1\). - Another example, \(m = 17, x = 4\): \(4 \times 13 = 52\). \(52 \mod 17 = 1\), so the remainder when 52 is divided by 17 is 1, and thus 13 is the inverse of 4 modulo 17. #### Problem Statement You are to write a method `modularInverse()` which accepts as input the two integers x and m, and outputs either the modular inverse n, or -1 to indicate "No such integer exists" if there is no such integer n. You may assume that \(m \leq 100\), x and m are non-negative. #### Example Code ```java public class ModInverse { public static void main(String[] args) { int m = 26; for (int x = 0; x < m; x++) { int n = modularInverse(x, m); if (n == -1) { System.out.println("The modular inverse of x " + x +
Expert Solution
steps

Step by step

Solved in 4 steps with 2 images

Blurred answer
Knowledge Booster
Encryption and decryption
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education