[SOLVED] Modular Exponents in PHP

[HFD]

Hi, sorry for the large amount of posts lately but I need more help 

 

I need to be able to work out very large powers with mod n - so for example, at the moment I'm testing 614^17 (mod 5063).

 

So far I have this script:

 

<?php

$num1 = 614;
$num2 = 17;
$mod = 5063;
$answer;


for ($i = 0; $i < $num2; $i++)
{
$answer = $num1 * $num2;
$answer = $answer % $mod;
$num1 = $answer;
}

echo $num1;
echo "<br />";
echo $num2;
echo "<br /><b>";
echo $answer;

?>

 

However, I've calculated the value that the answer should be, and verified it with others, and the server is not outputting the correct values. The answer should be 2668, but the server does not return this value - I've also tried changing the < $num2 in the for loop to <= $num2, etc but to no avail.

 

Any ideas? Thanks

[Daniel0]

You cannot have numbers above 2,147,483,648 for a 32-bit signed integer. You need to use something like BCMath.

[HFD]

Thanks for your reply, I'm just testing the BCMath extensions now as they are installed on my server.

 

But, I'm a bit as I am using this method of exponentiation because it uses significantly less memory (after every multiplication, it applies mod 5063 to that number, then carries out the next, modding that number too...etc), and I was told in theory the PC should never have to compute large numbers at once with this method. Or perhaps I'm just thinking of it wrong

 

EDIT: BCMath returns the same wrong result...but, I've noticed something rather stupid in my code. I was multiplying $num1 by $num2 which was wrong, as it should be simply $num1 * $num1 - I've amended this but still have the wrong answer...is there anything else I've missed? Thanks

[Daniel0]

I'm not really sure what you're trying to do. Are you trying to do what in PHP equates to pow(614, 17) % 5063? In that case you can just do bcmod(bcpow(614, 17), 5063).

[HFD]

Thanks for your reply again, I've just tested that and it works perfect so thanks this is for coursework though and we are required to understand the theory that when carrying out modular exponentiation that after every power/multiplication, if you mod the number by the modulus you are using, and carry out the next multiplication on the newly 'modded' number, and repeat that until you finish all the multiplications required in the exponentiation. So to perhaps show that I understand the theory I'm wondering if it's possible to do it that way in PHP...

 

For example, in this 614^17 mod 5063...

 

1: 614 * 614 = 376 996

    376996 mod 5063 = 2334

 

2: 2334 * 2334 = 5447556

    5447556 mod 5063 = 4831

 

 

And carry this out 17 times in total, after all the exponentiation is done.

 

If I'm being completely confusing no worries, as the code you gives works fine I could just use that

[HFD]

Right, I just figured out that my method that I'm using seems completely wrong 

 

So I guess a final question (which has nothign to do with PHP, sorry:p)  is how would you break down these equations so they are easy to perform? For example I also have to do 2668^3473 (mod 5063) which would of course prove impossible by hand...Thanks

[Daniel0]

You could do this:

$base = 614;
$exponent = 17;
$mod = 5063;

for ($res = 1; $exponent > 0; $exponent >>= 1) {
if (($exponent & 1) == 1) {
	$res = $res * $base % $mod;	
}

$base = $base * $base % $mod;
}

echo $res;

[HFD]

Thanks, that works great just one last question - I'd like to be able to fully comprehend what the program does (I'm not completely familiar with PHP) so can I just ask what the $exponent >>= 1 and $exponent & 1 signify? I'm not familiar with these expressions.

 

Again, thanks very much.

[Daniel0]

You can read about those operators here:

http://php.net/operators.bitwise

 

& is bitwise AND. It "flips on" the bits that are "on" in both the left and the right operands. E.g. 1100₂ & 1001₂ = 1000₂

 

>> means "shift right". It essentially shifts the bits in the left operand the number of the times the right operand specifies. E.g 0011₂ << 2₁₀ = 1100₂

[HFD]

Thanks