Modular exponentiation. The powerMod function computes modular expo- nentiationn

Question

Modular exponentiation. The powerMod function computes modular expo- nentiationne modmwheren,e,andmareintegers,andn>0,e>0,andm>1.

The following is the pseudocode for powerMod. Note that the function returns 1 on invalid input.

FUNCTION powerMod(n, e, m)
IF any of n, e, or m is invalid THEN

RETURN 1

result = 1

WHILE (e > 0)
IF e is odd THEN

result = (result n) mod m e=e/2

n = (n n) mod m RETURN result

Write a C program powerMod.c that prompts the user for three positive integers n, e, and m and then prints to the standard output the integer ne mod m. The program should work with any integers less than 231 1.

The block below shows an execution of the program at the command line.

Explanation / Answer

#include <stdio.h>

int powerMod (int n, int e, int m)
{
    int result = 1;
    if (n<=0 || e<=0 || m<=1)
    {
        return -1;
    }
    n = n%m;
    while (e>0)
    {
        if (e & 1)
        {
            result = (result * n) % m;
        }
        e = e/2;
        n = (n*n) %m;
    }
    return result;
}
int main()
{
    int n, e, m;
    int ret;
    printf ("Please enter n,e and m:");

    scanf ("%d%d%d", &n, &e, &m);
    ret = powerMod (n, e, m);

    printf ("%d^%d mod%d = %d ", n, e, m, ret);
    return 0;
}

OUTPUT:

---------------

[root@localhost rnd]# ./powerMod
Please enter n,e and m:123 456 789
123^456 mod789 = 699
[root@localhost rnd]#

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.