hey guys :D
I have this small math problem,
( a * b ) mod n = 1
Given a, n:
find the smallest value of 'b' that satisfies the equation above.
any Idea about how to find the answer better than linear time search.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
hey guys :D
I have this small math problem,
( a * b ) mod n = 1
Given a, n:
find the smallest value of 'b' that satisfies the equation above.
any Idea about how to find the answer better than linear time search.
Name |
---|
http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
this is the same as finding the inverse of A (mod C) right ??
Yes, it's the same. Wikipedia article has some examples.
one more question please, who to choose the proper values for a, n
ikatanic any constraints on values other than 'a' and 'n' should be co primes ??
Nope. Extended Euclidean algorithm is used to solve the equation Ax+By=GCD(A,B) and since GCD(a,n)=1 the equation a*b-k*n=1=GCD(a,n) has infinitely many solutions.
But I found this statement on some website:
"Only the numbers coprime to C (numbers that share no prime factors with C) have a modular inverse (mod C)"
this is for the formula above in my post.
You are not right. GCD(a, n) must be equal to 1, otherwise it has no solution. You can read here
He knows that, I just said that there is not another constraint.
(a*b) mod n = 1 means that (a*b) = k*n+1 for some integer k>=0.
a*b-k*n = 1 is an equation of the form Ax+By=C which can be solved using Extended Euclidean algorithm.
Update: When I started writing my comment I didn't see that ikatanic has commented, sorry :)
P_Nyagolov thank you and ikatanic :D