# 14005: 【原4005】RSA

### 题目描述

author: 张羽兮 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4005

# RSA

## Description

RSA算法可以算是目前最著名的公钥加密算法，其原理为求两个数的乘积(p * q = N)容易而对一个数分解质因数难（N = p * q)。其加密/解密过程如下： 假设我们需要传递的信息是x，我们通过选取合适的N和e得到加密的信息 y = x ^ e mod N。其中N和e的要求为： ①N=pq，p, q为两个质数； ②gcd(e, (p-1)(q-1))=1，即e与(p-1)(q-1)互质（最大公约数为1）。 而破解该信息的方法根据这样一个公式：x = y ^ d mod N = (x ^ e) ^ d mod N, 其中d满足 ed = 1 mod (p-1)(q-1)。 dzm同学学习了RSA算法之后若有所悟：原来想要破解信息y只需要求得所给e和N对应的d就可以了。他已经知道了如何从N求出p和q，但他不知道怎么通过e，p，q求出d。于是他来问lty，lty随手写了段伪代码给dzm,并且说：你用这段扩展欧几里得算法求得的(x, y, r) = extend-Euclid(e, （p-1)(q-1)) 中的x就是你需要的d了。

## Code

``````function extended-Euclid(a, b)
{
//Input: Two positive integers a and b with a >= b >= 0
//Output: Integers x, y, d such that d = gcd(a, b) and ax + by = r
if b = 0 then return (1, 0, a)
(x, y, r) = extended-Euclid(b, a mod b)
return (y, x - [a / b] * y, r);
}
``````

dzm听说最近czc给wkn发了段RSA加密信息（据说和期末考试题有关），想尝试破解出这段信息（说不定有考题哦）。不过他不太确定自己破解的是不是正确，所以希望你也帮他破解一下。

## Sample Input 1

``````52 55 3 1
``````

## Sample Output 1

``````13 27
``````

## Sample Input 2

``````8 15 7 0
``````

## Sample Output 2

``````2
``````

## HINT

1. zyx悄悄告诉你，如果想让一个函数返回多个值，可以使用结构体struct
2. 本题只是给出了RSA算法的相关结论和公式，有关其证明有兴趣的同学可以在网上查找相关资料或查阅《算法概论》第一章。
3. 扩展欧几里得算出的d可能为负数

## Oops! 本题目还没有解答！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
{"ft_lang_label":"__label__zh","ft_lang_prob":0.87421525,"math_prob":0.99284035,"size":1444,"snap":"2022-27-2022-33","text_gpt3_token_len":1039,"char_repetition_ratio":0.08055556,"word_repetition_ratio":0.0,"special_character_ratio":0.31925207,"punctuation_ratio":0.113970585,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9704213,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-07-06T09:28:03Z\",\"WARC-Record-ID\":\"<urn:uuid:deb7205e-a333-4c8f-ba59-266093f79f6a>\",\"Content-Length\":\"16687\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:86e70324-fe87-4377-b542-a33533d11e15>\",\"WARC-Concurrent-To\":\"<urn:uuid:095e2427-a664-4c4d-97df-2c77de2f967b>\",\"WARC-IP-Address\":\"104.21.94.153\",\"WARC-Target-URI\":\"https://oj.sjtucs.com/nr/14005/\",\"WARC-Payload-Digest\":\"sha1:2ZBGPLDU6CLIUZ3IXDTDGVIZ7UXNKBNT\",\"WARC-Block-Digest\":\"sha1:7FYTKGMMIA4KRTD3HRRFMV45AC7SAFEN\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-27/CC-MAIN-2022-27_segments_1656104669950.91_warc_CC-MAIN-20220706090857-20220706120857-00279.warc.gz\"}"}