MOD calculation / reversing

[bilbo]

hi raduga_fb,

your assertion

c = powmod(base, 3, mod), where: mod=10093 prime, c=5072

can be reverted as:

base = powmod(c, (2*mod + 1)/9, mod) = powmod(5072, 2243, 10093) = 777

holds only for few values of base!

The output of this program:

#include "gmp.h"

void
main(void)
{
	int ok=0, ko=0;
	int primemod = 10093;
	mpz_t base, mod, res1, res2;

	mpz_init(base);
	mpz_init(mod);
	mpz_init(res1);
	mpz_init(res2);

	mpz_set_ui(mod, primemod);

#if 0
	mpz_set_ui(base, 777);
#else
	for ( ; mpz_cmp_ui(base, 0xFFFFF)<=0; mpz_add_ui(base, base, 1))
#endif
	{
	mpz_powm_ui(res1, base, 3, mod);  // (a*a*a) % mod
	//gmp_printf("%Zd\n", res1);

	mpz_powm_ui(res2, res1, (2*primemod + 1)/9, mod);
	//gmp_printf("%Zd\n", res2);
	if (mpz_cmp(base, res2) == 0) ok++; else ko++;
	}

	gmp_printf("ok %d, ko %d\n", ok, ko);
}

is in fact
ok 3365, ko 1045211
for base in the range 0 - 0xFFFFF

So we need more constraints...

bilbo