lichess.org
Donate

calculate huge numbers with mod x?

For example, I have huge numbers

12345^(9876543211) + 67890^(1234567899) mod 34567

how to quickly calculate them down?

I know

  1. A +B mod C = [ (A mod C) + (B mod C) ] mod C

  2. A ^(B×C) mod D = {[(A^B) mod D] * [(A^C) mod D] } mod D

  3. A ^ B mod C = [(A mod C) ^ B] mod C

But, for example, must I try to devide large numbers down by just trying every prime number possible until I just happen to find the fitting one to reduce the exponent to a level my calculator manages?

The bases are usually ok, but reducing a large, not clearly divisable exponent currently consumes too much time. 2, 3, 5 are able to be seen by looking, but above that?

Also when do number overflows happen on calculators? [model Casio fx-87DE Plus]

(Tipp: Euler's totient theorem)

For example, I have huge numbers 12345^(9876543211) + 67890^(1234567899) mod 34567 how to quickly calculate them down? I know 1) A +B mod C = [ (A mod C) + (B mod C) ] mod C 2) A ^(B×C) mod D = {[(A^B) mod D] * [(A^C) mod D] } mod D 3) A ^ B mod C = [(A mod C) ^ B] mod C But, for example, must I try to devide large numbers down by just trying every prime number possible until I just happen to find the fitting one to reduce the exponent to a level my calculator manages? The bases are usually ok, but reducing a large, not clearly divisable exponent currently consumes too much time. 2, 3, 5 are able to be seen by looking, but above that? Also when do number overflows happen on calculators? [model Casio fx-87DE Plus] (Tipp: Euler's totient theorem)

I love math but.. bring me some popcorns!

I love math but.. bring me some popcorns!

to find a^m mod 12345 find b = a^2 * a^2 mod 12345 then find c = b^2 * b^2 mod 12345 ... find y = a^(2^k) mod 12345 where 2^k <= m and 2^(k+1) > m then use cache (b,c,d,e ...) to get a^((2^k)+q)=a^m mod 12345

to find a^m mod 12345 find b = a^2 * a^2 mod 12345 then find c = b^2 * b^2 mod 12345 ... find y = a^(2^k) mod 12345 where 2^k <= m and 2^(k+1) > m then use cache (b,c,d,e ...) to get a^((2^k)+q)=a^m mod 12345

You could perform logarithmic exponentiation, that would be ~60 iterations of multiply and divide modulo 34567 in total.
Edit: the upper bound is actually double that, so 120

You could perform logarithmic exponentiation, that would be ~60 iterations of multiply and divide modulo 34567 in total. Edit: the upper bound is actually double that, so 120

@steel-apron said ^

to find a^m mod 12345 find b = a^2 * a^2 mod 12345 then find c = b^2 * b^2 mod 12345 ... find y = a^(2^k) mod 12345 where 2^k <= m and 2^(k+1) > m then use cache (b,c,d,e ...) to get a^((2^k)+q)=a^m mod 12345

so task is a^m mod 12345.

  1. I define b as a^4 mod 12345
  2. I define c as b^4 mod 12345

oh, I see what you do now.

So argument is: make small steps with a^ something, thus always reducing the base by the mod number, avoiding a overflow.

I have not tested it, but it sounds just as laborous, because I have to simultaniously keep a tally on how large a^smt is and only reduce by lastNum^2 per turn?

I mean after many steps of n=a^(lastOne*2), I reach a^smt + k = a^original , but I still need to calculate k, which I cannot do with calculator because of overflow

@steel-apron said [^](/forum/redirect/post/HWTxrbIV) > to find a^m mod 12345 find b = a^2 * a^2 mod 12345 then find c = b^2 * b^2 mod 12345 ... find y = a^(2^k) mod 12345 where 2^k <= m and 2^(k+1) > m then use cache (b,c,d,e ...) to get a^((2^k)+q)=a^m mod 12345 so task is a^m mod 12345. 1) I define b as a^4 mod 12345 2) I define c as b^4 mod 12345 oh, I see what you do now. So argument is: make small steps with a^ something, thus always reducing the base by the mod number, avoiding a overflow. I have not tested it, but it sounds just as laborous, because I have to simultaniously keep a tally on how large a^smt is and only reduce by lastNum^2 per turn? I mean after many steps of n=a^(lastOne*2), I reach a^smt + k = a^original , but I still need to calculate k, which I cannot do with calculator because of overflow

I mean after many steps of n=a^(lastOne*2), I reach a^smt + k = a^original , but I still need to calculate k, which I cannot do with calculator because of overflow

factorize the remainder k = A02^(lastone-1) +A12^(lastone-2) + ... + Alastone-1 and then take values of a^(2^i) mod 12345 from your previous calculations...

a^(2^lastone) mod 12345 multiply by a^A02^(lastone-1) mod 12345 and then by a^A12^(lastone-2) mod 12345 ...

p.s. i'd say it is not a job for a calculator. we have a cycle which length depends on the hugeness of your input.

> > I mean after many steps of n=a^(lastOne*2), I reach a^smt + k = a^original , but I still need to calculate k, which I cannot do with calculator because of overflow factorize the remainder k = A0*2^(lastone-1) +A1*2^(lastone-2) + ... + Alastone-1 and then take values of a^(2^i) mod 12345 from your previous calculations... a^(2^lastone) mod 12345 multiply by a^A0*2^(lastone-1) mod 12345 and then by a^A1*2^(lastone-2) mod 12345 ... p.s. i'd say it is not a job for a calculator. we have a cycle which length depends on the hugeness of your input.

