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"