分数的模运算
在ECC加密算法中需要用到对分数的模运算，但大多的资料只给结果没有给计算过程，就连初等数论书上面也不到计算
方法，搜索了一下，终于在网上到了相关资料，用的思路其实还是整数模运算的，直接copy下来
下面是“分数”模运算的定义：
b, m互质（互为素数）
k = a/b (mod m) <=> kb = a (mod m)
这里求 x = 1/17 (mod 2668)
<=>
17x = 1 (mod 2668)
<=>
17x = 2668k + 1 （k∈整数）
取合适的k使得17|(2668k+1)  【应该是17能被(2668k+1)整除,也即17x mod 2668 = 1】
这里刚好17 | (2668 + 1)
所以k = 1, x = (2668+1)/17 = 157
当然，当k = 1 + 17n 时，
x = (2668 + 17·n·2668 + 1)/17 = 157 + 2668n
也符合条件（n任意整数）
但如果限定 2668 > x > 0，x是唯一的。
分数求模（取余）过程 [原创 2008-03-20 20:13:27]   
字号：大 中 小
貌似分数是这样取余的，好好学习，天天向上！
计算a/x(mod n)
a/x (mod n)=a*x^-1(mod n)
计算1/x mod n   
=x^(-1) mod n
就是求y，满足：
yx = 1 mod n
y是有限域F(n)上x的乘法逆元素
可用扩展的欧几里得算法求乘法逆元
int ExtEnclid(int d,int f)       
{
        int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;
    if(d>f) d=d+f-(d=f);  //交换d和f使得d<f
        x1=1,x2=0,x3=f;
        y1=0,y2=1,y3=d;
        while(1)
        {
                if(y3==0)       return 0;       //没有逆元,gcd(d,f)=x3
                if(y3==1)       return y2;      //逆元为y2,gcd(d,f)=1
                k=x3/y3;                                       
                t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3;
                x1=y1,x2=y2,x3=y3;
                y1=t1,y2=t2,y3=t3;
        }
( ) }

int main()
{
        int d,f,res;

        printf("you can try d=550 f=1769, d^-1 = 550, press ctrl+Z to&\n");
        printf("intput the d and f value:\n");
        while(scanf("%d%d",&d,&f)==2)
        {
                printf("Enclid : gcd(%d,%d)=%d\n",d,f,Enclid(d,f));
                res=ExtEnclid(d,f);
                if(res==0)      printf("Not Exist the d^-1\n");
                else
                        if(res>0)       printf("ExtenderEnclid : d^-1 = %d , 
                                         %d * %d = 1 mod %d\n",res,d,res,f);
                        else
                        {
                                printf("ExtenderEnclid : d^-1 = (%d) , 
                                       %d * (%d) = 1 mod %d\n",res,d,res,f);
                                printf("ExtenderEnclid : d^-1 = %d , %d * 
                                          %d = 1 mod %d\n",res+f,d,res+f,f);
                        }
        }
        return 0;
}
用扩展的欧几里德算法简单描述如下：
ExtendedEuclid(d,f)
1 （X1,X2,X3):=(1,0,f)
2  (Y1,Y2,Y3):=(0,1,d)
3  if (Y3=0) then return  d'=null//无逆元
4  if (Y3=1) then return  d'=Y2  //Y2为逆元
5  Q:=X3 div Y3
6  (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3)
7 （X1,X2,X3):=(Y1,Y2,Y3)
8  (Y1,Y2,Y3):=(T1,T2,T3)
9  goto 3
例1：（2/5) mod 17
=2×5^-1 mod 17   (中间的是5的-1次方)
=2×7 mod 17
=14
下面来看一看y=5^-1 mod 17 =7是怎样算出来的（即求5关于17的逆元）：
d
x1
x2
x3
y1
y2
y3
　
1
0
17
0
1
5
3
0
1
5
1
-3
2
2
1
-3
2
-2
7
1
例2：(4/6) mod 17
=4×6^-1 mod 17   (中间的是6的-1次方)
=4×3 mod 17
=12
即求6关于17的逆元：
d
x1
x2
x3
y1
y2
y3
　
如果y2的值最后为负值，还要进行取模运算。
例3：求7关于96的乘法逆元（即7^-1 mod 96）
d
x1
x2
x3
y1
y2
y3
　
1
0
96
0
1
7
13
0
1
7
1
-13
5
1
1
-13
5
-1
14
2
2
-1
14
2
3
-41
1
-41 mod 96 =55 所以55就是7关于96的逆元，让我们检验一下55*7 mod 96 =1
例4: 上节课的题:p=11;g=5;x=3;令m=3，k=2；
解: y=5^3mod11=4
  a=5^2mod11=3
  b=4^2*3mod11=4
b*a^-x(mod p)=4*3^-3(mod 11)=4*27^-1(mod 11)=4*9mod（11）=3
d
x1
x2
x3
y1
y2
y3
　
1
0
11
0
1
27
0
0
1
27
1
0
11
2
1
0
11
-2
1
5
2
-2
1
5
5
-2
1
-2mod（11）=9