MOD calculation / reversing

[raduga_fb]

Thank you Bilbo for reply & effort. Please look following code.

For our situation, "m", "a" and "b" are known. "b" is equal to (2*m+1)/9

I do not have the "gmp library" at the moment. I'll try to install it today :-)

Just I am wondering about that, the numbers a, b, m have 128 bytes length. Can GMP handle it (result r should be in 128 bytes length also) ? In case YES, I think I found the solution.

Did you read something about "Tonelli-Shanks algorithm" ? The solution is modified version of it :-) Look at the bottom where I took the trick from..



int main()
{
mpz_t a, b, m, r;

mpz_init_set_str(a, "5072", 0);
mpz_init_set_str(b, "2243", 0);
mpz_init_set_str(m, "10093", 0);

mpz_init(r);
mpz_powm(r, a, b, m);

gmp_printf("%Zd\n", r); /* r = 777 */

mpz_clear(a);
mpz_clear(b);
mpz_clear(m);
mpz_clear(r);

return 0;






#include <gmp.h>

int main()
{
mpz_t a, b, m, r;

mpz_init_set_str(a, "2988348162058574136915891421498819466320"
"163312926952423791023078876139", 0);
mpz_init_set_str(b, "2351399303373464486466122544523690094744"
"975233415544072992656881240319", 0);
mpz_init(m);
mpz_ui_pow_ui(m, 10, 40);

mpz_init(r);
mpz_powm(r, a, b, m);

gmp_printf("%Zd\n", r); /* ...16808958343740453059 */

mpz_clear(a);
mpz_clear(b);
mpz_clear(m);
mpz_clear(r);

return 0;
}





#assumes p prime returns cube root of a mod p
def cuberoot(a, p):
if p == 2:
return a
if p == 3:
return a
if (p%3) == 2:
return pow(a,(2*p - 1)/3, p)
if (p%9) == 4:
root = pow(a,(2*p + 1)/9, p)
if pow(root,3,p) == a%p:
return root
else:
return None
if (p%9) == 7:
root = pow(a,(p + 2)/9, p)
if pow(root,3,p) == a%p:
return root
else:
return None
else:
print "Not implemented yet. See the second paper"

[bilbo]

I'll have a look to the algorithm you said.

GMP can handle every size and can be used with gcc (MINGW on Windows). If you want to use Visual Studio, grab MPIR, which is perfectly compatible with GMP.

Best regards
bilbo