libnum factordb

libnum¶

安装指令：pip install libnum
使用场景：进制转换、打素数表等等
function list, here are common used functions:
- converting
  - s2n(s:string/bytes) -> int
  - n2s(n:int) -> bytes
- math
  - nroot(x, n) -> truncated n'th root of x
  - gcd(a, b, ...)
  - lcm(a, b, ...)
  - xgcd(a, b) -> (x, y, g) for a*x+b*y=gcd(a,b)=g
  - invmod(a, n) & has_invmod(a, n)
  - solve_crt(remainders:list, modules:list)
  - nCk(n, k) -> number of combinations
  - factorize(n) -> dict (factors)
  - factorial(n)
- ECC: todo

数据类型转换 ¶

In [ ]:

Copied!





from libnum import s2n, n2s, s2b, b2s
from gmpy2 import log2
from Crypto.Util.number import bytes_to_long, long_to_bytes

s = "012abc"
s2n(s), bytes_to_long(s.encode()) # (52987856773731, 52987856773731)
n2s(num), long_to_bytes(num) # ('012abc', b'012abc')

s_num = s2n(s)
len_in_bits(num), log2(num) # (46, mpfr('45.590727008691232'))


s2b(s), "".join([bin(ord(c)) for c in s])[2:] # ('001100000011000100110010011000010110001001100011', '1100000b1100010b1100100b11000010b11000100b1100011')
s_bin = s2b(s)
b2s(s_bin), "".join([chr(int(s_bin[i:i+8], 2)) for i in range(0, len(s_bin), 8)]) # ('012abc', '012abc')
from libnum import s2n, n2s, s2b, b2s
from gmpy2 import log2
from Crypto.Util.number import bytes_to_long, long_to_bytes

s = "012abc"
s2n(s), bytes_to_long(s.encode()) # (52987856773731, 52987856773731)
n2s(num), long_to_bytes(num) # ('012abc', b'012abc')

s_num = s2n(s)
len_in_bits(num), log2(num) # (46, mpfr('45.590727008691232'))


s2b(s), "".join([bin(ord(c)) for c in s])[2:] # ('001100000011000100110010011000010110001001100011', '1100000b1100010b1100100b11000010b11000100b1100011')
s_bin = s2b(s)
b2s(s_bin), "".join([chr(int(s_bin[i:i+8], 2)) for i in range(0, len(s_bin), 8)]) # ('012abc', '012abc')

Out[ ]:

(b'012abc', '012abc')

获取素数 ¶

primes(n) 获取不大于 n 的所有素数
generate_primes(n) 获取长度为 n bits 的素数
factorize(n) 分解质因数

In [36]:

Copied!





little_num = 101
littlelittle_num = 11
to_be_factorized = 564587462423644586312345678908654325263456667
primes(little_num), generate_prime(littlelittle_num), factorize(to_be_factorized)
little_num = 101
littlelittle_num = 11
to_be_factorized = 564587462423644586312345678908654325263456667
primes(little_num), generate_prime(littlelittle_num), factorize(to_be_factorized)

Out[36]:

([2,
  3,
  5,
  7,
  11,
  13,
  17,
  19,
  23,
  29,
  31,
  37,
  41,
  43,
  47,
  53,
  59,
  61,
  67,
  71,
  73,
  79,
  83,
  89,
  97,
  101],
 1733,
 {264547984673890083312604955351805711413: 1, 13093: 1, 163: 1})

当然，大数分解质因数还得看 factordb 。

factordb¶

安装指令：pip3 install factordb-python
使用场景：命令行中使用，分解大整数，之中存储了大量的已知的分解的整数，也就是说相当于只是在查表，所以很快。

对于上面的大数：

8699621268124163273600280057569065643071518478496234908779966583664908604557271908267773859706827828901385412151814796018448555312901260592

yafu 分解失败；libnum 分解了 6 min 还在跑；

sage 分解用时 53 s 左右：

2^4 * 3^2 * 31 * 61 * 223 * 4013 * 281317 * 4151351 * 339386329 * 370523737 * 5404604441993 * 26798471753993 * 25866088332911027256931479223 * 64889106213996537255229963986303510188999911

factordb 很快就给出了答案：

$ factordb 86996212681241632736002800575690656430715184784
96234908779966583664908604557271908267773859706827828901385412151814796018448555312901260592
2 2 2 2 3 3 31 61 223 4013 281317 4151351 339386329 370523737 5404604441993 26798471753993 25866088332911027256931479223 64889106213996537255229963986303510188999911