Julio Albuja At 3:25, I was referring to the alpha and beta calculation when I said "both numbers." Specifically, find 12^(40/2) = ?? mod 41 AND find (7^(40/2))^(Xo) = ? mod 41. Then I compared them on the next line. Does that answer you question?
There is a small mistake in the presentaion, where you find x2, when q=2 your beta2 should be beta1*alpha^-(2*x1). Since here x1 is 0, it doesn't make any change in the final answer.
I actually was about to post it now. The implementation gave error for large values. Had to figure it out from www-math.ucdenver.edu/~wcherowi/courses/m5410/phexam.html
Hi, there's a few ways to do inverse numbers. What I did was this: 7^(-1) is 1/7 and 1/7 mod 41 = x (x is the whole number we're trying to find) Do a little algebra and get 1 mod 41= 7x We also know that 42 = 1 mod 41 So 42 = 7x Then x = 42/7 = 6 Hence 7^(-1) = 6 mod 41
I'm confused as to how you got -1(mod 41) = (-1)^x0(mod 41) ? Could you please help me with this step? When I take 12^(40/2) = 12^(20) (mod 41) I get 18. Where does the -1 come from?
fermats little theorem provides for a^(p-1) == 1 (mod p). Now for an unknown `x`, a^x == -1 (mod p) will give x = (p-1)/2. This can be proved by squaring both sides of the equation a^x == -1 (mod p). Implies, a^2x == 1 (mod p). Again using fermat's theorem, 2x == p-1 or x = (p-1)/2
+M Hk198 I'm sorry to say I honestly don't remember where it comes from, other than that it is simply part of the formula used to calculate betas. The formula for calculating any given beta is the following (and I used just "sub(x)" meaning "subscript x"): Bsub(j+1) = [Bsub(j)]*[Alpha^(-Xsub(j)*q^j)] ...the negative in front of the X is the one I believe you are referring to.
Thanks for the video it's so helpfull for me. But a have question, ıf the mod number not a prime I mean what if for example it gives us mod(5×17=85) Still do we do the same procedure?
+burcu sunturlu As a general rule, when computing discrete logs (such as with the Pohlig-Hellman algorithm), the mod will not be prime. The mod will be primes multiplied together. But regardless, yes--it should be the same procedure. In your example though (p=85), you would want to factor 85-1 = 84 = 2*2*21. However, I'm not sure I understood your question; if not feel free to ask again.
+Theoretically The example ı gave mod 85 85-1=84=2*2*3*7 ı mean first we do pohlig hellman algorithm and we do Chinesee remainder theorem for 3 equation Is this true?
Bcoz 7^20=40mod41 , which can be written as 7^20=-1mod41( as subtracting 40 or adding -1 makes the 7^20 divisible by 41),we use -1 to make it look less weird
Julio Albuja At 3:25, I was referring to the alpha and beta calculation when I said "both numbers." Specifically, find 12^(40/2) = ?? mod 41 AND find (7^(40/2))^(Xo) = ? mod 41. Then I compared them on the next line. Does that answer you question?
There is a small mistake in the presentaion, where you find x2, when q=2 your beta2 should be beta1*alpha^-(2*x1). Since here x1 is 0, it doesn't make any change in the final answer.
Good catch Safeer KM , thanks.
I added an annotation to note this in the video.
Where does this "2" come from? What is the equation for this coeffcient? What if we had 2^4 instead of 2^3 ? What would be coefficient then?
I actually was about to post it now. The implementation gave error for large values. Had to figure it out from www-math.ucdenver.edu/~wcherowi/courses/m5410/phexam.html
Thank you for doing this, helped me understand the algorithm :)
So glad!
My notes say that B2 = B1(alpha)^(-x1 * q). Is the power mislabeled in this video?
Your explanation helped a lot. Thank you very much
Why q1 = 2^2 at time 5:29?
pleasant voice to listen to, helpful & i like the way u explain..
but can i solve a CRT-Eq-System with 3 or more equations, the same way like u did ?
Interesting, but since minute 3:25, what do you mean calculate both numbers?
Thank you, this saved me so much time!
4:54 - how do you calculate (7)^-1 ???
Hi, there's a few ways to do inverse numbers. What I did was this:
7^(-1) is 1/7
and 1/7 mod 41 = x (x is the whole number we're trying to find)
Do a little algebra and get 1 mod 41= 7x
We also know that 42 = 1 mod 41
So 42 = 7x
Then x = 42/7 = 6
Hence 7^(-1) = 6 mod 41
How about when you get a beta different from 1 or -1? Like how about 101 (mod 353) = -1 ^ x (mod 353)?
Are you still reading this? I have an important question!
I'm confused as to how you got -1(mod 41) = (-1)^x0(mod 41) ? Could you please help me with this step? When I take 12^(40/2) = 12^(20) (mod 41) I get 18. Where does the -1 come from?
fermats little theorem provides for a^(p-1) == 1 (mod p). Now for an unknown `x`, a^x == -1 (mod p) will give x = (p-1)/2. This can be proved by squaring both sides of the equation a^x == -1 (mod p). Implies, a^2x == 1 (mod p). Again using fermat's theorem, 2x == p-1 or x = (p-1)/2
Where does the negative sign comes from in power of alpha when finding Beta 1 and Beta 2, Will highly appreciate the explanation
+M Hk198 I'm sorry to say I honestly don't remember where it comes from, other than that it is simply part of the formula used to calculate betas. The formula for calculating any given beta is the following (and I used just "sub(x)" meaning "subscript x"):
Bsub(j+1) = [Bsub(j)]*[Alpha^(-Xsub(j)*q^j)]
...the negative in front of the X is the one I believe you are referring to.
+M Hk198 Also, this link may or may not help:
anh.cs.luc.edu/331/notes/PohligHellmanp_k2p.pdf
+Theoretically Thanks a lot for the explanation and a link.
Thanks for the video it's so helpfull for me. But a have question, ıf the mod number not a prime I mean what if for example it gives us mod(5×17=85)
Still do we do the same procedure?
+burcu sunturlu As a general rule, when computing discrete logs (such as with the Pohlig-Hellman algorithm), the mod will not be prime. The mod will be primes multiplied together. But regardless, yes--it should be the same procedure. In your example though (p=85), you would want to factor 85-1 = 84 = 2*2*21.
However, I'm not sure I understood your question; if not feel free to ask again.
+Theoretically Now ı understand better with your answer, thanks a lot..
+Theoretically The example ı gave mod 85
85-1=84=2*2*3*7
ı mean first we do pohlig hellman algorithm and we do Chinesee remainder theorem for 3 equation
Is this true?
how did you calculated the valueof x0 = -1 mod 41
Bcoz 7^20=40mod41 , which can be written as 7^20=-1mod41( as subtracting 40 or adding -1 makes the 7^20 divisible by 41),we use -1 to make it look less weird
Are you working in NASA ryt now?
(Y) Understood completely, thanks :)
Narendra Singh So glad!
Thanks!