我有四个无符号的32位整数,表示无符号的128位整数,以小端顺序表示:
typedef struct {
unsigned int part[4];
} bigint_t;
我想将此数字转换为十进制字符串表示形式并将其输出到文件中.
现在,我正在使用一个bigint_divmod10函数将数字除以10,跟踪余数.我重复调用此函数,将余数作为数字输出,直到数字为零.这很慢.这是最快的方法吗？如果是这样,有没有一种聪明的方法来实现我没有看到的这个功能？我试过看GMP get_str.c,但我发现它非常难以理解.
编辑:这是我能够为divmod10函数提供的最快的代码:
static unsigned uint128_divmod10(uint128 *value)
{
unsigned int a = value->word[3];
unsigned int b = value->word[2];
unsigned int c = value->word[1];
unsigned int d = value->word[0];
unsigned int diva = a / 5;
unsigned int divb = b / 5;
unsigned int divc = c / 5;
unsigned int divd = d / 5;
value->word[3] = diva;
value->word[2] = divb;
value->word[1] = divc;
value->word[0] = …我正试图弄清楚如何从头开始实施RSA加密(仅用于智力练习),我坚持这一点:
对于加密,c = m e mod n
现在,e通常是65537.m和n是1024位整数(例如128字节数组).对于标准方法来说,这显然太大了.你会如何实现这个？
我在这里读了一些关于取幂的内容,但它并没有点击我:
本章(见第14.85节)
谢谢.
编辑:也发现了这个 - 这是我应该看的更多吗？维基百科 - 模块化指数
我正在尝试为bignums实施长期划分.由于嵌入式编程的局限性,遗憾的是我无法使用像GMP这样的库.此外,我希望学习如何实施它的智力练习.到目前为止,我已经使用任意长度的字节数组完成了加法和乘法运算(所以每个字节就像一个基数为256的数字).
我只是想开始实施除法/模数,我想知道从哪里开始？我在网上发现了很多高度优化(又名不可读)的代码,这对我没有帮助,而且我发现了很多高技术的数学白皮书,我无法弥合理论与实现之间的差距. .
如果有人可以推荐一个流行的算法,并指出一个简单易懂的解释,倾向于implmenentation,那就太棒了.
-edit:我需要的算法在被除数为~4000位时有效,除数为~2000位
-edit:这个算法能用base-256吗？http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html
-edit:这是我真的应该使用的算法(牛顿师)吗？http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division
2 ^ 64离我的ram /硬盘可以处理的"无限"还有一段距离......
首先我想知道GMP如何与内存/处理器一起工作,因为它做了一些阴暗的优化......
我还想知道是否有一种方法可以在任意数量的字节上存储一个整数(无符号,更容易).例如,在50个字节上,我的上限为2 ^ 400 -1.要做的是使用携带以保持数字从一个字节到另一个字节保持一致,我对此有一些了解,但我真的不确定它是最快的方法.我甚至不确定我是否正确.
我猜GMP使用这种方式来存储它的数据,但我只想要一些(甚至很少)解释或某些理论转发(我没有任何博士学位,所以不要太难).
似乎GMP只提供了mpf(浮点)类型的字符串序列化:
mpf_get_str(), mpf_class::get_str()
mpz(整数)类型具有原始字节的附加接口: mpz_out_raw()
http://gmplib.org/manual/Function-Index.html
我错过了什么吗？有谁知道另一个可以序列化GMP浮点数的库？有谁知道另一个提供强大序列化的bignum lib？
编辑:我很高兴序列化MPFR的mpfr_t,同样似乎只提供字符串输出:http://www.mpfr.org/mpfr-current/mpfr.html#Function-Index
如果它是密码学中的32位操作系统,系统如何执行2 ^ 56模7？
它是如何存储在内存中的？
我正在使用加密技术,需要使用一些非常大的数字.我还使用新的Intel指令进行无进位乘法,这需要m128i数据类型,这是通过加载一个以浮点数据作为参数的函数来完成的.
我需要存储2 ^ 1223整数,然后将其平方并存储该值.
我知道我可以使用GMP库,但我认为创建两个存储2 ^ 1224和2 ^ 2448等值的数据类型会更快.它将有更少的开销.我将使用karatsuba乘以数字,所以我需要对数据类型执行的唯一操作是添加,因为我将打破数字以适应m128i.
有人可以指导我的方向,可以帮助我创建我需要的整数的大小.
我正在尝试哈希一个BigInteger/BigNum,我在Android/iOS上得到了不同的结果.我需要获得相同的Hash结果,以便两个应用程序按照SRP协议工作.仔细观察它对正数很好,但不适用于负数(第一个半数大于7).不确定哪一个是正确的,哪一个要调整以匹配另一个.
安卓:
void hashBigInteger(String s) {
try {
BigInteger a = new BigInteger(s, 16);
MessageDigest sha = MessageDigest.getInstance("SHA-256");
byte[] b = a.toByteArray();
sha.update(b, 0, b.length);
byte[] digest = sha.digest();
BigInteger d = new BigInteger(digest);
Log.d("HASH", "H = " + d.toString(16));
} catch (NoSuchAlgorithmException e) {
throw new UnsupportedOperationException(e);
}
}
iOS版:
void hashBigNum(unsigned char *c) {
BIGNUM *n = BN_new();
BN_hex2bn(&n, c);
unsigned char buff[ SHA256_DIGEST_LENGTH ];
int len = BN_num_bytes(n);
unsigned char * bin = (unsigned char *) malloc( …当我使用 truffle 开发智能合约时，每当从 truffle 控制台请求一些数字（例如帐户余额或地址）时；我收到一个 BN 对象，如下所示：
BN {
negative: 0,
words: [ 37748736, 3305132, 2220446, <1 empty item> ],
length: 3,
red: null
}
该对象是bn.js库的一部分。但我无法找到任何有关如何解释该对象的文档。
我怎么读这个。我想了解该对象中每个字段的含义，并能够手动将其转换为正常数字。
是否有一些数学"最佳"基础可以加速因子计算？
背景:为了好玩,我正在实施我自己的bignum库.( - :这是我的第一个错误吗？:-).我正在通过打印n阶乘(n!)的精确值(十进制)来试验内部表示和回归测试中使用的各种基数.
我的bignum库表示整数并进行乘法的方式,时间与内部表示n!中"1"位的总数成正比.在我的内部表示中使用基数2,4,8,16,2 ^ 8,2 ^ 30等都给出了与任何特定数字完全相同的"1"位总数.
除非我做了一些错误,任何给定的阶乘(N!)在基地18代表具有比在基地10或或基地16或19基地等等(原则)表示相同的值较少的"1"位,使用基础18会使我的bignum库比使用base 10或某些二进制2 ^ w base或base 19运行得更快.我认为这与n这个事实有关!或者是短或具有更多的"尾随零"或两者时在基部18比底座10打印出来,或或基座16或基座19有一些其他,将工作比基部18甚至更好的基础？换句话说,是否存在代表n的基数!比基数18更少的"1"位？
这不是"bignum库和素性测试算法的便利基础是什么？" 因为我怀疑"的最佳基地与被称为是大阶乘整数,有很多的2和3个因素的工作"比"最佳基地不同的与没有任何小的因素,并可能整数工作主要".( - :加快因子计算 - 可能是以其他类型的计算为代价 - 我的第二个错误？:-)
编辑:例如:
(decimal) 16! ==
(decimal ) == 20,922,789,888,000 // uses decimal 14 "1" bits
(dozenal ) == 2,41A,B88,000,000 // uses decimal 10 "1" bits
(hexadecimal) == 130,777,758,000 // uses decimal 18 "1" bits
(octadecimal) == 5F,8B5,024,000 // uses decimal 14 "1" bits
(我或多或少在右边存储数字,没有逗号,加上一些元数据开销).(虽然有人可能认为"当你增加基地将使用更少的'1’比特来表示给定数量"或""如果增加基体,将使用较少的非零数字来表示给定数量",上述示例显示并非总是如此.)
我将每个数字存储为一个小整数("int"或"long int"或"byte").有没有其他合理的方法来存储数字？我很确定我的计算机将这些整数存储为二进制 - 每个"1","2","4","8"和"G"数字使用一个"1"位; 每个"3","5","6","9"和"A"数字使用两个"1"位; 每个"7"和"B"数字使用三个"1"位; 每个"F"数字使用四个"1"位等.
该值(16!)的十进制和十八进制表示都需要14"1"位.所以我在之前的计算中犯了一个错误:对于每个n,代表n!在十进制中,并不总是比在十进制中表示相同的值具有更少的"1"位.但问题仍然存在:是否还有一些其他"最佳"基础需要最少1位的数据才能存储大型因子？
有人问:"你如何存储这些数字？" 嗯,这正是我的问题 - 存储n形式数字的最佳方法是什么!？我 …