Special property for mod

[dsouza123]

I am trying to understand the mod function, ( the integer remainder after an integer division ).

When it is a mod of small numbers, it is understandable how it is done very quickly, but with very large numbers in the range of mersennes how is it done. Is there some special properties of mod/modular arithmetic that quickens it ?

Example
2^22282517 mod 5393976387915192439 results in 1
Would 2 to the 2222517 power need to be calculated then have it divided by 5393976387915192439 with the remainder the answer ?

I noticed uBasic does it instantly, also the gmp calculator at http://www.swox.com/gmp/
UBasic only supports integers that fit in 540 16 bit words so that would be about 2600 digits yet 2^22282517 is about 6707706 digits long and there is no overflow error and the result is correct.

How is this possible?
I've gone to sites that discuss modular arithmetic but haven't found any answers.

Is there something unique with powers of 2 or whatever special property is being used can it be done with other bases ?

[smh]

when you type

? 2^22282517 mod 5393976387915192439

you'll get an overflow, so i'll guess you mean the modpow function?

? modpow(2,22282517,5393976387915192439)

From the help:

~~MODPOW
MODPOW(a,b,n)
(a to the b) mod n. Mod is taken each time a is raised in
order not to overflow. b >= 0, n > 0.
Note: If b = 0, it returns 1 neglecting the value of a.
Inp: b must be integer b >= 0
a and n must be the same type: integer, polynomial or
modpolynomial. if a is integer then n must be positive.
Out: same as a
Ex: print modpow(12,34,56) result: 16

[dsouza123]

You are correct the modpow(base,exp,modvalue) is what I used in uBasic.
The equation I posted is from using the gmp calculator.
Sorry for the confusion.

Is it really as simple as that ?

Is this the method for modpow ?

start with the base
repeat
do a multiply and a mod
until until (exp - 1) multiplies are done.

[wblipp]

mod(a*b) = mod( mod(a) * mod(b) )
mod(a+b) = mod( mod(a) + mod(b) )

You calculate mod( 2^22282517 ) with successive squaring, picking off the items needed.

mod(2^1) = 2
mod(2^2) = mod( 2^1 * 2^1 )
mod(2^4) = mod( 2^2 * 2^2 )
mod(2^8) = mod(2^4 * 2^4 )
mod(2^16) = mod(2^8 * 2^8 )
etc.

You can arrange the calculation in 3 columns
1. Halve the exponent in the first column
2. Square the number in the second column
3. Collect odd powers in the third column


22282517   2 1
11141253   4 2
 5570626  16 8
 2785313 256 8

The first line repesents your number as
2^22282517 * 1

The second line represents this same number as
4^11141253 * 2

The third line represents this same number as
16^5570626 * 8

The fourth as
256^2785313 * 8

When the numbers in the second and third column get larger than the modulus, you replace the values with modulus. In a few rows you will have the number as
(Col 2)^0 * (Col 3)

which is just the column 3 number.

[GP2]

The GMP library also has a "modpow" function, except it's called mpz_powm. GMP uses a naming scheme where the mpz_ prefix indicates integer functions, mpf_ indicates floating-point functions, and so forth.

Naturally, you want to use this function rather than literally calculating 2^enormous and only then doing the modulo.