学习动机

国赛有道题可以随机生成一组pq试试运气，而且队友确实跑出来了（2023CISCN初赛-badkey）

于是就来学一下多线程，这样比赛需要爆k的时候也比较快

multiprocessing --- 基于进程的并行

概述

from multiprocessing import Pool

def f(x):
    return x*x

if __name__ == '__main__':
    # Pool()创建进程池 https://docs.python.org/zh-cn/3/library/multiprocessing.html#multiprocessing.pool.Pool
    with Pool(5) as p: # 5个进程， with语句会自动调用close()和join()方法 ,
        print(p.map(f, [1, 2, 3])) # map()会将第二个参数的每个元素作为第一个参数的参数，返回一个列表
        
# Output:
# [1],[4],[9]

Process 类

在 multiprocessing 中，通过创建一个 Process 对象然后调用它的 start() 方法来生成进程。 Process 和 threading.Thread API 相同。 一个简单的多进程程序示例是:

from multiprocessing import Process

def f(name):
    print('hello', name)

if __name__ == '__main__':
    p = Process(target=f, args=('bob',)) # 创建进程 target为进程执行的函数 args为函数的参数
    p.start() # 启动进程
    p.join() # 等待进程结束

# Output:
# hello bob

要显示所涉及的各个进程ID，这是一个扩展示例:

from multiprocessing import Process
import os

def info(title):
    print(title)
    print('module name:', __name__) # 模块名
    print('parent process:', os.getppid()) # 父进程id
    print('process id:', os.getpid()) # 当前进程id

def f(name):
    info('function f')
    print('hello', name)

if __name__ == '__main__':
    info('main process line')
    p = Process(target=f, args=('bob',)) # 创建一个Process实例，target为进程函数，args为进程函数的参数
    p.start() # 启动进程
    p.join() # 等待子进程结束后再继续往下运行，通常用于进程间的同步

# Output:
# main process line
# module name: __main__
# parent process: 20051
# process id: 79785
# function f
# module name: __mp_main__
# parent process: 79785
# process id: 79787
# hello bob

两条进程

from multiprocessing import Process
import os

def worker(name):
    print('Worker %s (%s) is running...' % (name, os.getpid())) # os.getpid()获取当前进程ID

if __name__ == '__main__':
    print('Parent process %s.' % os.getpid())
    p1 = Process(target=worker, args=('A',)) # 创建子进程时，只需要传入一个执行函数和函数的参数，创建一个Process实例，用start()方法启动
    p2 = Process(target=worker, args=('B',))
    print('Process will start.')
    p1.start()
    p2.start()
    p1.join() # join()方法可以等待子进程结束后再继续往下运行，通常用于进程间的同步
    p2.join()
    print('Process end.')

Check

from multiprocessing import Process
import os
import time

def worker(name):
    print('Worker %s (%s) is running...' % (name, os.getpid())) # os.getpid()获取当前进程ID
    # 等待3s 并打印name & 时间 用于观察进程间的并发执行
    for i in range(3):
        print('Worker %s is counting %s...' % (name, i))
        time.sleep(1)

if __name__ == '__main__':
    print('Parent process %s.' % os.getpid())
    p1 = Process(target=worker, args=('A',)) # 创建子进程时，只需要传入一个执行函数和函数的参数，创建一个Process实例，用start()方法启动
    p2 = Process(target=worker, args=('B',))
    print('Process will start.')
    p1.start()
    p2.start()
    p1.join() # join()方法可以等待子进程结束后再继续往下运行，通常用于进程间的同步
    p2.join()
    print('Process end.')

# Output:
# Parent process 82357.
# Process will start.
# Worker A (82359) is running...
# Worker A is counting 0...
# Worker B (82360) is running...
# Worker B is counting 0...
# Worker A is counting 1...
# Worker B is counting 1...
# Worker A is counting 2...
# Worker B is counting 2...
# Process end.

实战爆k：

from multiprocessing import Process
import os
import time
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
import gmpy2

n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
# m = \sqrt[3]{c + k \times N} 
# 枚举k
def find_k(start, end):
    for k in range(start, end):
        m, exact = gmpy2.iroot(ct + k * n, e)
        if exact:
            print(long_to_bytes(m))
            break

if __name__ == '__main__':
    # 总k上限为1e10，每个进程枚举1e9个k, 创建10个进程的参数为(0, 1e9), (1e9, 2e9), ..., (9e9, 1e10)
    s1 = int(0)
    s2 = int(1e9)
    s3 = int(2e9)
    s4 = int(3e9)
    s5 = int(4e9)
    s6 = int(5e9)
    s7 = int(6e9)
    s8 = int(7e9)
    s9 = int(8e9)
    s10 = int(9e9)
    end = int(1e10)

    p1 = Process(target=find_k, args=(s1, s2)) # 创建子进程时，只需要传入一个执行函数和函数的参数，创建一个Process实例，用start()方法启动
    p2 = Process(target=find_k, args=(s2, s3))
    p3 = Process(target=find_k, args=(s3, s4))
    p4 = Process(target=find_k, args=(s4, s5))
    p5 = Process(target=find_k, args=(s5, s6))
    p6 = Process(target=find_k, args=(s6, s7))
    p7 = Process(target=find_k, args=(s7, s8))
    p8 = Process(target=find_k, args=(s8, s9))
    p9 = Process(target=find_k, args=(s9, s10))
    p10 = Process(target=find_k, args=(s10, end))
    print('Process will start.')
    p1.start()
    p2.start()
    p3.start()
    p4.start()
    p5.start()
    p6.start()
    p7.start()
    p8.start()
    p9.start()
    p10.start()
    p1.join() # join()方法可以等待子进程结束后再继续往下运行，通常用于进程间的同步
    p2.join()
    p3.join()
    p4.join()
    p5.join()
    p6.join()
    p7.join()
    p8.join()
    p9.join()
    p10.join()
    print('Process end.')

实测cpu负载符合预期，不过这个代码着实有点丑，美化一下

from multiprocessing import Process
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
import gmpy2

n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

# m = \sqrt[3]{c + k \times N} 
# 枚举k
def find_k(start, end):
    for k in range(start, end):
        m, exact = gmpy2.iroot(ct + k * n, e)
        if exact:
            print(long_to_bytes(m))
            break

if __name__ == '__main__':
    # 总k上限为1e10，每个进程枚举1e9个k, 创建10个进程的参数为(0, 1e9), (1e9, 2e9), ..., (9e9, 1e10)
    s = [int(i * 1e9) for i in range(10)]
    end = int(1e10)

    processes = []
    print('Process will start.')
    for i in range(10):
        p = Process(target=find_k, args=(s[i], s[i+1] if i < 9 else end)) # if i < 9 else end 用于处理最后一个进程
        processes.append(p)
        p.start()

    for p in processes:
        p.join()

    print('Process end.')

solve~