Homework Help is Here – Start Your Trial Now!
Math
Advanced Math
2.3. Let g be a primitive root for Fp. (a) Suppose that x = a and x = b are both integer solutions to the congruence g = h (mod p). Prove that a = b (mod p - 1). Explain why this implies that the map (2.1) on page 65 is well-defined.

2.3. Let g be a primitive root for Fp. (a) Suppose that x = a and x = b are both integer solutions to the congruence g = h (mod p). Prove that a = b (mod p - 1). Explain why this implies that the map (2.1) on page 65 is well-defined.

Advanced Engineering Mathematics
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
See similar textbooks
icon
Related questions
Question

[Algebraic Cryptography] How do you solve this?

2.3. Let g be a primitive root for Fp. (a) Suppose that x = a and x = b are both integer solutions to the congruence g¹ = h (mod p). Prove that a = b (mod p − 1). Explain why this implies that the map (2.1) on page 65 is well-defined. -
Transcribed Image Text:2.3. Let g be a primitive root for Fp. (a) Suppose that x = a and x = b are both integer solutions to the congruence g¹ = h (mod p). Prove that a = b (mod p − 1). Explain why this implies that the map (2.1) on page 65 is well-defined. -
Remark 2.2. The discrete logarithm problem is a well-posed problem, namely to find an integer exponent à such that g = h. However, if there is one so- lution, then there are infinitely many, because Fermat's little theorem (The- orem 1.24) tells us that gº−¹ = 1 (mod p). Hence if x is a solution to gª = h, then x + k(p − 1) is also a solution for every value of k, because gæ+k(p-1) = g. −1)k = h. 1² = h (mod p). Thus logg (h) is defined only up to adding or subtracting multiples of p - 1. In other words, logg (h) is really defined modulo p – 1. It is not hard to verify (Exercise 2.3(a)) that log, gives a well-defined function logg : F* P Z (p − 1)Z (2.1)
Transcribed Image Text:Remark 2.2. The discrete logarithm problem is a well-posed problem, namely to find an integer exponent à such that g = h. However, if there is one so- lution, then there are infinitely many, because Fermat's little theorem (The- orem 1.24) tells us that gº−¹ = 1 (mod p). Hence if x is a solution to gª = h, then x + k(p − 1) is also a solution for every value of k, because gæ+k(p-1) = g. −1)k = h. 1² = h (mod p). Thus logg (h) is defined only up to adding or subtracting multiples of p - 1. In other words, logg (h) is really defined modulo p – 1. It is not hard to verify (Exercise 2.3(a)) that log, gives a well-defined function logg : F* P Z (p − 1)Z (2.1)
Expert Solution
steps

Step by step

Solved in 2 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
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…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,
SEE MORE TEXTBOOKS