 mersenneforum.org > Math The modulo operation, how is it computed?
 Register FAQ Search Today's Posts Mark Forums Read 2002-12-31, 13:05   #1
eepiccolo

Dec 2002
Frederick County, MD

17216 Posts The modulo operation, how is it computed?

OK, I've looked at the math of the LL test, and for reference, here is a guote form a thread in "The Software"
Quote:
Originally Posted by smh

From that page:
Quote:
 The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2^P-1 is prime if and only if S^p-2 is zero in this sequence: S(0) = 4, S(N) = S(N-1)^2 - 2 mod 2^P-1. For example, to prove 2^7 - 1 is prime: [list] S0 = 4 S1 = 4 * 4 - 2 mod 127 = 14 S2 = 14 * 14 - 2 mod 127 = 67 S3 = 67 * 67 - 2 mod 127 = 42 S4 = 42 * 42 - 2 mod 127 = 111 S5 = 111 * 111 - 2 mod 127 = 0[/list:u]
People talk about the multiplication of large numbers, and how we use a DFT to accomplish this. While I don't fully understand this process yet, I have found resources and am studying it. However, I haven't found anything about how the modulo operation works. Is the modulo operation something so simple that people don't really talk about it? If so, I'm sure someone could give me a simple explanation of how the operation is preformed. Or perhaps something else is going on that I haven't found out about yet? Could someone please help me out on this?   2002-12-31, 20:21   #2

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts Re: The modulo operation, how is it computed?

Quote:
Originally Posted by smh
From that page:
Quote:
 The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2^P-1 is prime if and only if S^p-2 is zero in this sequence: S(0) = 4, S(N) = S(N-1)^2 - 2 mod 2^P-1.
There's a mistake in that quote.

Quote:
 ... if and only if S^p-2 is zero ...
should be

Quote:
 ... if and only if S(p-2) is zero ...   2002-12-31, 20:53   #3

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts Re: The modulo operation, how is it computed?

Quote:
 Originally Posted by eepiccolo Is the modulo operation something so simple that people don't really talk about it?
Um ... yeah ... but once you know the secret password, it's easy. :)

"M modulo N", in the context of GIMPS, basically means "the remainder when M is divided by N". "Modulo" is usually abbreviated as "mod".

Examples:[list]7 mod 2 = 1
7 mod 4 = 3
8 mod 2 = 0
2 mod 8 = 2[/list:u]

There's more to it than just that, but as long as you're discussing only positive integers, you can usually get along all right with the simple "remainder when M is divided by N" definition.

"Congruence" is a term closely associated with "modulo".

See http://mathworld.wolfram.com/Congruence.html for a more complete explanation of "modulo".

(BTW, http://mathworld.wolfram.com/ is a great reference for almost any mathematical term! Eric Weisstein, its author, has done a great service to mathematics by compiling definitions and explanations of thousands (over 11,000) of math terms.

But that's not all! Eric Weisstein has also compiled similar databases for some of the sciences and music. See http://www.ericweisstein.com/encyclopedias/)   2003-01-02, 12:47 #4 eepiccolo   Dec 2002 Frederick County, MD 5628 Posts Actually... I wasn't refering to what the modulus opperator does... I have a pretty good handle on congruences and whatnot. I am curious from a computer's point of view how a mod is calculated, which I guess boils down do modular arithmetic in base 2. The impression I get is that there is some sort of shortcut to taking mods with 2^p-1. I'm just trying to figure out why we don't have to worry about the time it takes to mod, since from all I've read, we only worry about the time it takes to square (which, of course, is sped up by an FFT).   2003-01-06, 13:35 #5 eepiccolo   Dec 2002 Frederick County, MD 2·5·37 Posts Hmmm, now, before the crash , Cheesehead had told me that the FFT gives us the mod for free. But someone else had also given a method for taking mods, and unfortunately, I don't remember who that was, and I didn't write down what that person wrote. So could whoever it was that posted that please post their reply again?   2003-01-07, 07:39   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts Not just any old FFT operation gives the mod 2^P-1 for free.

It's Crandall-Fagin's discrete weighted transform using an irrational base that mods for free, because it performs within itself the same set of operations that produce the mod 2^P-1.

From the GIMPS math page at http://www.mersenne.org/math.htm:
Quote:
 In a January, 1994 Mathematics of Computation article by Richard Crandall and Barry Fagin titled "Discrete Weighted Transforms and Large-Integer Arithmetic", the concept of using an irrational base FFT was introduced. This improvement more than doubled the speed of the squaring by allowing us to use a smaller FFT and it performs the mod 2^P-1 step for free.   2003-01-07, 16:01   #7
zygote

Sep 2002

716 Posts eepiccolo wrote

Quote:
 But someone else had also given a method for taking mods
The method only works when the calculation is done in base 2, which fortunately is the way computers are designed. It relies on the fact that 2^p-1 is one less than a power of two. In mod notation, 2^p = 1 (mod 2^p-1). That allows one to reduce the modulo calculation to a simple additon.

After squaring and subtracting two, but before reducing modulo 2^p-1, S(n) is a number of no more than 2p binary digits. This can be written

S(n) = 2^p * (top p significant digits) + (bottom p significant digits)
= (top p significant digits) + (bottom p significant digits) (mod 2^p-1)

Please note how similar this is to determining whether a base 10 number is divisible by 9. The fact that 9 is one less than a power of ten allows one to transform an issue of divisibility into a simple addition problem by the method of "casting out nines". Simply add up the digits of the number and check to see if the sum is divisible by nine.   2003-01-08, 03:07   #8

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts Quote:
 Originally Posted by zygote S(n) = 2^p * (top p significant digits) + (bottom p significant digits) = (top p significant digits) + (bottom p significant digits) (mod 2^p-1)
Quote:
 S(n) = [ 2^p * (top p significant digits) ] + [ (bottom p significant digits) ] = [ (top p significant digits) + (bottom p significant digits) ] (mod 2^p-1)
IOW, add the top p significant digits (as a p-bit integer) to the bottom p significant digits (as another p-bit integer), then (if there was a carry out of the most significant bit during the addition) do a modulo 2^p-1 on that sum.

Quote:
 Originally Posted by zygote Please note how similar this is to determining whether a base 10 number is divisible by 9. The fact that 9 is one less than a power of ten allows one to transform an issue of divisibility into a simple addition problem by the method of "casting out nines". Simply add up the digits of the number and check to see if the sum is divisible by nine.
Yes! We're "casting out (2^p-1)s"! :D  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post daxmick Information & Answers 12 2017-12-03 23:36 clowns789 Operation Billion Digits 574 2017-09-12 01:34 Oddball Twin Prime Search 370 2013-01-03 21:26 smslca Math 3 2011-04-18 17:18 crash893 Software 23 2005-10-17 03:47

All times are UTC. The time now is 03:32.

Fri May 20 03:32:38 UTC 2022 up 36 days, 1:33, 0 users, load averages: 1.49, 1.47, 1.43