Re: Congruence with division

"Ulrich Sondermann" <usondermann@xxxxxxxxxxxxx> writes:

> I'm trying to break down a computing problem. I have a number to raise to a
> power and take the modulus of. If I can make the exponent a power of 2 then
> the mod problem is an easy one regardless of size. Here is a simple problem
> but in my case the numbers are quite large.
>
> 3^13 = 3 mod(7), I would like to make this (3^16)/(3^3) Buy computing the
> numerator and denominator separately to simplify the problem.
>
> but 3^16 = 4 mod(7) and 3^3 = 6 mod(7)

So where is the problem? The inverse of 6 is 6, and 24 mod 7 is 3.

And since 3^13 is the same as 3^(13 mod psi(7)) = 3^(13 mod 6) = 3,
this result is fine.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
.

Relevant Pages

  • Re: Congruence with division
    ... >> I'm trying to break down a computing problem. ... I have a number to raise to a ... If I can make the exponent a power of 2 then ... There is no problem in this example because the modulus is prime. ...
    (sci.math)
  • Congruence with division
    ... I'm trying to break down a computing problem. ... I have a number to raise to a ... power and take the modulus of. ... If I can make the exponent a power of 2 then ...
    (sci.math)
  • Re: Congruence with division
    ... If I can make the exponent a power of 2 then ... the fastest piece of software out there) will allow you to raise one ... hundred digit number by another hundred digit number mod a third ...
    (sci.math)
  • Re: Irrational numbers questions
    ... which means what power "a" must I raise the number ... Han de Bruijn ...
    (sci.math)
  • Re: factorial and exponent
    ... It will enable you to do "Arithmetic without Limitations"!! ... Raise A to the power B, storing the result in A. Now raise B to the ...
    (comp.lang.c)