mersenneforum.org > Math Special property for mod
 Register FAQ Search Today's Posts Mark Forums Read

 2003-10-30, 15:08 #1 dsouza123     Sep 2002 66210 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 ?
2003-10-30, 16:16   #2
smh

"Sander"
Oct 2002
52.345322,5.52471

100101001012 Posts

when you type

Code:
? 2^22282517 mod 5393976387915192439
you'll get an overflow, so i'll guess you mean the modpow function?
Code:
? modpow(2,22282517,5393976387915192439)
From the help:
Quote:
 ~~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

 2003-10-30, 16:34 #3 dsouza123     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.
 2003-10-30, 16:39 #4 wblipp     "William" May 2003 New Haven 3×787 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.
 2003-10-31, 05:49 #5 GP2     Sep 2003 50368 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 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post davar55 Soap Box 199 2017-05-24 04:01 Bundu Puzzles 22 2009-09-22 01:30 T.Rex Math 6 2006-09-17 22:11 T.Rex Math 3 2005-11-14 18:23 T.Rex Math 3 2004-10-08 19:13

All times are UTC. The time now is 16:21.

Sat May 15 16:21:10 UTC 2021 up 37 days, 11:02, 0 users, load averages: 2.19, 2.11, 2.11