Squaring modulo a value - XP Math - Forums

 XP Math - Forums Squaring modulo a value

 08-21-2008 #1 haravikk Guest   Posts: n/a Squaring modulo a value Hi there, To preface; my experience with mathematics in the domain of computing, my understanding of maths notation is relatively basic though I'm fairly comfortable with high-school mathematics and some more complex, mostly base 2 (binary) stuff. I'm mostly familiar with algorithms for doing things rather than equations. If any answers can be given as simply as possible I'd much appreciate it! The problem I'm working with is one of encryption, namely; I'm attempting to implement RSA cryptography on a very limited platform, so efficiency is a must. Now, I've followed many standard algorithms but unfortunately they're not quite all there. For those not familiar with it, RSA basically works by taking a chunk of data, treating it as a big number, raising it to the power of a public key, and reducing it modulo another number. In computing terms however these numbers are too big for the machine to handle natively, so they are treated as multiple digits where each digit is represented by a smaller (native) number. For the sake of this let's just assume I'm working in base 10 since it's nice and simple. Also, in case people don't know about the modulo (%) operation, for two values a and b, a % b will return the remainder of the division a / b. I can't remember encountering this operator in maths, but it's everywhere in computing as it helps to restrict values to useful ranges. Anyway, the current method I'm using to do (a ^ b) % c is to do the calculation in steps, each step I perform either a squaring of a value, or a multiplication, and then immediately reduce it % c, this helps keep the value at a sane size, and I don't need the full result of a ^ b anyway. However, each of these squarings and multiplications are costly, and I'm wondering if there is any good mathematical way to reduce the work required in calculating them, knowing that they are to be reduced modulo c immediately afterward? For example, if one of the multiplications were (43 * 37) % 59, I would end up with a 4-digit result for 43 * 37 (1591), but I'm reducing it to fit within a two-digit restriction. So do I really need all four digits to be calculated? Is there anything else I can do with the two values to get the same result, knowing that it will fall within the range of 0 - 58? For those that are familiar with the problem, I'm using Diminished Radix Reduction to do the modulo operation quickly, and the squarings/multiplications utilise the "Comba" method for speed, but are ultimately O(n ^ 2) complexity; that is, for n digits the algorithm takes n ^ 2 time to calculate the result. I'd hoped to use Karatsuba multiplication but the overhead actually makes it a lot slower for me =( Thanks for any help, I'm trying loads of other techniques too, but anyone who likes a challenge any efforts to help are much appreciated!

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Welcome     XP Math News     Off-Topic Discussion Mathematics     XP Math Games Worksheets     Homework Help     Problems Library     Math Challenges

All times are GMT -4. The time now is 05:53 AM.

 Contact Us - XP Math - Forums - Archive - Privacy Statement - Top