Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
Ron Rivest, Adi Shamir and Len Adleman
Time Limit: 3000ms, Special Time Limit:7500ms, Memory Limit:32768KB
Total submit users: 11, Accepted users: 10
Problem 11787 : No special judgement
Problem description
  Ronald Linn Rivest,Adi Shamir,还有Leonard Adleman,这三个人的全名也许有点冗长。但是以他们三个人的名字的首字母命名的算法称得上是赫赫有名——RSA公钥加密算法。为了表彰这三个人在RSA加密系统上的贡献,ACM于2002年向他们颁发了图灵奖。
RSA加密算法的流程如下:首先选择2个质数p和q,令n=pq。再计算出r=(p-1)(q-1)。再找到一对数(e, d),关于r互逆,即ed%r=1。将p和q销毁,将(n, e)公布给发送方,(n, d)藏起来给接收方。
假设要发送的信息是m,发送方计算出c=m^e%n,然后发送c。接收方收到c以后,即可计算出m=c^d%n。
使用一个例子来描述如何用RSA加密传递仅含有英文大写字母的信息。假定要传递的信息只有大写字母A~Z,并将其编码为整数0~25。首先选择p=3、q=11,则n=33,r=20,取e=3、d=7。要传输的串为“ACM”,对应的数分别是0、2、12,分别计算出其3次方并对33取模,结果为0、8、12。将0、8、12发送给接收方,接收方再计算其7次方对33取模,得到0、2、12,从而还原出“ACM”这段信息。

Input
  输入有多个案例,每个案例两行。第一行为4个正整数n、r、e、d,保证这四个数可以用于RSA加密,含义如上所述,且26<n<100。第二行为一个仅含大写英文字母的字符串,长度不超过100,为发送方需要发送的信息。发送方会将这段信息经过RSA加密之后发出。当n、r、e、d全为0时表示输入结束。

Output
  每个案例输出一行,为接收方接收到信息后,还原出的源信息。

Sample Input
33 20 3 7
ACM
0 0 0 0
Sample Output
ACM
Problem Source
  HUNNU Contest

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:9459 today,15449748 total, since 2010-05-07