Great explanation! Just a minor objection: The difficulty is not due to the infinite number of solutions (as suggested at 5:00). The main challenge lies in the computational effort required to find even the smallest such x, when p is a very large prime.
You should also mention what makes the discrete logarithm problem any useful than normal modulo problem. Such as x mod 35. x = 52 and x = 857 and infinitely many x values would yield 17. So let me tell the part that makes using power important. The base (b) and the modulo (m) are known publicly and your secret is the powering integer x. Bob chooses a secret x and sends p = b^x mod m to Alice. Alice also knows the public values b and m and chooses her secret integer y. Then she does two things, 1) sends q = b^y mod m to Bob 2) Calculates s = (p^y) mod m. Bob receives q from Alice and calculates s = (q^x) mod m. Now both Alice and Bob share the same secret s to establish an encryptided commumination by relying on it. Anybody who sees the public values b, m, p, q is not able to calculate s easily without knowing x or y. For example Bob choses x = 8 and sends Alice 5^8 mod 17 = 16. Alice chooses y = 13 and sends Bob 5^13 mod 17 = 3. Bob receives 3 from Alice and calculates (3^8) mod 17 = 16. Alice receives 16 from Bob and calculates (16^13) mod 17 = 16. So now they both know that their secret key is 16.
Beautiful, thank you. 5^x mod 17 produces all 16 integers less than 17. But what about 16^x mod 17? 16 is relatively prime to 17 (a prime), but [16^x mod 17] has members that are not. This yields a [1,16,1,16,...] pattern. In fact, bases 2, 4, 8, 9, 13, 15 , and 16 all result in 'short' cycles (Some numbers between 1 and 16 are not output). Doesn't this severely impact the solutions space ?
5:40 Your explanation is faulty. It is hard to find x in 5^x = 12, not because there are multiple satisfying values in the congruence class. That is NOT what makes the problem hard. Problem is hard because you would have to look at all values between 1 and 16 to find the one that works.
Like really really crappy rehydrated coffee not actual real drip coffee lol. Nevertheless thank you for your excellent explanations as usual. But for hardcore serious coffee drinkers this isabsolutely not how to make coffee. Lol. Most hardcore coffe drinkers think of instant coffee as basically a sin against nature haha
First time someone explained this in a way that is understandable to me.
Great explanation! Just a minor objection: The difficulty is not due to the infinite number of solutions (as suggested at 5:00). The main challenge lies in the computational effort required to find even the smallest such x, when p is a very large prime.
You should also mention what makes the discrete logarithm problem any useful than normal modulo problem. Such as x mod 35. x = 52 and x = 857 and infinitely many x values would yield 17. So let me tell the part that makes using power important. The base (b) and the modulo (m) are known publicly and your secret is the powering integer x. Bob chooses a secret x and sends p = b^x mod m to Alice. Alice also knows the public values b and m and chooses her secret integer y. Then she does two things, 1) sends q = b^y mod m to Bob 2) Calculates s = (p^y) mod m. Bob receives q from Alice and calculates s = (q^x) mod m. Now both Alice and Bob share the same secret s to establish an encryptided commumination by relying on it. Anybody who sees the public values b, m, p, q is not able to calculate s easily without knowing x or y. For example Bob choses x = 8 and sends Alice 5^8 mod 17 = 16. Alice chooses y = 13 and sends Bob 5^13 mod 17 = 3. Bob receives 3 from Alice and calculates (3^8) mod 17 = 16. Alice receives 16 from Bob and calculates (16^13) mod 17 = 16. So now they both know that their secret key is 16.
Dear sir, this is an excellent way to understand. We request you to give clear and short notes for this (with respect to student aspect ).
thanks you neso academy you're the best
Can not wait for the next lecture.
Very great explanation
2 is not a prime generator of 7 tho
Very nicely explained. Thank you!
For making coffee we don't obviously need milk
damn good, finally it's crystal clear
Beautiful, thank you. 5^x mod 17 produces all 16 integers less than 17. But what about 16^x mod 17? 16 is relatively prime to 17 (a prime), but [16^x mod 17] has members that are not. This yields a [1,16,1,16,...] pattern. In fact, bases 2, 4, 8, 9, 13, 15 , and 16 all result in 'short' cycles (Some numbers between 1 and 16 are not output). Doesn't this severely impact the solutions space ?
please put PPT'S for C Programming
beautiful explanation but coffe isn't made with milk Bruh
5:40 Your explanation is faulty.
It is hard to find x in 5^x = 12, not because there are multiple satisfying values in the congruence class.
That is NOT what makes the problem hard.
Problem is hard because you would have to look at all values between 1 and 16 to find the one that works.
mam excellent explanation,Thank you very much Hare Krishna
What a chad!!
❤️❤️❤️❤️❤️
Like really really crappy rehydrated coffee not actual real drip coffee lol. Nevertheless thank you for your excellent explanations as usual. But for hardcore serious coffee drinkers this isabsolutely not how to make coffee. Lol. Most hardcore coffe drinkers think of instant coffee as basically a sin against nature haha