Exponentation?

[himmu7]

Could anybody suggest me how to write a code in C for calculating 15 bytes of base value powered to 64 bytes of exponent value?

[newb16]

You can't raise <amount of bytes> to the power of <amount of bytes>. You can raise number to number,and it depends on how the numbers are represented there. If they are positive integers, it will take 15*( 2^512) bytes of memory to store the result.

[himmu7]

You can't raise <amount of bytes> to the power of <amount of bytes>. You can raise number to number,and it depends on how the numbers are represented there. If they are positive integers, it will take 15*( 2^512) bytes of memory to store the result.

ya wat u said is right. but my problem is , in my application i do have value of 15 byte value.(i.e the total no. is 15 byte value) and even exponent value is 64 byte value.so now how to perform calculation for that. have to divide into bytes and calculate or any other method is there?

[donbock]

What accuracy and precision do you need for your result?

[himmu7]

What accuracy and precision do you need for your result?

There is nothing worry about precession.

[donbock]

Then convert these big integers into floating point. You will lose a lot of accuracy, but you will be able to compute an approximation.

Another approach is to apply the mathematical rules for using logarithms to multiply and exponentiate.

Another approach is to use a bignum library, but heed newb16's warning about the amount of memory it will take to hold the result.

[jkmyoung]

I think he meant, how many bytes do you want to store the result in? Do you care that it will probably take half your hard disk to store the result?

[himmu7]

I think he meant, how many bytes do you want to store the result in? Do you care that it will probably take half your hard disk to store the result?

i just want the result in 64 bytes

[himmu7]

and dis exponentiation is for RSA algorithm whose modulus value should be 512 bits.

[newb16]

Floating point (12 bit exponent for 64-bit double) will not handle it either.

[himmu7]

Floating point (12 bit exponent for 64-bit double) will not handle it either.

so now how should i handle?

[himmu7]

Floating point (12 bit exponent for 64-bit double) will not handle it either.

i should store this 64 bytes in an array.actually my requirement is RSA encryption. in that for encrypting data C=m^e mod n. this is the formula for that.
now 'm' is the plain text to be encrypted and n is 512 bit modulus value.e is 64 byte Encryption exponent value. so how should i deal this?

[jkmyoung]

Ah! If you had said mod earlier, this entire discussion could have been much shortened.

There are 2 problems:
A. Multiplying a 64 byte number by a 64 byte number and getting the modulus in a 64 byte result.
B. Algorithm for calculating the exponent.


A. I would take the largest unsigned primitive supported by your environment, (long or long long?) and use the primitive half that size for multiplications (cast as the larger type). Store the result in a 128-byte buffer, then calculate the mod of it.


Example. Multiplying a 2-unit number by another 2-unit number.
Eg, if you had ab * cd where each letter represents an unsigned int, the lowest uint would be:
1: low (b*d)
- the next uint would be
2: high(b*d) + low (a*d) + low(b*c).
- the next uint would be
3: remainder (from 2:) + high(a*d) + high(b*c) + low(a*b)
4: remainder (from 3:) + high(a*b)

where low() gets the lowest bits of the result, and high() gets the higher bits of the result.


B. See methods 4 then 5 in
Calculating Large Exponents
The code is pseudocode, and you will have to apply % to your temporary results.

[newb16]

Read a wikipedia article about RSA, implement it using square-and-multiply algorithm and modular exponentiation.

[himmu7]

Ah! If you had say mod earlier, this entire discussion could have been much shortened.

There are 2 problems:
A. Multiplying a 64 byte number by a 64 byte number and getting the modulus in a 64 byte result.
B. Algorithm for calculating the exponent.


A. I would take the largest unsigned primitive supported by your environment, (long or long long?) and use the primitive half that size for multiplications (cast as the larger type). Store the result in a 128-byte buffer, then calculate the mod of it.


Example. Multiplying a 2-unit number by another 2-unit number.
Eg, if you had ab * cd where each letter represents an unsigned int, the lowest uint would be:
1: low (b*d)
- the next uint would be
2: high(b*d) + low (a*d) + low(b*c).
- the next part would be
3: remainder (from 2:) + high(a*d) + high(b*c) + low(a*b)
4: remainder (from 3:) + high(a*b)

where low() gets the lowest bits of the result, and high() gets the higher bits of the result.


B. See methods 4 then 5 in
Calculating Large Exponents
The code is pseudocode, and you will have to apply % to your temporary results.

thank u so much for ur explanation. i forgot to tell the details of base value.
The base value is of 15 bytes length. i have to encrypt 15 bytes length of data.