Solved

help to do calculation

Posted on 2000-03-08
20
277 Views
Last Modified: 2012-03-15
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
Comment
Question by:kplonk
  • 7
  • 6
  • 4
  • +3
20 Comments
 
LVL 5

Expert Comment

by:PC_User321
ID: 2598514
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
 
LVL 5

Expert Comment

by:PC_User321
ID: 2598530
Change the first line to
int power(int x, int n)
0
 

Accepted Solution

by:
hernani earned 10 total points
ID: 2598721
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
 
LVL 84

Expert Comment

by:ozo
ID: 2598985
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
 
LVL 3

Expert Comment

by:arnond
ID: 2599504
ozo, why 'e>>1' and not simply 'e/2' ? speed ?

Arnon David.
0
 
LVL 84

Expert Comment

by:ozo
ID: 2599577
'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
 

Author Comment

by:kplonk
ID: 2602333
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
 
LVL 84

Expert Comment

by:ozo
ID: 2603195
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
 

Author Comment

by:kplonk
ID: 2608371
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
 
LVL 84

Expert Comment

by:ozo
ID: 2608395
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
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
LVL 5

Expert Comment

by:PC_User321
ID: 2608503
. unless you heed the warning in the last line of PC_User321's post.
0
 
LVL 84

Expert Comment

by:ozo
ID: 2608539
Even a 64 or 128 bit long would not suffice for 34^29
0
 
LVL 5

Expert Comment

by:PC_User321
ID: 2608542
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
 
LVL 5

Expert Comment

by:PC_User321
ID: 2608549
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
 
LVL 5

Expert Comment

by:PC_User321
ID: 2608551
>> 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
 
LVL 84

Expert Comment

by:ozo
ID: 2608552
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
 

Author Comment

by:kplonk
ID: 2608564
i will try with long, i reckon this is the prob
0
 
LVL 84

Expert Comment

by:ozo
ID: 2608589
The method I gave you should have no problem with 9^11 mod 35, even if your ints are only 16 bits
0
 
LVL 3

Expert Comment

by:3rsrichard
ID: 2617467
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
 

Author Comment

by:kplonk
ID: 2694916
thanks for all the help
0

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now