mersenneforum.org  

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

Reply
 
Thread Tools
Old 2016-03-29, 13:12   #1
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default CRT optimisation?

Apologies in advance for what is probably a rather naïve question. I'm playing with a factoring algorithm in which CRT calculations are one of the bottlenecks. I have used an optimisation to the CRT calculation, which improves things slightly. I have never seen this optimisation mentioned in the literature, and was wondering why, as it is a very obvious one: Rather than solving:
x = r0 (mod m0)
x = r1 (mod m1)
...
x = rn (mod mn)
we can solve
x-r0 = 0 (mod m0)
x-r0 = r1-r0 (mod m1)
...
x-r0 = rn-r0 (mod mn)
meaning one modular inversion can be avoided due to the 0 residue in the modified first congruence.
For example, in the case of just 2 congruences, this leads to:
x = r0 + |m0-1|m[SUB]1[/SUB] m0 (r1-r0) (mod m0m1)
rather than the usual:
x = |m1-1|m[SUB]0[/SUB]m1r0 + |m0-1|m[SUB]1[/SUB]m0r1 (mod m0m1)
Do the disadvantages (initial extra addition plus extra subtraction per non-initial congruence, and the possible complications of (ri-r0) going negative) outweigh the advantages in general?
Just curious... (and apologies for using = rather than the congruence symbol, which I can't find!)

Last fiddled with by mickfrancis on 2016-03-29 at 13:19 Reason: Formatting
mickfrancis is offline   Reply With Quote
Old 2016-03-29, 13:36   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
(and apologies for using = rather than the congruence symbol, which I can't find!)
no worries \equiv is what you want it's done in \TeX
science_man_88 is offline   Reply With Quote
Old 2016-03-29, 13:39   #3
mickfrancis
 
Apr 2014
Marlow, UK

5610 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
no worries \equiv is what you want it's done in \TeX
Ah yes - thanks!
mickfrancis is offline   Reply With Quote
Old 2016-03-29, 14:20   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33×131 Posts
Default

Are you assuming m0 is the smallest modulus in the set? I would think you risk messing up the CRT otherwise.

I don't have my copy of Knuth handy, but this looks a little like the fast(er) CRT that he describes.
jasonp is offline   Reply With Quote
Old 2016-03-29, 14:52   #5
mickfrancis
 
Apr 2014
Marlow, UK

3816 Posts
Default

Quote:
Originally Posted by jasonp View Post
Are you assuming m0 is the smallest modulus in the set? I would think you risk messing up the CRT otherwise.

I don't have my copy of Knuth handy, but this looks a little like the fast(er) CRT that he describes.
I'm not sure why it would be a problem - it's really just modular subtraction on the left and subtraction in a Residue Number System on the right isn't it? (I'm probably missing something here though...). I'd be interested to see the Knuth algorithm...
mickfrancis is offline   Reply With Quote
Old 2016-03-29, 16:46   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

7·239 Posts
Default

It's an exercise in Knuth (The Art of Computer Programming volume 2) just after his discussion of the Garner algorithm.
Nick is online now   Reply With Quote
Old 2016-03-29, 18:49   #7
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default

Quote:
Originally Posted by Nick View Post
It's an exercise in Knuth (The Art of Computer Programming volume 2) just after his discussion of the Garner algorithm.
I knew I should have invested in those volumes!
mickfrancis is offline   Reply With Quote
Old 2016-03-30, 00:38   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33·131 Posts
Default

The problem I was thinking of was that in general (a mod b) mod c is not the same as (a mod c) mod b. So if your m0 was larger than m1, then (r1 - r0) mod m1 may not be the same as (r1 - (r0 mod m1)) mod m1. I could be overthinking it though.
jasonp is offline   Reply With Quote
Old 2016-03-30, 02:08   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by jasonp View Post
The problem I was thinking of was that in general (a mod b) mod c is not the same as (a mod c) mod b. So if your m0 was larger than m1, then (r1 - r0) mod m1 may not be the same as (r1 - (r0 mod m1)) mod m1. I could be overthinking it though.
to further point out this problem I decided to post an example:

(30 mod 5) mod 7 -> 0 mod 7
(30 mod 7) mod 5 -> 2 mod 5

all we did was change the order of the modulo operations and it changes what we get back.

I think jasonp is overthinking it if CRT is chinese remainder theorem as the mod is never done twice and if you subtract the same thing from two things that are congruent they stay congruent. in the two congruences you give ( unless you meant m0 in one of them) you can think of them as polynomials r1-r0 can be (m1*y+r1)-(m1*z+r2). though I still don't see how you can cross values mod the m's like that. if you remember that any value mod another number is always congruent to itself you can rewrite the second as the first.

Last fiddled with by science_man_88 on 2016-03-30 at 02:11
science_man_88 is offline   Reply With Quote
Old 2016-03-30, 10:20   #10
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

7×239 Posts
Default

May I suggest that the modern algebraic way of looking at this offers some advantages here?

If we are working with integers modulo 5, for example, then we regard integers a and b as equivalent if (and only if) 5 divides a-b, so we have 5 equivalence classes:
{...,-15,-10,-5, 0,5,10,15,...}
{...,-14,-9,-4, 1,6,11,16,...}
{...,-13,-8,-3, 2,7,12,17,...}
{...,-12,-7,-2, 3,8,13,18,...}
{...,-11,-6,-1, 4,9,14,19,...}
For any integer a, we write \(\bar{a}\) to denote the equivalence class of a, i.e. the entire set of all integers equivalent to a modulo 5 (this is the set in the above list which a appears in).
We then define addition and multiplication on these sets by:
\[
\begin{eqnarray*}
\bar{a}+\bar{b} & = & \overline{a+b} \\
\bar{a}\cdot\bar{b} & = & \overline{a\cdot b}
\end{eqnarray*}
\]
for any integers a & b, and show that this is well-defined (i.e. the definition does not depend on the representative elements chosen). Thus, for example, we can write \(\bar{4}^2=\overline{-1}^2=\bar{1}\).

Viewed this way, we are not tempted to write something like "30 mod 5 mod 7" because 30 mod 5 is then the set \(\overline{30}=\bar{0}\) and not all elements of the set have the same remainder on division by 7, so the final "mod 7" is not a valid operation.
Nick is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Data Centre Energy Consumption Optimisation pinhodecarlos Lounge 15 2019-03-15 14:19
An opportunity for search engine optimisation fivemack Aliquot Sequences 6 2015-11-17 20:31
Basic optimisation question fivemack Puzzles 6 2008-04-08 13:50
HT and all kind of other optimisation thread hhh Prime Sierpinski Project 2 2006-04-06 09:33

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

Tue May 11 11:16:36 UTC 2021 up 33 days, 5:57, 1 user, load averages: 2.33, 2.36, 2.24

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.