Re: [go-nuts] Math.big issue

[Rémy Oudompheng]

Hello,

Fermat's little theorem says that 1111^5146 mod 5147 is 1

so similarly 1111^(5146+5146) mod 5147 is also 1.

Therefore it is correct that 1111^(5146+5147) mod 5147 is 1111.

If you have a large exponent, you should reduce it modulo (p-1) to keep the same result.

Regards,

Rémy.

Le dim. 11 juil. 2021 à 12:13, Paolo C. <paoc...@gmail.com> a écrit :

I think there is something wrong in big.Int Exp method.

This code:

func TestExp(t *testing.T) { 

   p := big.NewInt(5147) 

   ab = big.NewInt(5146 + 5147) 

   t.Logf("ab=%d", ab) 

   ab.Mod(ab, p) 

   t.Logf("ab=%d", ab) 

   c := big.NewInt(1111) 

   c_pow_ab := new(big.Int).Exp(c, ab, p) 

   t.Logf("c_pow_ab=%d", c_pow_ab)

}

and this code

func TestExp(t *testing.T) { 

   p := big.NewInt(5147) 

   ab = big.NewInt(5146 + 5147) 

   t.Logf("ab=%d", ab) 

   // ab.Mod(ab, p) 

   t.Logf("ab=%d", ab) 

   c := big.NewInt(1111) 

   c_pow_ab := new(big.Int).Exp(c, ab, p) 

   t.Logf("c_pow_ab=%d", c_pow_ab)

}

should both return give "1" as result of the exponentiation.

The second snippet gives "1111".

In general, not "moduling" the exponent before entering EXP seems to return "one more power" of the base for each "order" addition, that should instead be a don't care.

The base of the exponentiation seems not to suffer the problem.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/e42c4674-6dd7-478d-ab86-1725c571a753n%40googlegroups.com.