def generate_smooth_prime()

in crypto/keybaseish/dsks.py [0:0]

• 40 lines of code
• 16 McCabe index (conditional complexity)

def generate_smooth_prime(bit_size, primitive_roots=[], smooth_bit_size=50, exclude=[]):
    """Generate smooth prime n
    Args:
        bit_size(int): size of generated prime in bits
        primitive_roots(list(int)): list of numbers that will be primitive roots modulo n
        smooth_bit_size(int): most factors of n-1 will be of this bit size   
        exclude(list(int)): n-1 won't have any factor from that list
    Returns:
        int: n
    """
    while True:
        n = 2
        factors = {2:1}

        # get random primes of correct size
        print('smooth prime - loop of size about {}'.format((bit_size - 2*smooth_bit_size)//smooth_bit_size))
        while n.bit_length() < bit_size - 2*smooth_bit_size:
            q = getPrime(smooth_bit_size)
            if q in exclude:
                continue
            n *= q
            if q in factors:
                factors[q] += 1
            else:
                factors[q] = 1

        # find last prime so that n+1 is prime and the size is correct
        smooth_bit_size_padded = bit_size - n.bit_length()
        print('smooth prime - smooth_bit_size_padded = {}'.format(smooth_bit_size_padded))
        while True:
            q = getPrime(smooth_bit_size_padded)
            if q in exclude:
                continue
            if isPrime((n*q)+1):
                n = (n*q)+1
                if q in factors:
                    factors[q] += 1
                else:
                    factors[q] = 1
                break
        
        # check if given numbers are primitive roots
        print('smooth prime - checking primitive roots')
        are_primitive_roots = True
        if len(primitive_roots) > 0: 
            for factor, factor_power in factors.items():
                for primitive_root in primitive_roots:
                    if pow(primitive_root, (n-1)//(factor**factor_power), n) == 1:
                        are_primitive_roots = False
                        break

        if are_primitive_roots:
            print('smooth prime - done')
            return n, factors
        else:
            print('primitive roots criterion not met')