Exercise 9.3.18. Show that 341 is a pseudoprime base 2 but not a pseu- doprime base 3.
Exercise 9.3.18. Show that 341 is a pseudoprime base 2 but not a pseu- doprime base 3.
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
Please do Exercise 9.3.18 and please show step by step and explain
![Let n be an odd composite number and b be a positive integer such that
ged(b, n) = 1. If bn-1 = 1 (mod n), then n is a pseudoprime base b. We
can get a more accurate test for the primality of n if we test n versus a
294
CHAPTER 9 INTRODUCTION TO CRYPTOGRAPHY
number of prime bases. If n is a pseudoprime for several prime bases, then
we can say with high confidence that n is most probably a prime.
Exercise 9.3.18. Show that 341 is a pseudoprime base 2 but not a pseu-
doprime base 3.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F892e817a-9b32-4eeb-b8fc-5dd7ffde6479%2F6d420251-85e1-436e-bb0c-371eda43c74a%2Fk99x4ir_processed.png&w=3840&q=75)
Transcribed Image Text:Let n be an odd composite number and b be a positive integer such that
ged(b, n) = 1. If bn-1 = 1 (mod n), then n is a pseudoprime base b. We
can get a more accurate test for the primality of n if we test n versus a
294
CHAPTER 9 INTRODUCTION TO CRYPTOGRAPHY
number of prime bases. If n is a pseudoprime for several prime bases, then
we can say with high confidence that n is most probably a prime.
Exercise 9.3.18. Show that 341 is a pseudoprime base 2 but not a pseu-
doprime base 3.
![Probabilistic methods using the "little Fermat theorem"
In practice, neither the brute force nor the Fermat method is used to verify
large prime numbers. Instead, probabilistic methods are used: these methods
can show that it's very, very likely that n is a prime, but they don't prove
for certain. The principal test of this type is the Miller-Rabin test for
primality. This test uses some of the principles described below.
In Exercise 18.3.15 in Section 18.3.2, we will prove the following fact
(which is widely known as Fermat's little theorem):
If p is any prime number and a is any nonzero integer, then a²-1 = 1
(mod p).
We can use Fermat's little theorem as a screening test for primes. For
example, 15 cannot be prime since
215-12¹44 (mod 15).
However, 17 is a potential prime since
217-12161 (mod 17).
We say that an odd composite number n is a pseudoprime if
2-1 (mod n).](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F892e817a-9b32-4eeb-b8fc-5dd7ffde6479%2F6d420251-85e1-436e-bb0c-371eda43c74a%2Fx7pesxj_processed.png&w=3840&q=75)
Transcribed Image Text:Probabilistic methods using the "little Fermat theorem"
In practice, neither the brute force nor the Fermat method is used to verify
large prime numbers. Instead, probabilistic methods are used: these methods
can show that it's very, very likely that n is a prime, but they don't prove
for certain. The principal test of this type is the Miller-Rabin test for
primality. This test uses some of the principles described below.
In Exercise 18.3.15 in Section 18.3.2, we will prove the following fact
(which is widely known as Fermat's little theorem):
If p is any prime number and a is any nonzero integer, then a²-1 = 1
(mod p).
We can use Fermat's little theorem as a screening test for primes. For
example, 15 cannot be prime since
215-12¹44 (mod 15).
However, 17 is a potential prime since
217-12161 (mod 17).
We say that an odd composite number n is a pseudoprime if
2-1 (mod n).
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Recommended textbooks for you
![Advanced Engineering Mathematics](https://www.bartleby.com/isbn_cover_images/9780470458365/9780470458365_smallCoverImage.gif)
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
![Numerical Methods for Engineers](https://www.bartleby.com/isbn_cover_images/9780073397924/9780073397924_smallCoverImage.gif)
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…](https://www.bartleby.com/isbn_cover_images/9781118141809/9781118141809_smallCoverImage.gif)
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
![Advanced Engineering Mathematics](https://www.bartleby.com/isbn_cover_images/9780470458365/9780470458365_smallCoverImage.gif)
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
![Numerical Methods for Engineers](https://www.bartleby.com/isbn_cover_images/9780073397924/9780073397924_smallCoverImage.gif)
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…](https://www.bartleby.com/isbn_cover_images/9781118141809/9781118141809_smallCoverImage.gif)
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
![Mathematics For Machine Technology](https://www.bartleby.com/isbn_cover_images/9781337798310/9781337798310_smallCoverImage.jpg)
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
![Basic Technical Mathematics](https://www.bartleby.com/isbn_cover_images/9780134437705/9780134437705_smallCoverImage.gif)
![Topology](https://www.bartleby.com/isbn_cover_images/9780134689517/9780134689517_smallCoverImage.gif)