mod (modulus)question

daggeredge

ok...
repeating networking and have to do RSA

my prob is this during decryption I have to....

On the calculator when I put 17 to the power of 29

I get 4.819685721...to the power of 35
i need to subtract before the decimal and multiply by something else however it won't come out with a viable answer (methinks its down to the power of 35!)
how do I convert it to a number without powers so I can subtract before the point?!
cheers

(is there a calculation I can do, or a button on my calculator? - casio by the way)

satchmo

Heheh thats not to the power of 35, it's e+35, which means move the decimal point 35 places to the right. Calculators do this because there's not enough space do display that many digits.

Seth Brundle

satchmo is correct - you are basically trying to get an integer (4) from the answer (4.819685721 with 35 decimal places) whereas in fact the answer is already an integer (albeit a very long one)

daggeredge

cheers 4 that!
alright back 2 it! :rolleyes:

Syth

You must remember that calculators can only store numbers to a certain degree of accuracy. So the correct answer to a question might be 563,459,235,021,004,555 but the calculator would only store that as 5.634592350 * 10^18, ie as 563,459,235,000,000,000, so it wouldn't be exact. Don't really knwo how to get around that though, pen and paper?

Paulmee

daggeredge wrote:

ok...
On the calculator when I put 17 to the power of 29
QUOTE]

I could be wrong but this is how I would do it.
Instead of 17 to the power of 29, take 17 to the power of 15 * 17 to the power of 14. i.e (14+15) Choose smaller numbers if you have to.

Then mod each of these individually.
17^15 mod x and 17^14 mod x.

Keep on repeating this until you get the key or whatever. The method of solving this should only involve using integers.

I could be wrong though...

Seth Brundle

it would result in an integer as one integer minus another will still leave an integer whether it is +ive, zero or -ive

Err..

Potato Man wrote:

daggeredge wrote:

ok...
On the calculator when I put 17 to the power of 29
QUOTE]

I could be wrong but this is how I would do it.
Instead of 17 to the power of 29, take 17 to the power of 15 * 17 to the power of 14. i.e (14+15) Choose smaller numbers if you have to.

Then mod each of these individually.
17^15 mod x and 17^14 mod x.

Keep on repeating this until you get the key or whatever. The method of solving this should only involve using integers.

I could be wrong though...

I think that should be something more like:

((17^15 mod x) + (17^14 mod x)) mod x


If on the other hand you actually need to work out the complete integer value of 17^29 I can only think of breaking this into sections that your calculator can handle and then using paper. Using my calculator I can do 17^8 before E numbers come into play so I would break it down like this:

17^29 =
17^8 * 17^8 * 17^8 * 17^5 =
6975757440 * 6975757440 * 6975757440 * 1419857 =
then use paper...

PhilH

Lads, isn't this meant to be the programming forum? How about this approach...

import java.math.*;

public class Main
{
    public static void main (String[] args)
    {
        BigInteger x = new BigInteger("17");
        BigInteger y = x.pow(29);
        System.out.println(y);
    }
}

Giving 481968572106750915091411825223071697

Err..

Err.. wrote:

I think that should be something more like:

((17^15 mod x) + (17^14 mod x)) mod x

Sorry, should have read

((17^15 mod x) * (17^14 mod x)) mod x

Also, if this is the case, it follows that

((17^1 mod x) * (17^1 mod x) ...29 times) mod x

gives the answer which may be an easier way of approaching it if 17 mod x results in a small number

Err..

PhilH wrote:

Lads, isn't this meant to be the programming forum? How about this approach...

import java.math.*;

public class Main
{
    public static void main (String[] args)
    {
        BigInteger x = new BigInteger("17");
        BigInteger y = x.pow(29);
        System.out.println(y);
    }
}

Giving 481968572106750915091411825223071697

Of course, but I assume the original post related to sitting an exam where paper and calculator would be the only tools available.

Err..

Err.. wrote:

17^29 =
17^8 * 17^8 * 17^8 * 17^5 =
6975757440 * 6975757440 * 6975757440 * 1419857 =
then use paper...

Apologies, just realised the 0 at the end of 6975757440 is actually a loss of precision so would use

17^7 * 17^7 * 17^7 * 17^7 * 17

instead

PhilH

Completely fair point, Err..

I was only half-serious with the post anyway. Hope I didn't step on anyone's toes.

PHiL

Paulmee

Obviously doing it in a programming language would be quicker/more relevant to this board.
I also presumed it was for a pen and paper exam having done something similar in Cryptography last year

I had forgotten how to do problems like that, thanks Err.. for refreshing my memory.
All I remember was (in a kinda-pseudo way) to solve stuff like that
1. Break down the answer into bits.
2. Mod each part
3. Repeat step 1.

Thats why mod is so useful in comp science.

LoBo

If you're doing it w/ pen and paper you don't need to multiply it all out- just leave everything in power-of form

If its not for a PnP exam, use a tool eg mathematica rather than a handheld calculator, lost accuracy etc.