Login Registrieren

Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Algorithms

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani

Computer Science

1st Edition · 333 pages

ISBN: 9780073523408

Chapter 1: Q28E (page 49)

In an RSA cryptosystem, p = 7and q = 11(as in Figure 1.9). Find appropriate exponents and .

Short Answer

Expert verified

The correct exponent of d is 37 and e is 13.

Step by step solution

01

Introduction

RSA cryptosystem are asymmetric cryptography algorithm in which it contains public as well as private key. By the use of both the keys data get more secured and for decryption public can be visible to everyone but private key is shared with the authorized user secretly.

02

Find the value of

We have given that, p = 7 , q = 11 , n = $p \times q,$

Then

$n = 7 \times 11 = 77$

Now, find $ϕ (n) = (p - 1) \times (q - 1)$ .

$ϕ (n) = (p - 1) \times (q - 1) = (7 - 1) \times (11 - 1) = 6 \times 10 = 60$

Let’s, assume e as private key, such that

$(e \times d) modphi (n) = 1$

The value of e is 13 as it is the next prime number after 11

So,

$(13 \times d) \mod 60 = 1 d = 37$

The correct exponent of d is 37 and e is 13.

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

1.38. To see if a number, say $562437487$ , is divisible by $3$ , you just add up the digits of its decimalrepresentation, and see if the result is divisible by role="math" localid="1658402816137" $3$ .

( $5 + 6 + 2 + 4 + 3 + 7 + 4 + 8 + 7 = 46$ , so it is not divisible by $3$ ).

To see if the same number is divisible by $11$ , you can do this: subdivide the number into pairs ofdigits, from the right-hand end $(87, 74, 43, 62, 5)$ , add these numbers and see if the sum is divisible by $11$ (if it's too big, repeat).

How about $37$ ? To see if the number is divisible by $37$ , subdivide it into triples from the end $(487, 437, 562)$ add these up, and see if the sum is divisible by $37$ .

This is true for any prime $p$ other than $2$ and $5$ . That is, for any prime $p≠2,5$ , there is an integer $r$ such that in order to see if $p$ divides a decimal number $n$ , we break $n$ into $r$ -tuples of decimal digits (starting from the right-hand end), add up these $r$ -tuples, and check if the sum is divisible by $p$ .

(a) What is the smallest $r$ such for $p=13$ ? For $p=13$ ?

(b) Show that $r$ is a divisor of $p-1$ .

Let $[m]$ denote the set ${0, 1, \dots, m - 1}$ . For each of the following families of hash functions, say whether or not it is universal, and determine how many random bits are needed to choose a function from the family.

(a) $H = {h_{a_{1}, a_{2}} : a_{1}, a_{2} \in [m]}$ , where $m$ is a fixed prime and

$h_{a_{1}} \cdot h_{a_{1}, a_{2}} (x_{1}, x_{2}) = a_{1} x_{1} + a_{2} x_{2} m o d m$

Notice that each of these functions has signature $h_{a_{1}, a_{2}} : {[m]}^{2} \to [m]$ that is, it maps a pair of integers in $[m]$ to a single integer in $[m]$ .

(b) $H$ is as before, except that now $m = 2^{k}$ is some fixed power of. $2$

(c) $H$ is the set of all functions $f : [m] \to [m - 1]$ .

Show that if $x$ is a nontrivial square root of 1 modulo N , that is if $x^{2} \equiv 1 \mod N$ but $x \neq \pm 1 \mod N$ , then $N$ must be composite. (For instance, $4^{2} \equiv 1 \mod 15 but 4 ≢ \pm 1 \mod 15$ ; thus 4 is a nontrivial square root of 1 modulo 15.)

Show that $\log (n!) = θ (nlogn)$

(Hint: To show an upper bound, compare $(n!)$ with $n^{n}$ . To show a lower bound, compare it with ${(\frac{n}{2})}^{\frac{n}{2}}$ ).

Show that any binary integer is at most four times as long as the corresponding decimal integer. For very large numbers, what is the ratio of these two lengths, approximately?

See all solutions

Recommended explanations on Computer Science Textbooks

Problem Solving Techniques

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Organisation and Architecture

Read Explanation

Big Data

Read Explanation

Functional Programming

Read Explanation

Data Representation in Computer Science

Read Explanation

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free