从RSA算法中，我了解到，这在某种程度上取决于以下事实：给定大量（A），在计算上不可能从两者推导
不是素数定理，是吗？
这表明没有解$ n $（$ n> 2 $）这样：$ X ^ n + Y ^ n = Z ^ n $。
有人可以对此加以说明吗？
#1 楼
要从头到尾逐步介绍RSA，下面是它的工作原理。选择两个大的素数$ p $，$ q $。计算$ n = pq $。
计算$ \ phi（pq）$。这恰好是$（p-1）（q-1）$。
选择$ e $使得$ gcd（e，\ phi（pq））= 1 $并且$ 1
进行一些加密; $ c = t ^ e \ mod n $和$ t = c ^ d \ mod n $。
您真正想知道的是为什么这些语句成立。费马小定理指出，$ a ^ p =一个\ mod（p）$。另一种等效的定义是$ a ^ {p-1} = 1 \ mod（p）$。
实际上，对于RSA而言，这还不够。您想要的是称为Euler-Fermat概化的概化，它指出：
$$ a ^ {\ phi（n）} = 1 \ mod {n} $$
下一步-这个$ \ phi（x）$函数到底是什么？用简单的英语来说，它是小于或等于$ x $的数字数量，它们也是互质的。对于任何给定的质数$ p $，每个小于其本身的数字都是互质数，这意味着$ \ phi（p）= p-1 $。如果您想知道为什么$ \ phi（1）= 1 $，那么$ gcd（x，1）= 1 $是共素性的定义，包括1本身。
现在，也有可能证明$ \ phi（xy）= \ phi（x）\ phi（y）$。除非有人真的希望我这样做，否则我将跳过详细信息（请参阅有关数论的教科书），但这实际上意味着$ n = pq \ Rightarrow \ phi（n）= \ phi（p）\ phi（q）\ Rightarrow \ phi（n）=（p-1）（q-1）$。
现在，也有一些小组理论。某些正整数集的乘法在模下形成一个组，条件是您为其选择的所有元素都是所用模的互质。碰巧我们选择了$ e $作为模$ \ phi（pq）$的互质数。群论向我们保证了群中存在一个整数，该整数作为该整数的唯一逆，并在相乘后将该整数转换为恒等式。乘法下的标识元素为$ 1 $，此处的倒数为$ d $。
因此，让我们回顾一下：我们有$ e $，我们有$ d $。一个是组\\ phi（n）$下另一个的逆。我们需要的是一个指向Euler Fermat概括的链接，该链接显示如下：
$$ t =（（t ^ e）^ d）= t ^ {ed} \ mod（n）$$
所以，在我们这样做之前，让我们先回顾一下我们对一致性的理解。如果我有数字$ 4 \ mod（9）$，您是否高兴$ 13 = 4 \ mod（9）$？那22美元= 4 \ mod 9 $？那$ 31 = 4 \ mod（9）$？您应该会在这里看到一种模式。实际上，在这种情况下，您的一般表示形式是$ 4 + 9k $会生成与$ 4 $模$ 9 $等价的一组数字。
因此，$ de = 1 \ mod \ phi（pq ）$可以表示为$ de = 1 + k \ phi（pq）$，是吗？即到1，我可以加上$ \ phi（pq）$的倍数，然后应用$ phi（pq）$取模，它等于1。
这可能需要一些时间。
到达目的地后，$ t ^ {ed} = t ^ {1 + k \ phi（pq）} \ mod（pq）$。我所做的只是将一个表达式替换为另一个。没有魔法。现在重新排列一下：$ t ^ {1 + k \ phi（pq）} = t ^ 1 t ^ {k \ phi（pq）} \ mod（pq）$然后是$ t ^ {1} t ^ { k \ phi（pq）} = t ^ 1（t ^ {\ phi（pq）}）^ k \ mod（pq）$。
现在，我们使用Euler-Fermat概化。注意，我们有$ t ^ {\ phi（pq）} \ mod（pq）$。由于处于“模”状态，我们仍然可以对此进行评估，因为$ k $的幂只是意味着将$ k $大量的该表达式相乘。因此，现在应用定理：
$$ t ^ {\ phi（pq）} = 1 \ mod（pq）$$
，我们剩下的是$ t ^ 1（t ^ {\ phi（pq）}）^ k = t ^ 1 \ times（1）^ k \ mod（pq）$，您可能只知道$ t $。
所以，这就是它们之间的联系。这也不是证明RSA的唯一方法。我认为中国余数定理证明更好，但我也觉得很难理解。
#2 楼
$ X ^ n + Y ^ n = Z ^ n $（即，不可能使用$ n> 2 $和$ X，Y，Z> 1 $的情况）被称为“费马定理（大）定理”保证金还不够大）。但是对于RSA理论重要的定理被称为“费马小定理”：$$ a ^ p \ equiv a \ mod p \ text {（如果$ p $ prime）} $$
或同等值（对于素数$ p $和$ a
$$ a ^ {p-1} \ equiv 1 \ mod p $$
这是由欧拉定理针对所有整数（而不仅仅是素数）推广的：
$$ a ^ {\ phi（n）} \ equiv 1 \ mod n $$
如果让$ n = p $（$ p $素数），则$ \ phi（p）= p -1 $。这表示为“如果$ p $是质数，则与$ p $互质的$ 1 $和$ p $之间的数字数量为$ p-1 $”。
使用在RSA中：我们选择两个大质数$ p $和$ q $，$ n = p·q $，然后计算$ \ phi（n）$等于$（p-1）（q-1）$ 。之所以成立，是因为如果$ p $和$ q $都是素数，则$ p $的互质数也是$ q $的互质数，反之亦然（两者的倍数除外），因此$$ \ phi（n）= \ phi（p·q）= \ phi（p）·\ phi（q）=（p-1）（q-1）。$$然后我们得出公共和私有指数，也就是公共和私钥，来自此$ \ phi（n）$。
#3 楼
不，那不是费马定理。这是费马小定理，其中指出如果$ p $是素数，则$ a ^ p $与$ a $模$ p $是一致的。
证明RSA算法的正确性需要这个定理（也需要中文余数定理）。任何涵盖RSA的介绍性文字都应涵盖这一点（以及任何不值得在其上打印论文的介绍性文字）。
从RSA算法中，我知道它在某种程度上取决于在给定大质数（A）的情况下，不可能从计算得出其乘积为两个质数（B＆C）的事实。
这是不正确的。一个质数不可能是另外两个质数的乘积。而是模量$ n $是两个大素数的乘积，通常称为$ p $和$ q $。
#4 楼
我想你的意思是
Fermat's Little Theorem。上面的答案很详细，但是
they are incomplete。这是
supplement to the above answers。>
为了指出问题，我们首先回顾欧拉定理。
欧拉定理如果$ n \ ge 1 $和$ gcd（a，n）= 1 $，则$ a ^ {\ varphi（n）} \ equiv 1 \ pmod n $。
如果$ p $是质数，$ \ varphi（p）= p-1 $，我们得到费马小定理。
费马小定理假设$ p为素数，并假定$ p \ not | a $。然后$ a ^ {p-1} \ equiv 1 \ pmod p $
根据欧拉定理，上述答案中有一个隐含条件。
$ $ t ^ {ed} \ equiv t \ pmod {（pq）} $$
隐式条件是$ gcd（t，pq）= 1 $，然后是$ t ^ { ed} \ equiv t ^ {k \ varphi（pq）+1} \ equiv t \ pmod {pq} $
但是如果$ gcd（t，pq）\ not = 1 $怎么办？例如$ t = r \ cdot p $或$ t = s \ cdot q $。
现在我们证明情况$$ t ^ {ed} \ equiv t \ pmod {（pq）}，gcd（t，pq）\ not = 1 $$
不使用中国余数定理的简单方法。
首先，我们给出一个定理。它位于《基础数字理论》第6卷第4.9.1节中。
结论4.9.1如果$ a \ equiv b \ pmod {m_1}，a \ equiv b \ pmod {m_2}，...，a \ equiv b \ pmod {m_k } $，其中$ a $和$ b $是整数，而$ m_1，m_2，...，m_k $是成对的相对素数正整数，则$$ a \ equiv b \ pmod {m_1m_2 \ cdot \ cdot \ cdot \ cdot m_k }。$$
所以，如果
$$ t ^ {ed} \ equiv t \ pmod {p} $$
$$ t ^ {ed} \ equiv t \ pmod {q} $$
$$ gcd（p，q）= 1 $$
因此
$$ t ^ {ed} \ equiv t \ pmod {（pq）} $$
因为$ p $和$ q $是在平等的基础上，我们仅证明：
$$ t ^ {ed} \ equiv t \ pmod {p} $$
这是要证明的命题：
假设$ p $和$ q $为素数，并假设$ gcd（t，pq）\ not = 1 $，$ e \ cdot d = k \ varphi（pq）+ 1 $，则$$ t ^ {ed} \ equiv t \ pmod {p} $$
证明：
1。假设$ t \ not \ equiv 0（mod \ p）\ Rightarrow gcd（t，p）= 1 $
因此$$ t ^ {ed} \ equiv t ^ {k \ cdot \ varphi（n）+1} \ equiv t ^ {k（p-1）（q-1）+1} \ equiv t（t ^ {p-1}）^ {k（q -1）} \ pmod p $$
因为$ gcd（t，p）= 1 $，由费马小定理$$ t ^ {p-1} \ equiv 1 \ pmod p $$
因此$$ t ^ {ed} \ equiv t（t ^ {（p-1）}）^ {k（q-1）} \ equiv t \ cdot 1 ^ {k（q-1）} \ pmod p $ $
因此$$ t ^ {ed} \ equiv t \ pmod p $$
2。假设$ t \ equiv 0 \ pmod p $
因此
$$ t ^ {ed} \ equiv 0 ^ {ed} \ equiv 0 \ equiv t（mod \ p）$$
因此，我们证明了命题：
$$ t ^ {ed} \ equiv t \ pmod {p} $$
以同样的方式：
$$ t ^ {ed} \ equiv t \ pmod {q} $$
通过推论4.9.1：
$$ t ^ {ed} \ equiv t \ pmod {（pq）} $ $
评论
$ \ begingroup $
事实是phi函数是可乘的，在phi函数的Wikipedia页面上，使用中文余数定理几乎没有什么证明。
$ \ endgroup $
–pg1989
2011年12月9日在22:02
$ \ begingroup $
这是一些书籍和原始文章中所述的RSA。由PKCS＃1标准化并使用的RSA允许使用$λ（n）= \ operatorname {lcm}（p-1，q-1）$而不是$ ϕ（n）$，因此可以使用降低$ d $，通常快一点。而且，最重要的是，加密不是$t↦c= t ^ e \ bmod n $，它在这个有限的空间中存在太多的安全问题，无法列出。
$ \ endgroup $
–fgrieu♦
13年4月12日在18:36
$ \ begingroup $
非常清楚，易于理解的解释-但忽略了欧拉定理-因此，证明-仅适用于相对于'p * q'的素数't'
$ \ endgroup $
–staafl
13年4月21日在19:48