20031030, 15:08  #1 
Sep 2002
2·331 Posts 
Special property for mod
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 ? 
20031030, 16:16  #2  
"Sander"
Oct 2002
52.345322,5.52471
29·41 Posts 
when you type
Code:
? 2^22282517 mod 5393976387915192439 Code:
? modpow(2,22282517,5393976387915192439) Quote:


20031030, 16:34  #3 
Sep 2002
2×331 Posts 
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. 
20031030, 16:39  #4 
"William"
May 2003
New Haven
23×103 Posts 
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. 
20031031, 05:49  #5 
Sep 2003
5·11·47 Posts 
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 floatingpoint functions, and so forth.
Naturally, you want to use this function rather than literally calculating 2^enormous and only then doing the modulo. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Intellectual property rites  davar55  Soap Box  199  20170524 04:01 
MMO Property Calculation  Bundu  Puzzles  22  20090922 01:30 
A property of Fermat numbers. Already known ?  T.Rex  Math  6  20060917 22:11 
A property about the order of divisors of (Mq1)/2  T.Rex  Math  3  20051114 18:23 
I need a proof for this binomial property.  T.Rex  Math  3  20041008 19:13 