学步园

当b好大时，使用该算法是最好的选择。常应用于密码学：

代码：

/*
File:                 abn.c
Description:          求 a的b次方模n的通用算法
Author:               hanxi
*/

#include <stdio.h>
#include <math.h>

int f(int a, int b, int n)
{
    int c=0, d=1;
    int i;
    for (i=31; i>=0; i--)
    {
        d = (d*d) % n;
        c *= 2;
        int tmp;
        tmp = 1<<i;
        //printf("tmp=%d\n",tmp);
        if ((b&tmp)!=0)
        {
            d = (d*a) % n;
            c++; 
        }
    }
    return d;
}

int main()
{
    int a = 2, b = 5, n = 10;
    printf("求a的b次方模n\n");
    printf("请输入a,b,n（用逗号隔开，如果a,b,n全为0则退出系统）:");
    scanf("%d,%d,%d",&a,&b,&n);
    printf("a=%d,b=%d,n=%d\n",a,b,n);
    while (a!=0 && b!=0 && n!=0)
    {
        int d = f(a,b,n);
        printf("%d的%d次方模%d=%d\n",a,b,n,d);
        int x = pow(a,b);
        printf("%d的%d次方模%d=%d\n",a,b,n,x%n);
        printf("请输入a,b,b（用逗号隔开）：");
        scanf("%d,%d,%d",&a,&b,&n);
        printf("a=%d,b=%d,n=%d\n",a,b,n);
    }
    printf("程序已结束...");
    return 1;
}