@steel-apron said ^

I mean after many steps of n=a^(lastOne*2), I reach a^smt + k = a^original , but I still need to calculate k, which I cannot do with calculator because of overflow

factorize the remainder k = A02^(lastone-1) +A12^(lastone-2) + ... + Alastone-1 and then take values of a^(2^i) mod 12345 from your previous calculations...

a^(2^lastone) mod 12345 multiply by a^A02^(lastone-1) mod 12345 and then by a^A12^(lastone-2) mod 12345 ...

p.s. i'd say it is not a job for a calculator. we have a cycle which length depends on the hugeness of your input.

Oh god, I took many minutes to realise lastone is not LA STONE, but last one :D

Unfortunately I did not quite understand what you mean this time.
We want to find k. Thus we assume k can be written as a factorisation of other numbers A0, A1, A2... ?

@steel-apron said [^](/forum/redirect/post/Fqf2EAY7) > > > > I mean after many steps of n=a^(lastOne*2), I reach a^smt + k = a^original , but I still need to calculate k, which I cannot do with calculator because of overflow > > factorize the remainder k = A0*2^(lastone-1) +A1*2^(lastone-2) + ... + Alastone-1 and then take values of a^(2^i) mod 12345 from your previous calculations... > > a^(2^lastone) mod 12345 multiply by a^A0*2^(lastone-1) mod 12345 and then by a^A1*2^(lastone-2) mod 12345 ... > > p.s. i'd say it is not a job for a calculator. we have a cycle which length depends on the hugeness of your input. Oh god, I took many minutes to realise lastone is not LA STONE, but last one :D Unfortunately I did not quite understand what you mean this time. We want to find k. Thus we assume k can be written as a factorisation of other numbers A0, A1, A2... ?

let's begin from the beginning. we want to get a^m mod 12345. m = a[k]*2^k + a[k-1]*2^(k-1) + ... a[0] for some k, where a[i] = 0 or 1 then we find consequentially b[i] = a^(2^i) mod 12345 using the fact that (a * b) (mod c) = ((a mod c) * (b mod c)) mod c. computation starts from b[0] = a mod 12345 up to b[k]. finally we'll compute a composition of (b[1] * b[13] * b[27] * b[38] *...) mod 12345 where a[1] = a[13] = a[27] = a[38] =...= 1 and the rest are zeroes this composition will be the desired number.

this is the algorythm i suggest.

let's begin from the beginning. we want to get a^m mod 12345. m = a[k]*2^k + a[k-1]*2^(k-1) + ... a[0] for some k, where a[i] = 0 or 1 then we find consequentially b[i] = a^(2^i) mod 12345 using the fact that (a * b) (mod c) = ((a mod c) * (b mod c)) mod c. computation starts from b[0] = a mod 12345 up to b[k]. finally we'll compute a composition of (b[1] * b[13] * b[27] * b[38] *...) mod 12345 where a[1] = a[13] = a[27] = a[38] =...= 1 and the rest are zeroes this composition will be the desired number. this is the algorythm i suggest.

@steel-apron said ^

let's begin from the beginning. we want to get a^m mod 12345. m = a[k]*2^k + a[k-1]*2^(k-1) + ... a[0] for some k, where a[i] = 0 or 1 then we find consequentially b[i] = a^(2^i) mod 12345 using the fact that (a * b) (mod c) = ((a mod c) * (b mod c)) mod c. computation starts from b[0] = a mod 12345 up to b[k]. finally we'll compute a composition of (b[1] * b[13] * b[27] * b[38] *...) mod 12345 where a[1] = a[13] = a[27] = a[38] =...= 1 and the rest are zeroes this composition will be the desired number.

this is the algorythm i suggest.

ah, ok I get it, you turn the number into a-nary:
for any term a^b mod c, we define function f[] as

f[0] = 0
f[1] = a
f[n]= { f[n-1] +...+ f[1] +1) } mod c

The you compute f[n] long enough for 2 f[x] to appear that have the same value. Rest has the same pattern, thus allowing us to calculate d:= [b mod lengthOfThePattern].

Allowing us to calculate a^(b-d) mod c?

What do you mean with composition?

@steel-apron said [^](/forum/redirect/post/tmkqzFtB) > let's begin from the beginning. we want to get a^m mod 12345. m = a[k]*2^k + a[k-1]*2^(k-1) + ... a[0] for some k, where a[i] = 0 or 1 then we find consequentially b[i] = a^(2^i) mod 12345 using the fact that (a * b) (mod c) = ((a mod c) * (b mod c)) mod c. computation starts from b[0] = a mod 12345 up to b[k]. finally we'll compute a composition of (b[1] * b[13] * b[27] * b[38] *...) mod 12345 where a[1] = a[13] = a[27] = a[38] =...= 1 and the rest are zeroes this composition will be the desired number. > > this is the algorythm i suggest. ah, ok I get it, you turn the number into a-nary: for any term a^b mod c, we define function f[] as f[0] = 0 f[1] = a f[n]= { f[n-1] +...+ f[1] +1) } mod c The you compute f[n] long enough for 2 f[x] to appear that have the same value. Rest has the same pattern, thus allowing us to calculate d:= [b mod lengthOfThePattern]. Allowing us to calculate a^(b-d) mod c? What do you mean with composition?