----- Original Message ----- From: "Frank_A_L_I_N_Y" <[EMAIL PROTECTED]> To: "Mersenne discussion list" <[EMAIL PROTECTED]> Sent: Tuesday, May 28, 2002 12:43 PM Subject: Mersenne: Quicker Multiplying ?
6 is -2 mod 8 6*6 = 36 36 = -4 mod 8 2^2 = 4 if the mod of the represented as a negative is much less than the positive, could we square the negative and save some time ? Thanks Frank Anzalone I once had a look at something like that (though not in relation to Mersenne primes). In general, if you want to calculate a^2 mod m, and (m - a) is less than (or equal to) the square root of m, then you just calculate (m -a)^2 and don't have to perform a 'mod' operation at all !! Only trouble is, that as m gets larger, the chances that (m - a) will be less than the square root of m diminish - and the testing required outweighs the advantage of being able to (occasionally) avoid having to perform a mod operation. Of course even if (m-a) is greater than the square root of m, it may still be quicker to do (m - a)^2 mod m than to do m^2 mod m. (I suppose that if a > m /2, then (m-a)^2 mod m can be calculated at least as quickly m^2 mod m.) But it was the cost of continually testing the condition and performing the subtraction that made it not wothwhile in my case. (Then again, it might just have been the case that *I* was not "testing the condition and performing the subtraction" in an efficient manner :-) As regards the search for Mersenne primes, I suspect that the same costs would kill the idea, though I don't really know ...... Cheers, Rob _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
