Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 290
  • Last Modified:

help to do calculation

i have three vars, all integer

caled m,e and n
i want to do this calculation in c

m^e mod n

do i need a header, or not what is the exact syntax for this, to get the order of computation correct. thanks kieran
0
kplonk
Asked:
kplonk
  • 7
  • 6
  • 4
  • +3
1 Solution
 
PC_User321Commented:
power(int x, int n)
{
   int  index;
   int  result;

   result = 1;
   for (index = 0; index < n; index++)
      result = result* x;
   return(result);
}

/* To calculate m^e mod n */
answer = power(m, e) % n;


No headers are necessary.
This assumes that e is positive.
If you use large numbers you will have to use larger variable types, e.g. long.
0
 
PC_User321Commented:
Change the first line to
int power(int x, int n)
0
 
hernaniCommented:
Hi,

Although this introduce several casts, it might be the most clean way to do the calculation, since you use the standard libs:

#include <math.h>

answer = ((int) pow((double) m, (double) e)) % n;
0
What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

 
ozoCommented:
int pmod(int m,int e,int n){
  int p;
  if( e == 0 ){ return 1; }
  p = pmod(m,e>>1,n);
  p *= p;
  if( e&1 ){ p *= m; }
  return p%n;
}

answer = pmod(m%n,e,n)
0
 
arnondCommented:
ozo, why 'e>>1' and not simply 'e/2' ? speed ?

Arnon David.
0
 
ozoCommented:
'e>>1' for symmetry with 'e&1', and to raise suspicion about it working with e negative.
('e&1' usually works better than 'e%2' for negative e, but in this case, speed may be the only difference)
I'd have made e unsigned, but the question asked for int
0
 
kplonkAuthor Commented:
E(m)=m^e mod n = c
D(c)=c^d mod n

using e and d =11 and n=35

any value of m should give a value of c and then when c is in the second formual i should get back to m but this dont work, for some reason. is % the mod that i want?
0
 
ozoCommented:
e and d =11 and n=35 should work.
but if you are using PC_User321's or hernani's method, you are probably overflowing an int.
0
 
kplonkAuthor Commented:
yer but is this the correct, version of mod i am not sure that this is the thing that i am looking for, eg if m is 3 and e=11 n=35 then encyrapting gives 12 and decrypting gives 3 all is well, but 4 does not work so i recok ythe mod i asm using is not the correct interpretation of mod. what you reckon.
0
 
ozoCommented:
3^11 % 35 = 12 is correct
12^11 % 35 = 3
4^11 % 35 = 9
9^11 % 35 = 4
But 9^11 = 31381059609, which overflows a 32 bit int,
So you can't use the method proposed by PC_User321 or hernani
0
 
PC_User321Commented:
. unless you heed the warning in the last line of PC_User321's post.
0
 
ozoCommented:
Even a 64 or 128 bit long would not suffice for 34^29
0
 
PC_User321Commented:
Let me rephase that:

My method will work fine.  You must heed the warning on the last, which says "If you use large numbers you will have to use larger variable types, e.g. long."

In particular you should ensure that the types used for 'result' and 'power' can hold the size of the result of the exponentiation.


0
 
PC_User321Commented:
Let me rephase that:

My method will work fine.  You must heed the warning on the last, which says "If you use large numbers you will have to use larger variable types, e.g. long."

In particular you should ensure that the types used for 'result' and 'power' can hold the size of the result of the exponentiation.


0
 
PC_User321Commented:
>> Even a 64 or 128 bit long would not suffice for 34^29

True.
How about a 256 bit long? There might be machines that support it.
People who push the limits must take care.
0
 
ozoCommented:
or if such a type does not exist, you may prefer a method that only requires a type sufficient to hold the size of the result of the mod.
0
 
kplonkAuthor Commented:
i will try with long, i reckon this is the prob
0
 
ozoCommented:
The method I gave you should have no problem with 9^11 mod 35, even if your ints are only 16 bits
0
 
3rsrichardCommented:
Wouldn't
4^5 % 35 = 9
9^5 % 35 = 4
be more in the spirit of things, considering that 5 x 7 = 35 and
(4 x 6) +1 = 25 whose factors are 5?

And you should stick with ozo's method.
0
 
kplonkAuthor Commented:
thanks for all the help
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

  • 7
  • 6
  • 4
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now