Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 1: Q21E (page 49)

How many integers modulo113 have inverses?(Note:113=1331)

Short Answer

Expert verified

The number of integers coprime to113 are 1210

Step by step solution

01

Explain Inverse modulo

The modular multiplicative inverse can be defined as the GCD(a,b)must be equal to 1 and a, b are relatively prime.

02

Calculate the number of integers

Consider that the numbers1,11,121,1331 are the factors of 113. It is given that 113=1331, the number of integers can be calculated as follows,

113-1-112-1=1331-1-121-1=1330-120=1210

Therefore, The number of integers coprime to 113 are 1210

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

Starting from the definition of x≡ymodN(namely, that Ndivides x-y), justify the substitution rule x≡x'modN,y≡y'modNx+y≡x'+y'modN,and also the corresponding rule for multiplication.

1.36. Square roots. In this problem, we'll see that it is easy to compute square roots modulo a prime pwith p≡3(mod4).
(a) Suppose p≡3(mod4). Show that(p+1)/4 is an integer.
(b) We say x is a square root of a modulo p if a=x2(modp). Show that if p≡3(mod4)and if a has a square root modulo p, thena(p+1)/4 is such a square root.

Wilson's theorem says that a numberis prime if and only if
(N-1)!=-1(modN).

(a) If is prime, then we know every number1≤x<p is invertible modulo . Which of thesenumbers is their own inverse?
(b) By pairing up multiplicative inverses, show thatrole="math" localid="1658725109805" (p-1)!=-1(modp) for prime p.
(c) Show that if N is not prime, then(N-1)!≢(modN) .(Hint: Considerd=gcd(N,(N-1)!.)
(d) Unlike Fermat's Little Theorem, Wilson's theorem is an if-and-only-if condition for primality. Why can't we immediately base a primality test on this rule?

Give a polynomial-time algorithm for computing,abcmodp given a,b,c, and prime p.

Digital signatures, continued.Consider the signature scheme of Exercise 1.45.

(a) Signing involves decryption, and is therefore risky. Show that if Bob agrees to sign anything he is asked to, Eve can take advantage of this and decrypt any message sent by Alice to Bob.

(b) Suppose that Bob is more careful, and refuses to sign messages if their signatures look suspiciously like text. (We assume that a randomly chosen message−that is, a random number in the range{1,...,N-1} is very unlikely to look like text.) Describe a way in which Eve can nevertheless still decrypt messages from Alice to Bob, by getting Bob to sign messages whose signatures look random.
See all solutions

Recommended explanations on Computer Science Textbooks

Theory of Computation

Read Explanation

Computer Network

Read Explanation

Databases

Read Explanation

Computer Organisation and Architecture

Read Explanation

Problem Solving Techniques

Read Explanation

Algorithms 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