reinforcedconcretebounty.py

found=False
import random,math

def miller_rabin(n, k):

    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
    # for justification

    # If number is even, it's a composite number

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def mult_minus_print_list(pair_list):
    max_box=1
    min_v=pow(2,255)
    out=""
    brack=0
    i=1
    length=len(pair_list)
    for j in range(0,int(length/2)):
        out=out+"*"+str(pair_list[length-1-2*j]);
        i=i*pair_list[length-1-2*j]
        if(pair_list[length-1-2*j-1]!=0):
            out = out+"-"+str(pair_list[length-1-2*j-1])+")"
            brack=brack+1
        i=i-pair_list[length-1-2*j-1]
        if(pair_list[length-1-2*j]>max_box):
            max_box=pair_list[length-1-2*j]
        if(pair_list[length-1-2*j]-pair_list[length-1-2*j-1]<min_v):
            min_v=pair_list[length-1-2*j]-pair_list[length-1-2*j-1]
    str2=""
    for j in range(0,brack):
        str2= str2+"("
    print(str2+"1"+out+"=")
    print("max box size= ",max_box," min v value= ",min_v)
    return i

# Find decomposition of @number recursively into form @number = pq+k up to 
# @min_q<q <@max_q and @min_k<= k<=@max_k (both can be negative)
# @limit_sum is the limit to the accumulated deficiency Sum_i |k_i|/q_i

def find_decomposition_opt(number, v,max_d,pre_list):
    global min_num
    if((number<=v+max_d) & (number>=v)):
        pre_list=pre_list+[0,number]
        print("FOUND: ",number)
        print(pre_list)
        w=mult_minus_print_list(pre_list)
        print(w)
        return pre_list;
    if(number<v):
        return []
    if(number<min_num):
        print("MIN: ",number)
        min_num=number
    for k in range(max_d+1):
        if(miller_rabin(number+k,40)):          #prime
            continue
        for q in range(v+max_d,v+k-1,-1):
            if((number+k)%q==0):
                new_n = (number+k)//q
                res= find_decomposition_opt(new_n,v,max_d,pre_list+[k,q])
                if(len(res)!=0):
                    return res;
    return []

def findDecBest(input,num_sboxes):
    global min_num
    avg_sbox_size=int(math.pow(input,1/num_sboxes))
    max_d=41
    for v in range(avg_sbox_size-30,avg_sbox_size+40):
        min_num=input
        pre_list=[]
        print("input: ",input,"num sboxes: ", num_sboxes,"approx size: ", avg_sbox_size, " v=",v," max_d=",max_d)
        res =  find_decomposition_opt(input,v,max_d,pre_list);
        if(len(res)!=0):
            return;

def find256():
    BLSr = 52435875175126190479447740508185965837690552500527637822603658699938581184513
    print("BLS12-381, base order:",BLSr)
    input=BLSr
    min_num=input
    num_sboxes=27
    avg_sbox_size=int(math.pow(input,1/num_sboxes))
    findDecBest(input,num_sboxes)

def find64():
    order =18446744073709551557
    while(miller_rabin(order,10)==0 or (order%5!=1)):
        order = order -1
    input=order
    min_num=input
    num_sboxes=7
    avg_sbox_size=int(math.pow(input,1/num_sboxes))
    findDecBest(input,num_sboxes)

def find56():
    order = 2**56-1000;
    while(miller_rabin(order,10)==0 or (order%5==1)):
        order = order -1
    input=order
    min_num=input
    num_sboxes=6
    findDecBest(input,num_sboxes)

def find48():
    order = 2**48;
    while(miller_rabin(order,10)==0 or (order%5==1)):
        order = order -1
    input=order
    min_num=input
    num_sboxes=6
    findDecBest(input,num_sboxes)

find56()