首页 > ACM题库 > HDU-杭电 > HDU 1211 RSA-数论-[解题报告] C++
2013
12-04

HDU 1211 RSA-数论-[解题报告] C++

RSA

问题描述 :

RSA is one of the most powerful methods to encrypt data. The RSA algorithm is described as follow:

> choose two large prime integer p, q
> calculate n = p × q, calculate F(n) = (p – 1) × (q – 1)
> choose an integer e(1 < e < F(n)), making gcd(e, F(n)) = 1, e will be the public key
> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key

You can encrypt data with this method :

C = E(m) = me mod n

When you want to decrypt data, use this method :

M = D(c) = cd mod n

Here, c is an integer ASCII value of a letter of cryptograph and m is an integer ASCII value of a letter of plain text.

Now given p, q, e and some cryptograph, your task is to "translate" the cryptograph into plain text.

输入:

Each case will begin with four integers p, q, e, l followed by a line of cryptograph. The integers p, q, e, l will be in the range of 32-bit integer. The cryptograph consists of l integers separated by blanks.

输出:

For each case, output the plain text in a single line. You may assume that the correct result of plain text are visual ASCII letters, you should output them as visualable letters with no blank between them.

样例输入:

101 103 7 11
7716 7746 7497 126 8486 4708 7746 623 7298 7357 3239

样例输出:

I-LOVE-ACM.

 

RSA is one of the most powerful methods to encrypt data. The RSA algorithm is described as follow:

> choose two large prime integer p, q
> calculate n = p × q, calculate F(n) = (p – 1) × (q – 1)
> choose an integer e(1 < e < F(n)), making gcd(e, F(n)) = 1, e will be the public key
> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key

You can encrypt data with this method :

C = E(m) = me mod n

When you want to decrypt data, use this method :

M = D(c) = cd mod n

Here, c is an integer ASCII value of a letter of cryptograph and m is an integer ASCII value of a letter of plain text.

Now given p, q, e and some cryptograph, your task is to "translate" the cryptograph into plain text.

 

Input
Each case will begin with four integers p, q, e, l followed by a line of cryptograph. The integers p, q, e, l will be in the range of 32-bit integer. The cryptograph consists of l integers separated by blanks.
 

Output
For each case, output the plain text in a single line. You may assume that the correct result of plain text are visual ASCII letters, you should output them as visualable letters with no blank between them.
 
题意:给出p,q,e 和c的个数,求M(即文本的ASCII码值);
解题思路:1、求M,必须先求d,而d*e mod F(n)=1 mod F(n),其中F(n)=(p-1)*(q-1);这就是模线性方程 a*x=b(% n);  a=e,b=1,n=F(n);
                   用模线性方程求出d;
                  2、再求 M = D(c) = cd mod n;即求同余幕,这也是整数运算中的一个比较有名的算法。
#include<iostream>
#include<cmath>
using namespace std;
__int64 modular(__int64 b,__int64 n,__int64 m)//求同余幕
{
    __int64 x=1,power=b%m;
    __int64 temp=n;
    int a[65];
    int k=0,i;
    while(temp>0)
    {
        a[k++]=temp%2;
        temp/=2;
    }
    for(i=0;i<k;i++)
    {
        //printf("%d\n",a[i]);
        if(a[i]==1)
            x=(x*power)%m;
        power=(power*power)%m;
    }
    return x;
}
__int64 extgcd(__int64 a ,__int64 b,__int64 &x,__int64 &y)//扩展欧几里算法
{
    if(b==0)
    {
        x=1;y=0;return a;
    }
    __int64 d=extgcd(b,a%b,x,y);
    __int64 t=x; x=y; y=t-a/b*y;
    return d;
}
__int64 modeq(__int64 a,__int64 b,__int64 n)//求线性方程
{
    __int64 e,i,d,x,y;
    d=extgcd(a,n,x,y);
    //printf("%I64d %I64d %I64d %I64d\n",b,d,x,y);
    if(b%d>0)printf("No answer!\n");
    else
    {
        e=(x*(b/d))%n;
        i=0;
        while(((e+i*(n/d))%n)<0)
        {
            i++;
        }
        return (e+i*(n/d))%n;
    }
    return -1;
}
int main()
{
    __int64 p,q,e,l,d,n,m,c;

    //m=modular(2,644,645);
    //printf("%I64d\n",m);
    while(scanf("%I64d %I64d %I64d %I64d",&p,&q,&e,&l)!=EOF)
    {
        n=p*q;
        d=modeq(e,1,(p-1)*(q-1));
        //printf("%I64d\n",d);
        for(int i=0;i<l;i++)
        {
            scanf("%I64d",&c);
            m=modular(c,d,n);
            printf(i<l-1?"%c":"%c\n",m);
        }
    }
    return 0;
}

  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。