相关疑难解决方法(0)

我想计算一个用于RSA解密的^b mod n.我的代码(如下)返回错误的答案.这有什么问题？

unsigned long int decrypt2(int a,int b,int n)
{
    unsigned long int res = 1;

    for (int i = 0; i < (b / 2); i++)
    {
        res *= ((a * a) % n);
        res %= n;
    }

    if (b % n == 1)
        res *=a;

    res %=n;
    return res;
}

有人能告诉我一个好的C++库,用于处理(执行操作等等)任意大数(它可以是一个处理任意精度浮点数的库,但处理整数更重要)？

请只引用您使用的资料库,并告诉我你是怎么设法设置它,并把它捡起来,也许一个非常简约的例子或东西(基本上,如果提到图书馆没有良好的文档提供一些自己的输入).

为了记录,我在x64机器上使用Windows 7,CodeBlocks作为我的IDE,最新的MinGW作为编译器.

我试过的图书馆:

• vlint(操作不够,但对于小东西工作正常)

• bigint(易于设置,编译错误和文档不多(可能从中导出错误))

• ttmath(看起来很有前途,编译了一些BIG示例程序,并且由于编译错误而导致一些修复后运行,因为几乎没有文档,所以语法难以理解)

• gmp(甚至无法设置)

ps删除了"问题的咆哮部分",基本上解释了为什么我在Stackoverflow上问了很多次问题,所以人们会把它读到最后.

- >更新

所以我选一个答案,这不是直接回答我最初的问题,但对我帮助很大,解决这一点,我会发布一些我的调查结果,以帮助其他的C++新手跟我一样开始使用非常大的数字,工作没有挣扎几天的图书馆像我一样一步一步地进行微观指导.

我正在使用的东西(请记住遵循指南):

• Windows 7旗舰版x64

• Amd k10 x64(有些库不适用于此,其他库的行为会有所不同,其他库会自定义为amd k10,因此这不仅可以帮助您使用我使用的库,还可以帮助您使用其他库)

• Code :: Blocks 10.05包含MinGW的版本,文件名"codeblocks-10.05-setup.exe"(安装在C:\ Program Files(x86)\ CodeBlocks上)

• MinGW包(binutils-2.15.91-20040904-1.tar.gz gcc-core-3.4.2-20040916-1.tar.gz gcc-g ++ - 3.4.2-20040916-1.tar.gz mingw-runtime- 3.11.tar.gz w32api-3.8.tar.gz)在C:\ MinGW上提取

• TTMath 0.9.2文件名"ttmath-0.9.2-src.tar.gz"解压缩并将文件夹"ttmath"复制到文件夹"C:\ CPPLibs"(这是我将我的c ++库放入的文件夹)

怎么做才能把它全部搞定

• 转到代码:Blocks> Settings> Compiler and Debugger(我的编译器在这里自动检测到.如果你没有这样做,请在"Selected Compiler"上选择"GNU GCC Compiler"并点击"Set as Default"然后点击"Toolchain" Exectables"on"编译器安装目录你可以选择编译器的安装目录或尝试自动检测"并在"C++编译器"上进行排序"选择或写入"mingw32-g ++.exe".如果发生这种情况,你只需要做在"Selected Compiler"中选择"GNU GCC Compiler"并单击"Set as Default").

• 在不离开"代码:块>设置>编译器和调试器"的情况下,按照上面的解决方法,转到"搜索目录",然后单击"添加",选择"存储库"或"放置"的位置. ttmath"文件夹(在我的情况下为C:\ CPPLibs)然后转到"链接器"并执行相同的操作.

• 首先,你必须把该行的"ttmath"编码库#include <ttmath/ttmath.h>的主要功能之前(注:如果您使用的是64位系统,你会得到很多的错误,如果你不还,就把这行#define TTMATH_DONT_USE_WCHAR 之前 …

我必须把这个公式变成java代码:

如果我可以使用像Math.BigInteger这样的库会更容易,但遗憾的是我应该在没有它的情况下这样做.stackoverflow上的一些类似问题建议编写一个自己的bignum库,但我想在没有它的情况下这样做.

现在,我的进展是在这一步:

int h(String s) {
  long value = 1;
  int mod = ht.length;

  for (int i=0; i < s.length()-1; i++) {
     h += s.charAt(i) * Math.pow(256,i);
  }
  return (int) h % mod;
}

我知道功率的值在整数范围内变得非常快,所以我想到编写一个自己的方法来计算值的功率和模数.我的数学知识还不足以知道何时使用模数以及如何简化事物.

提前致谢!

我想验证是否

pow(a,b)%b == a

在C中为真,2≤b≤32768(2 ¹⁵)且2≤a≤b,a和b为整数.

但是,直接计算pow(a, b) % bb是一个大数字,这将很快导致C溢出.什么是验证这种情况是否成立的技巧/有效方法？

这个问题是基于找到费马小定理的证人,该定理指出如果这个条件是假的,那么b不是素数.

此外,我在可能的时间也受到限制,它不能太慢(接近或超过2秒).最大卡迈克尔号码,号码b,这不是素数,而且不满足pow(a, b)% b == a与2 <= a <= b(用b <= 32768)是29341.因此,对于检查方法pow(a, b) % b == a具有2 <= a <= 29341不应该太缓慢.

在C/C++我怎样才能计算(a^b)%m其中b不适合64位？换句话说,有没有办法用b%m而不是b？来计算上述值.

是否有任何算法可以在O(log(b))时间或O(log(b%m))时间计算上述结果？