计算最接近给定质数 pPrime 的算法
1.46/5 (7投票s)
2007年11月25日
4分钟阅读
46095
169
该算法用于查找最接近给定输入pPrime的素数，对于加密算法非常有用。
引言
这段代码是实现一个算法，用于判断给定的数字pPrime是否为
素数，另外，它会一直运行直到找到最接近给定pPrime的素数。
让我们指出这个算法的一个有用之处：假设你想应用一个
使用素数的加密算法，如RSA加密算法，
可能还有其他方法可以比这种方法更好地找到素数，但是“根据
离散数学科学家（我的导师）”的说法，这种方法很快，所以我应用了这种快速的方法来查找素数（有些人告诉我它并不快，我也这么认为）。
背景
在加密领域，我们定义如下：
P：明文。
C：密文（加密的）文本。
N：模数。
K：“密钥” 一个给定的数字（小于N的整数）< N ，与N 互质。
K'：K的倒数（模N）。
如果我们想使用加密密钥K来加密明文P，并且密钥K的范围
是从1到N，那么我们将得到如下公式：
(P*K)mod N = C。
类似地
(C*K')mod N = P。
问题在于，如果N 是非素数，那么我们需要找到与N互质的每一个数，
这是不切实际的，因为它会减少加密密钥的数量，这可能会导致
算法被暴力破解，所以我们可能需要以下操作：
*选择一个很大的数字N
*找出所有与N互质的数
现在我们可以看到该算法的用途了。一个定理如下：
如果N是素数，那么所有小于N的数（整数）都与N互质。
就是这样！我们只需要找到一个很大的素数，然后加密密钥将是
密钥数量 = N - 1
这样我们就可以消除暴力攻击（BFA）。
更多阅读，更多查找：http://wikipedia.org/
现在很清楚了，该算法找到的那个大素数就是用于加密算法的。
*在使用代码部分有更多解释。
使用代码
代码很简单，是直接实现用于检查素数
并找出素数的实际算法。
让我们看看
我选择26，因为它代表英文字母的数量。
现在给字母A-Z从1到26赋值。
假设我想用密钥15加密字母'C'。
P：'C'
K：15
N：26
C= (P*K) mod 26
如上所述，字母'C'代表2。
那么 C= (2*15) mod 26 = 4，它代表字母'E'。
很酷。
????? P=(C*k')mod 26 吗？????
C：'E'，代表4。
K'：7 为什么？？因为 4*26 + 1 = 105 <===> (k)15 * (k')7 = 105
不管怎样，请查看wikipedia.org。
现在
( 4*7) mod 26 = 2，它代表字母'C'。
问题出现在我们选择8作为密钥或13时，
这两个数字与N（26）有公约数，
因此，加密会出现不可逆映射（wiki..）
也就是说，如果我用密钥8加密某个字母，我可能会得到字母g。
而如果我们使用密钥13，我们将得到相同的字母。
问题！！！
解决方案是选择所有与N（例如26）没有公约数且小于N的密钥值，
它们将是：{1,2,3,5,7,11,13,17,19,23}
这就是我们上面讨论的，密钥数量在减少。
而且查找互质数真的很难，如果N是素数会更好。
然后我们可以使用所有N-1个值作为密钥。通过应用该算法，
我们找到最接近26的素数是29，所以密钥值将是
{1,2,3,4,5,6,.......26,27,28}=N-1
很酷，现在我们可以表示比字母更多的字符了，我们可以添加
例如逗号或星号，当然这里只能添加两个额外的符号{27,28}。
如果我们想一次表示两个字母呢？'AA'或'BZ'。
我们将有26*26种组合{'AA' ,'AB','AC' ...'ZW','ZY','ZZ'}
密钥数量将是676，巧合的是677是一个素数。
但对于(26^3 = 26*26*26 = 17576)一次加密3个字母呢？？
它是一个素数吗？？
幸运！！或者（不幸）……我们有我的代码来检查。
double pPrime,primeRoot;
pPrime=8031810176;//example
start:
primeRoot=System.Math.Floor( System.Math.Sqrt(pPrime));
int counter=0;
bool NotPrime=false;
double [] lessRootPrimeTable=new double[1000000];
for(double possiblePrime=2;possiblePrime<primeRoot;++possiblePrime)
{
for(double p=2;p<possiblePrime;p++)
while((possiblePrime%p)==0)//if
{
NotPrime=true;
break;
}
if(NotPrime==true)
{
NotPrime=false;
continue;}
if(NotPrime==false)
{
lessRootPrimeTable[counter]=possiblePrime;
while((pPrime)%lessRootPrimeTable[counter]==0)
{
//MessageBox.Show("Not Prime");
pPrime++;
goto start;
}
counter++;
}
}
MessageBox.Show(pPrime.ToString());
关注点
这件事将你带入密码学世界，如果我能破解RSA算法，那将是令人惊叹的。
我希望这是开始做这件事的一个好起点。
历史
2007年11月26日：应Fernando的建议，我做了一些更新来修复一些语法和拼写错误。
此外，我想说我很快就会发布一个完整的程序，使用这个算法或另一个更高效的算法来加密和解密一些明文。
2007年11月27日：我已更新代码，它将减少最坏情况。要查看旧代码，请参见上面的附件。