#!/usr/bin/env python3
import sys
from collections import Counter

def main():
    if len(sys.argv) < 2:
        print("用法: python count_chars.py <字符串>")
        sys.exit(1)

    input_str = sys.argv[1]  # 获取第一个参数作为输入字符串
    counts = Counter(input_str)  # 统计字符出现次数

    # 按字符排序输出
    for char in sorted(counts):
        print(f"'{char}': {counts[char]}")

if __name__ == "__main__":
    main()

PR.<x> = Zmod(n)[] #x是多项式自变量，Zmod(n)表示 多项式的系数是模n的
f = (p_base + (i << 265))  +  x * (mod << 6)
roots = f.monic().small_roots(X=2^453, beta=0.4, epsilon=0.05)
assert roots
p = f(roots[0])

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)

#1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
#40812438243894343296354573724131194431453023461572200856406939246297219541329623
#21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
#19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188

from Crypto.Util.number import long_to_bytes
h1, h2 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479, 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537
#h1是p的高300位（放在了低位），h2是q的低265位
# 1. 构造 p 的已知部分
mod = 1 << 265 #2^265
p_high = h1 << 724 #将高300位放到高位
#p = h1_724bit
#q = 759bit_h2
#n = p * q
#h2^-1 = inverse_mod(h2, 2^265)
#(n * h2^-1) % mod = (p % mod) * [(759bit_h2 * h2^-1) % mod] = (p % mod) * 1
p_low = (n * inverse_mod(h2, mod)) % mod #得到p的低265位
p_base = p_high + p_low #拼接p，中间有1024-300-265 = 459位缺失（265位~723位）

# 2. 使用 Coppersmith 算法查找 p 的中间缺失位
PR.<x> = Zmod(n)[] #x是多项式自变量，Zmod(n)表示 多项式的系数是模n的
for i in range(64):#2^6 = 64 爆破6位（穷举）
    # 构建多项式: f(x) = (p_base + i*2^265) + x*2^329 (2^329 = mod * 64)
    f = (p_base + (i << 265))  +  x * (mod << 6)
    #注意monic首一化
    roots = f.monic().small_roots(X=2^453, beta=0.4, epsilon =0.05) # 453 = 459 - 6 爆破了6位
    if roots:
        p = int(f(roots[0]))#需要强转int
        break
# 3. 解密 RSA
q = n // p
d = inverse_mod(e, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, n)))

#...
PR.<x> = Zmod(n)[]
f = p_base + x * mod
roots = f.monic().small_roots(X=2^459, beta=0.4, epsilon =0.04)
assert roots
p = int(f(roots[0]))
#...

python -c "from Crypto.Util.number import long_to_bytes
print(long_to_bytes(56006392793429523039334991295440472601833419964063188654957241090275128167728784831578248304182847101))"

# FLAG = bytes_to_long(pad(b"flag{??????}",64))
# def init_key():
#     p, q = getPrime(512), getPrime(512)
#     n = p*q
#     e = 9
#     while(GCD((p-1)*(q-1),e)!=1):
#         p, q = getPrime(512), getPrime(512)
#         n = p*q
#     d = inverse(e,(p-1)*(q-1))
#     return n,e,d

# n_list=list()
# c_list=list()
# for i in range(9):
#     N,e,d=init_key()
#     n_list.append(N)
#     c=pow(FLAG,e,N)
#     c_list.append(pow(FLAG,e,N))
#     assert(pow(c,d,N)==FLAG)
# print("n_list:",n_list)
# print("c_list:",c_list)

from Crypto.Util.number import long_to_bytes
n_list = [
]

c_list = [
]
e = 9
# CRT 合并
M = crt(c_list, n_list)
# 整数 9 次方根
m = M.nth_root(e)
print(long_to_bytes(int(m)))