|
用C会比较好,C有个大数运算库,能省略求证的时候对大数进行计算的复杂处理
以下代码是我在试图分解一个RSA的公钥
#include <nbtheory.h>
#include <stdio.h>
#include <windows.h>
#include <sstream>
#include <iostream>
#pragma comment (lib,"./cryptlib.lib")
using namespace CryptoPP;
using namespace std;
Integer mod_exp(Integer a,Integer b,Integer c)
{
Integer res, t;
res = 1 % c;
t = a % c;
while (b.NotZero())
{
if (b % 2==1)
{
res = res * t%c;
}
t = t * t%c;
b = b / 2;
}
return res;
}
Integer exgcd(Integer a, Integer b, Integer *x, Integer *y)
{
if (b == 0) {
(*x) = 1, (*y) = 0;
return a;
}
Integer r = exgcd(b, a%b, x, y);
Integer t = *y;
*y =(*x)- a / b * (*y);
*x = t;
return r;
}
Integer searchUtil(Integer target, Integer l, Integer r)
{
if (l + 1 == r)
return l;
else if (l + 1 < r)
{
Integer m = l + (r - l) / 2;
if (m*m == target)
return m;
else if (m*m < target)
return searchUtil(target, m, r);
else if (m*m > target)
return searchUtil(target, l, m);
}
}
Integer searchSqrtFloor(Integer target)
{
return searchUtil(target, 1, target);
}
unsigned int main()
{
Integer divv("141200934203348100398237203092056603810497665953866503938436185453188653157534841542476799951117838232625775007972565407157639296613520419503480411605352582268797113156766586228582255481135809096970885597928003710586870460226020496368765994413857405308613414568674463104615847526186185331402709548604450804313");
Integer divs("11876433034222735702746321410377879376272094689220724132957900598176502768763874640725383992846504809710949618722994122810563152826799311453851843016297619");
while (1)
{
if (divs % 10 == 7)
{
divs = divs -4;
}
else
{
divs = divs-2;
}
if (IsPrime(divs))
{
cout << dec << divs << endl;
if (divv%divs != 0)
{
continue;
}
else
{
break;
}
}
}
cout <<"find it:"<< dec << divs << endl;
}
|
|