mersenneforum.org  

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

Reply
 
Thread Tools
Old 2002-12-31, 13:05   #1
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

17216 Posts
Default 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
The math page gives more information about what the program actually does.

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?
eepiccolo is offline   Reply With Quote
Old 2002-12-31, 20:21   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts
Default 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 ...
cheesehead is offline   Reply With Quote
Old 2002-12-31, 20:53   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default 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/)
cheesehead is offline   Reply With Quote
Old 2003-01-02, 12:47   #4
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

2×5×37 Posts
Default

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).
eepiccolo is offline   Reply With Quote
Old 2003-01-06, 13:35   #5
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

2·5·37 Posts
Default

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?
eepiccolo is offline   Reply With Quote
Old 2003-01-07, 07:39   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2003-01-07, 16:01   #7
zygote
 
Sep 2002

1112 Posts
Default

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.
zygote is offline   Reply With Quote
Old 2003-01-08, 03:07   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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)
Let me add brackets to avoid the potential misinterpretation I made first time I read this:
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
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How is GHz days computed? daxmick Information & Answers 12 2017-12-03 23:36
Operation: Billion Digits clowns789 Operation Billion Digits 574 2017-09-12 01:34
Operation Megabit Twin Oddball Twin Prime Search 370 2013-01-03 21:26
modulo operation for polynomials? smslca Math 3 2011-04-18 17:18
how are odds computed? crash893 Software 23 2005-10-17 03:47

All times are UTC. The time now is 04:59.


Thu Dec 2 04:59:31 UTC 2021 up 131 days, 23:28, 0 users, load averages: 1.53, 1.32, 1.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.