mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-10-30, 15:08   #1
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default 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 ?
dsouza123 is offline   Reply With Quote
Old 2003-10-30, 16:16   #2
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

100101001012 Posts
Default

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
smh is offline   Reply With Quote
Old 2003-10-30, 16:34   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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.
dsouza123 is offline   Reply With Quote
Old 2003-10-30, 16:39   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2003-10-31, 05:49   #5
GP2
 
GP2's Avatar
 
Sep 2003

29·89 Posts
Default

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.
GP2 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Intellectual property rites davar55 Soap Box 199 2017-05-24 04:01
MMO Property Calculation Bundu Puzzles 22 2009-09-22 01:30
A property of Fermat numbers. Already known ? T.Rex Math 6 2006-09-17 22:11
A property about the order of divisors of (Mq-1)/2 T.Rex Math 3 2005-11-14 18:23
I need a proof for this binomial property. T.Rex Math 3 2004-10-08 19:13

All times are UTC. The time now is 18:53.

Sat Oct 24 18:53:05 UTC 2020 up 44 days, 16:04, 0 users, load averages: 1.77, 1.92, 1.97

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.