Re: Congruence with division


Ulrich Sondermann wrote:
> 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)
>
> TIA
> Ulie

Greetings,
The idea of first exponentiating and then taking mods is deeply
flawed. Instead, use a modular-exponentiation algorithm. Here is a
recursive approach to define a function pow(x,a,n) to compute x^a (mod
n):



pow(x,a,n) = { 1 if a = 0
x if a = 1
(pow(x,k,n)*pow(x,k,n)) mod n if a = 2k
(pow(x,k,n)*pow(x,k,n)*x) mod n if a = 2k+1

There are ways to put this in a loop (google "modular exponentiation"),
but even a straightforward implementation of the above in Derive (not
the fastest piece of software out there) will allow you to raise one
hundred digit number by another hundred digit number mod a third
hundred digit number in a small fraction of a second.

Hope that helps

-John Coleman

.

Relevant Pages

  • *** ADDENDUM: ALGORITHM DISCOVERED!!!! *** Re: Converting binary floating point numbers to decimal?
    ... appropriate power of ten to make it's magnitude less than ... This left-over digit then becomes the first of our ... The above is for a positive exponent, ... are handled much similar except we are multiplying, ...
    (sci.math)
  • Re: Prove that its dense!
    ... lies in [0,1). ... where c and d are integers, by adding any power of sqrt-1. ... raise the exponent on sqrt-1 to make the increment arbitrarily small. ...
    (sci.math)
  • Re: Prove that its dense!
    ... lies in [0,1). ... where c and d are integers, by adding any power of sqrt-1. ... raise the exponent on sqrt-1 to make the increment arbitrarily small. ...
    (sci.math)
  • Re: (2^n-1)(3^n-1) never a square ?
    ... Prime Expression for exponent of prime ... This means, m must contain an odd power of 2, such that is even. ... So the primefactor 5 does not give more restrictions on m. ...
    (sci.math)
  • Re: (2^n-1)(3^n-1) never a square ?
    ... Prime Expression for exponent of prime ... This means, m must contain an odd power of 2, such that is even. ... So the primefactor 5 does not give more restrictions on m. ...
    (sci.math)