Quantcast Squaring modulo a value - XP Math - Forums
XP Math Home Sign Up FREE! | Sign In | Classroom Setup | Common Core Alignment PDF Version

Go Back   XP Math - Forums > Welcome > Off-Topic Discussion

Thread Tools Display Modes
Old 08-21-2008   #1
Posts: n/a
Default 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!
  Reply With Quote

Thread Tools
Display Modes

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 Jump

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, vBulletin Solutions Inc.
XP Math