def getStrongPrime(N, e=0, false_positive_prob=1e-6, randfunc=None):
    """getStrongPrime(N:int, e:int, false_positive_prob:float, randfunc:callable):long
    Return a random strong N-bit prime number.
    In this context p is a strong prime if p-1 and p+1 have at
    least one large prime factor.
    N should be a multiple of 128 and > 512.

    If e is provided the returned prime p-1 will be coprime to e
    and thus suitable for RSA where e is the public exponent.

    The optional false_positive_prob is the statistical probability
    that true is returned even though it is not (pseudo-prime).
    It defaults to 1e-6 (less than 1:1000000).
    Note that the real probability of a false-positive is far less. This is
    just the mathematically provable limit.

    randfunc should take a single int parameter and return that
    many random bytes as a string.
    If randfunc is omitted, then Random.new().read is used.
    """
    # This function was implemented following the
    # instructions found in the paper:
    #   "FAST GENERATION OF RANDOM, STRONG RSA PRIMES"
    #   by Robert D. Silverman
    #   RSA Laboratories
    #   May 17, 1997
    # which by the time of writing could be freely downloaded here:
    # http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2713&rep=rep1&type=pdf

    # Use the accelerator if available
    if _fastmath is not None:
        return _fastmath.getStrongPrime(long(N), long(e), false_positive_prob,
            randfunc)

    if (N < 512) or ((N % 128) != 0):
        raise ValueError ("bits must be multiple of 128 and > 512")

    rabin_miller_rounds = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))

    # calculate range for X
    #   lower_bound = sqrt(2) * 2^{511 + 128*x}
    #   upper_bound = 2^{512 + 128*x} - 1
    x = (N - 512) >> 7;
    # We need to approximate the sqrt(2) in the lower_bound by an integer
    # expression because floating point math overflows with these numbers
    lower_bound = divmod(14142135623730950489L * (2L ** (511 + 128*x)),
                         10000000000000000000L)[0]
    upper_bound = 1 - (1L << (512 + 128*x))
    # Randomly choose X in calculated range
    X = getRandomRange (lower_bound, upper_bound, randfunc)

    # generate p1 and p2
    p = [0, 0]
    for i in (0, 1):
        # randomly choose 101-bit y
        y = getRandomNBitInteger (101, randfunc)
        # initialize the field for sieving
        field = [0] * 5 * len (sieve_base)
        # sieve the field
        for prime in sieve_base:
            offset = y % prime
            for j in xrange ((prime - offset) % prime, len (field), prime):
                field[j] = 1

        # look for suitable p[i] starting at y
        result = 0
        for j in range(len(field)):
            composite = field[j]
            # look for next canidate
            if composite:
                continue
            tmp = y + j
            result = _rabinMillerTest (tmp, rabin_miller_rounds)
            if result > 0:
                p[i] = tmp
                break
        if result == 0:
            raise RuntimeError ("Couln't find prime in field. "
                                "Developer: Increase field_size")

    # Calculate R
    #     R = (p2^{-1} mod p1) * p2 - (p1^{-1} mod p2) * p1
    tmp1 = inverse (p[1], p[0]) * p[1]  # (p2^-1 mod p1)*p2
    tmp2 = inverse (p[0], p[1]) * p[0]  # (p1^-1 mod p2)*p1
    R = tmp1 - tmp2 # (p2^-1 mod p1)*p2 - (p1^-1 mod p2)*p1

    # search for final prime number starting by Y0
    #    Y0 = X + (R - X mod p1p2)
    increment = p[0] * p[1]
    X = X + (R - (X % increment))
    while 1:
        is_possible_prime = 1
        # first check candidate against sieve_base
        for prime in sieve_base:
            if (X % prime) == 0:
                is_possible_prime = 0
                break
        # if e is given make sure that e and X-1 are coprime
        # this is not necessarily a strong prime criterion but useful when
        # creating them for RSA where the p-1 and q-1 should be coprime to
        # the public exponent e
        if e and is_possible_prime:
            if e & 1:
                if GCD (e, X-1) != 1:
                    is_possible_prime = 0
            else:
                if GCD (e, divmod((X-1),2)[0]) != 1:
                    is_possible_prime = 0

        # do some Rabin-Miller-Tests
        if is_possible_prime:
            result = _rabinMillerTest (X, rabin_miller_rounds)
            if result > 0:
                break
        X += increment
		# abort when X has more bits than requested
		# TODO: maybe we shouldn't abort but rather start over.
        if X >= 1L << N:
            raise RuntimeError ("Couln't find prime in field. "
                                "Developer: Increase field_size")
    return X
dataset/ETHPy150Open cloudera/hue/desktop/core/ext-py/pycrypto-2.6.1/lib/Crypto/Util/number.py/getStrongPrime/swapped operands of `-`