Factorizes the given large integer.

        :param pq: the prime pair pq.
        :return: a tuple containing the two factors p and q.
489763
def factorize(cls, pq):
        
        if pq % 2 == 0:
            return 2, pq // 2

        y, c, m = randint(1, pq - 1), randint(1, pq - 1), randint(1, pq - 1)
        g = r = q = 1
        x = ys = 0

        while g == 1:
            x = y
            for i in range(r):
                y = (pow(y, 2, pq) + c) % pq

            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = (pow(y, 2, pq) + c) % pq
                    q = q * (abs(x - y)) % pq

                g = cls.gcd(q, pq)
                k += m

            r *= 2

        if g == pq:
            while True:
                ys = (pow(ys, 2, pq) + c) % pq
                g = cls.gcd(abs(x - ys), pq)
                if g > 1:
                    break

        p, q = g, pq // g
        return (p, q) if p < q else (q, p)
8555
def pauli(qubo):
	
	from blueqat.pauli import qubo_bit
	h = 0.0
	assert all(len(q) == len(qubo) for q in qubo)
	for i in range(len(qubo)):
		h += qubo_bit(i) * qubo[i][i]
		for j in range(i + 1, len(qubo)):
			h += qubo_bit(i)*qubo_bit(j) * (qubo[i][j] + qubo[j][i])
	return h
1084839
def compute_factorial(n):
    
    sleep_walk(10)
    ret = 1
    for i in range(n):
        ret = ret * (i + 1)
    return ret
1087448
def factorization( n ):
  """"""

  assert isinstance( n, integer_types )

  if n < 2: return []

  result = []
  d = 2

  # Test the small primes:

  for d in smallprimes:
    if d > n: break
    q, r = divmod( n, d )
    if r == 0:
      count = 1
      while d <= n:
        n = q
        q, r = divmod( n, d )
        if r != 0: break
        count = count + 1
      result.append( ( d, count ) )

  # If n is still greater than the last of our small primes,
  # it may require further work:

  if n > smallprimes[-1]:
    if is_prime( n ):   # If what's left is prime, it's easy:
      result.append( ( n, 1 ) )
    else:               # Ugh. Search stupidly for a divisor:
      d = smallprimes[-1]
      while 1:
        d = d + 2               # Try the next divisor.
        q, r = divmod( n, d )
        if q < d: break         # n < d*d means we're done, n = 1 or prime.
        if r == 0:              # d divides n. How many times?
          count = 1
          n = q
          while d <= n:                 # As long as d might still divide n,
            q, r = divmod( n, d )       # see if it does.
            if r != 0: break
            n = q                       # It does. Reduce n, increase count.
            count = count + 1
          result.append( ( d, count ) )
      if n > 1: result.append( ( n, 1 ) )

  return result
368303
def _rsa_recover_prime_factors(n, e, d):
    
    # See 8.2.2(i) in Handbook of Applied Cryptography.
    ktot = d * e - 1
    # The quantity d*e-1 is a multiple of phi(n), even,
    # and can be represented as t*2^s.
    t = ktot
    while t % 2 == 0:
        t = t // 2
    # Cycle through all multiplicative inverses in Zn.
    # The algorithm is non-deterministic, but there is a 50% chance
    # any candidate a leads to successful factoring.
    # See "Digitalized Signatures and Public Key Functions as Intractable
    # as Factorization", M. Rabin, 1979
    spotted = False
    a = 2
    while not spotted and a < _MAX_RECOVERY_ATTEMPTS:
        k = t
        # Cycle through all values a^{t*2^i}=a^k
        while k < ktot:
            cand = pow(a, k, n)
            # Check if a^k is a non-trivial root of unity (mod n)
            if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:
                # We have found a number such that (cand-1)(cand+1)=0 (mod n).
                # Either of the terms divides n.
                p = _gcd(cand + 1, n)
                spotted = True
                break
            k *= 2
        # This value was not any good... let's try another!
        a += 2
    if not spotted:
        raise ValueError("Unable to compute factors p and q from exponent d.")
    # Found !
    q, r = divmod(n, p)
    assert r == 0
    p, q = sorted((p, q), reverse=True)
    return (p, q)
842966
@GwtIncompatible("TODO")
  public static BigInteger divide(BigInteger p, BigInteger q, RoundingMode mode) {
    BigDecimal pDec = new BigDecimal(p);
    BigDecimal qDec = new BigDecimal(q);
    return pDec.divide(qDec, 0, mode).toBigIntegerExact();
  }
583219
def find_prime_polys(generator=2, c_exp=8, fast_primes=False, single=False):
    ''''''
    # fast_primes will output less results but will be significantly faster.
    # single will output the first prime polynomial found, so if all you want is to just find one prime polynomial to generate the LUT for Reed-Solomon to work, then just use that.

    # A prime polynomial (necessarily irreducible) is necessary to reduce the multiplications in the Galois Field, so as to avoid overflows.
    # Why do we need a "prime polynomial"? Can't we just reduce modulo 255 (for GF(2^8) for example)? Because we need the values to be unique.
    # For example: if the generator (alpha) = 2 and c_exp = 8 (GF(2^8) == GF(256)), then the generated Galois Field (0, 1, α, α^1, α^2, ..., α^(p-1)) will be galois field it becomes 0, 1, 2, 4, 8, 16, etc. However, upon reaching 128, the next value will be doubled (ie, next power of 2), which will give 256. Then we must reduce, because we have overflowed above the maximum value of 255. But, if we modulo 255, this will generate 256 == 1. Then 2, 4, 8, 16, etc. giving us a repeating pattern of numbers. This is very bad, as it's then not anymore a bijection (ie, a non-zero value doesn't have a unique index). That's why we can't just modulo 255, but we need another number above 255, which is called the prime polynomial.
    # Why so much hassle? Because we are using precomputed look-up tables for multiplication: instead of multiplying a*b, we precompute alpha^a, alpha^b and alpha^(a+b), so that we can just use our lookup table at alpha^(a+b) and get our result. But just like in our original field we had 0,1,2,...,p-1 distinct unique values, in our "LUT" field using alpha we must have unique distinct values (we don't care that they are different from the original field as long as they are unique and distinct). That's why we need to avoid duplicated values, and to avoid duplicated values we need to use a prime irreducible polynomial.

    # Here is implemented a bruteforce approach to find all these prime polynomials, by generating every possible prime polynomials (ie, every integers between field_charac+1 and field_charac*2), and then we build the whole Galois Field, and we reject the candidate prime polynomial if it duplicates even one value or if it generates a value above field_charac (ie, cause an overflow).
    # Note that this algorithm is slow if the field is too big (above 12), because it's an exhaustive search algorithm. There are probabilistic approaches, and almost surely prime approaches, but there is no determistic polynomial time algorithm to find irreducible monic polynomials. More info can be found at: http://people.mpi-inf.mpg.de/~csaha/lectures/lec9.pdf
    # Another faster algorithm may be found at Adleman, Leonard M., and Hendrik W. Lenstra. "Finding irreducible polynomials over finite fields." Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM, 1986.

    # Prepare the finite field characteristic (2^p - 1), this also represent the maximum possible value in this field
    root_charac = 2 # we're in GF(2)
    field_charac = int(root_charac**c_exp - 1)
    field_charac_next = int(root_charac**(c_exp+1) - 1)

    prim_candidates = []
    if fast_primes:
        prim_candidates = rwh_primes1(field_charac_next) # generate maybe prime polynomials and check later if they really are irreducible
        prim_candidates = [x for x in prim_candidates if x > field_charac] # filter out too small primes
    else:
        prim_candidates = xrange(field_charac+2, field_charac_next, root_charac) # try each possible prime polynomial, but skip even numbers (because divisible by 2 so necessarily not irreducible)

    # Start of the main loop
    correct_primes = []
    for prim in prim_candidates: # try potential candidates primitive irreducible polys
        seen = bytearray(field_charac+1) # memory variable to indicate if a value was already generated in the field (value at index x is set to 1) or not (set to 0 by default)
        conflict = False # flag to know if there was at least one conflict

        # Second loop, build the whole Galois Field
        x = 1
        for i in xrange(field_charac):
            # Compute the next value in the field (ie, the next power of alpha/generator)
            x = gf_mult_noLUT(x, generator, prim, field_charac+1)

            # Rejection criterion: if the value overflowed (above field_charac) or is a duplicate of a previously generated power of alpha, then we reject this polynomial (not prime)
            if x > field_charac or seen[x] == 1:
                conflict = True
                break
            # Else we flag this value as seen (to maybe detect future duplicates), and we continue onto the next power of alpha
            else:
                seen[x] = 1

        # End of the second loop: if there's no conflict (no overflow nor duplicated value), this is a prime polynomial!
        if not conflict: 
            correct_primes.append(prim)
            if single: return prim

    # Return the list of all prime polynomials
    return correct_primes
868761
def _ppf(self, q, dist, cache):
        """"""
        return -evaluation.evaluate_inverse(dist, 1-q, cache=cache)
888326
public static RQ factorize(Matrix A) {
        return new RQ(A.numRows(), A.numColumns()).factor(new DenseMatrix(A));
    }
1073050
public static int crypto_scalarmult(byte[] q,
  byte[] n,
  byte[] p)
{
  byte[] e = new byte[32];
  int i;
  int[] x1 = new int[10];
  int[] x2 = new int[10];
  int[] z2 = new int[10];
  int[] x3 = new int[10];
  int[] z3 = new int[10];
  int[] tmp0 = new int[10];
  int[] tmp1 = new int[10];
  int pos;
  int swap;
  int b;

  for (i = 0;i < 32;++i) e[i] = n[i];
//  e[0] &= 248;
//  e[31] &= 127;
//  e[31] |= 64;
  fe_frombytes.fe_frombytes(x1,p);
  fe_1.fe_1(x2);
  fe_0.fe_0(z2);
  fe_copy.fe_copy(x3,x1);
  fe_1.fe_1(z3);

  swap = 0;
  for (pos = 254;pos >= 0;--pos) {
    b = e[pos / 8] >>> (pos & 7);
    b &= 1;
    swap ^= b;
    fe_cswap.fe_cswap(x2,x3,swap);
    fe_cswap.fe_cswap(z2,z3,swap);
    swap = b;
//CONVERT #include "montgomery.h"

/* qhasm: fe X2 */

/* qhasm: fe Z2 */

/* qhasm: fe X3 */

/* qhasm: fe Z3 */

/* qhasm: fe X4 */

/* qhasm: fe Z4 */

/* qhasm: fe X5 */

/* qhasm: fe Z5 */

/* qhasm: fe A */

/* qhasm: fe B */

/* qhasm: fe C */

/* qhasm: fe D */

/* qhasm: fe E */

/* qhasm: fe AA */

/* qhasm: fe BB */

/* qhasm: fe DA */

/* qhasm: fe CB */

/* qhasm: fe t0 */

/* qhasm: fe t1 */

/* qhasm: fe t2 */

/* qhasm: fe t3 */

/* qhasm: fe t4 */

/* qhasm: enter ladder */

/* qhasm: D = X3-Z3 */
/* asm 1: fe_sub.fe_sub(>D=fe#5,<X3=fe#3,<Z3=fe#4); */
/* asm 2: fe_sub.fe_sub(>D=tmp0,<X3=x3,<Z3=z3); */
fe_sub.fe_sub(tmp0,x3,z3);

/* qhasm: B = X2-Z2 */
/* asm 1: fe_sub.fe_sub(>B=fe#6,<X2=fe#1,<Z2=fe#2); */
/* asm 2: fe_sub.fe_sub(>B=tmp1,<X2=x2,<Z2=z2); */
fe_sub.fe_sub(tmp1,x2,z2);

/* qhasm: A = X2+Z2 */
/* asm 1: fe_add.fe_add(>A=fe#1,<X2=fe#1,<Z2=fe#2); */
/* asm 2: fe_add.fe_add(>A=x2,<X2=x2,<Z2=z2); */
fe_add.fe_add(x2,x2,z2);

/* qhasm: C = X3+Z3 */
/* asm 1: fe_add.fe_add(>C=fe#2,<X3=fe#3,<Z3=fe#4); */
/* asm 2: fe_add.fe_add(>C=z2,<X3=x3,<Z3=z3); */
fe_add.fe_add(z2,x3,z3);

/* qhasm: DA = D*A */
/* asm 1: fe_mul.fe_mul(>DA=fe#4,<D=fe#5,<A=fe#1); */
/* asm 2: fe_mul.fe_mul(>DA=z3,<D=tmp0,<A=x2); */
fe_mul.fe_mul(z3,tmp0,x2);

/* qhasm: CB = C*B */
/* asm 1: fe_mul.fe_mul(>CB=fe#2,<C=fe#2,<B=fe#6); */
/* asm 2: fe_mul.fe_mul(>CB=z2,<C=z2,<B=tmp1); */
fe_mul.fe_mul(z2,z2,tmp1);

/* qhasm: BB = B^2 */
/* asm 1: fe_sq.fe_sq(>BB=fe#5,<B=fe#6); */
/* asm 2: fe_sq.fe_sq(>BB=tmp0,<B=tmp1); */
fe_sq.fe_sq(tmp0,tmp1);

/* qhasm: AA = A^2 */
/* asm 1: fe_sq.fe_sq(>AA=fe#6,<A=fe#1); */
/* asm 2: fe_sq.fe_sq(>AA=tmp1,<A=x2); */
fe_sq.fe_sq(tmp1,x2);

/* qhasm: t0 = DA+CB */
/* asm 1: fe_add.fe_add(>t0=fe#3,<DA=fe#4,<CB=fe#2); */
/* asm 2: fe_add.fe_add(>t0=x3,<DA=z3,<CB=z2); */
fe_add.fe_add(x3,z3,z2);

/* qhasm: assign x3 to t0 */

/* qhasm: t1 = DA-CB */
/* asm 1: fe_sub.fe_sub(>t1=fe#2,<DA=fe#4,<CB=fe#2); */
/* asm 2: fe_sub.fe_sub(>t1=z2,<DA=z3,<CB=z2); */
fe_sub.fe_sub(z2,z3,z2);

/* qhasm: X4 = AA*BB */
/* asm 1: fe_mul.fe_mul(>X4=fe#1,<AA=fe#6,<BB=fe#5); */
/* asm 2: fe_mul.fe_mul(>X4=x2,<AA=tmp1,<BB=tmp0); */
fe_mul.fe_mul(x2,tmp1,tmp0);

/* qhasm: E = AA-BB */
/* asm 1: fe_sub.fe_sub(>E=fe#6,<AA=fe#6,<BB=fe#5); */
/* asm 2: fe_sub.fe_sub(>E=tmp1,<AA=tmp1,<BB=tmp0); */
fe_sub.fe_sub(tmp1,tmp1,tmp0);

/* qhasm: t2 = t1^2 */
/* asm 1: fe_sq.fe_sq(>t2=fe#2,<t1=fe#2); */
/* asm 2: fe_sq.fe_sq(>t2=z2,<t1=z2); */
fe_sq.fe_sq(z2,z2);

/* qhasm: t3 = a24*E */
/* asm 1: fe_mul121666(>t3=fe#4,<E=fe#6); */
/* asm 2: fe_mul121666(>t3=z3,<E=tmp1); */
fe_mul121666.fe_mul121666(z3,tmp1);

/* qhasm: X5 = t0^2 */
/* asm 1: fe_sq.fe_sq(>X5=fe#3,<t0=fe#3); */
/* asm 2: fe_sq.fe_sq(>X5=x3,<t0=x3); */
fe_sq.fe_sq(x3,x3);

/* qhasm: t4 = BB+t3 */
/* asm 1: fe_add.fe_add(>t4=fe#5,<BB=fe#5,<t3=fe#4); */
/* asm 2: fe_add.fe_add(>t4=tmp0,<BB=tmp0,<t3=z3); */
fe_add.fe_add(tmp0,tmp0,z3);

/* qhasm: Z5 = X1*t2 */
/* asm 1: fe_mul.fe_mul(>Z5=fe#4,x1,<t2=fe#2); */
/* asm 2: fe_mul.fe_mul(>Z5=z3,x1,<t2=z2); */
fe_mul.fe_mul(z3,x1,z2);

/* qhasm: Z4 = E*t4 */
/* asm 1: fe_mul.fe_mul(>Z4=fe#2,<E=fe#6,<t4=fe#5); */
/* asm 2: fe_mul.fe_mul(>Z4=z2,<E=tmp1,<t4=tmp0); */
fe_mul.fe_mul(z2,tmp1,tmp0);

/* qhasm: return */
  }
  fe_cswap.fe_cswap(x2,x3,swap);
  fe_cswap.fe_cswap(z2,z3,swap);

  fe_invert.fe_invert(z2,z2);
  fe_mul.fe_mul(x2,x2,z2);
  fe_tobytes.fe_tobytes(q,x2);
  return 0;
}
1149569
public static QL factorize(Matrix A) {
        return new QL(A.numRows(), A.numColumns()).factor(new DenseMatrix(A));
    }
1341197
def carmichael_of_factorized( f_list ):
  

  if len( f_list ) < 1: return 1

  result = carmichael_of_ppower( f_list[0] )
  for i in range( 1, len( f_list ) ):
    result = lcm( result, carmichael_of_ppower( f_list[i] ) )

  return result
281757
function(symbol, factors) {
                try {
                    if(symbol.group === CP) { 
                        //this may have the unfortunate side effect of expanding and factoring again
                        //to only end up with the same result. 
                        //TODO: try to avoid this
                        //collect the symbols and sort to have the longest first. Thinking is that the longest terms 
                        //has to contain the variable in order for it to be factorable
                        var symbols = _.expand(symbol.clone(), true).collectSymbols(null, null, function(a, b) {
                            return (b.length || 1) - (a.length || 1);
                        });
                        
                        var map = {}; //create a map of common factors
                        var coeffs = [];
                        for(var i=0; i<symbols.length; i++) {
                            var sym = symbols[i]; 
                            coeffs.push(sym.multiplier.clone());
                            sym.each(function(x) {
                                var p = Number(x.power);
                                //This check exits since we have a symbolic power.
                                //For the future... think about removing this check and modify for symbolic powers
                                if(isNaN(p))
                                    throw new Error('exiting');
                                //loop through the symbols and lump together common terms
                                if(x.value in map) {
                                    if(p < map[x.value][0])
                                        map[x.value][0] = p;
                                    map[x.value][1].push(x);
                                }
                                else
                                    map[x.value] = [p, [x]];
                            });
                        }
                        //the factor
                        var factor = new Symbol(1);
                        for(var x in map) {
                            //if this factor is found in all terms since the length of 
                            //matching variable terms matches the number of original terms
                            if(map[x][1].length === symbols.length) {
                                //generate a symbol and multiply into the factor
                                factor = _.multiply(factor, _.pow(new Symbol(x), new Symbol(map[x][0])));
                            }
                        }
                        //get coefficient factor
                        var c = core.Math2.QGCD.apply(null, coeffs);

                        if(!c.equals(1)) {
                            factors.add(new Symbol(c));
                            for(var i=0; i<symbols.length; i++) {
                                symbols[i].multiplier = symbols[i].multiplier.divide(c);
                            }
                        }
                            
                        //if we actuall found any factors
                        if(!factor.equals(1)) { 
                            factors.add(factor);
                            symbol = new Symbol(0);
                            for(var i=0; i<symbols.length; i++) {
                                symbol = _.add(symbol, _.divide(symbols[i], factor.clone()));
                            }
                        }
                    }
                }
                catch(e){;}

                return symbol;
            }
40282
def _factor_generator(n):
    
    p = prime_factors(n)
    factors = {}
    for p1 in p:
        try:
            factors[p1] += 1
        except KeyError:
            factors[p1] = 1
    return factors
84605
def qth_pw(self, q):
        
        return heapq.nlargest(q + 2, self._T.iteritems(),
                              key=operator.itemgetter(1))[-1]
773349
def factor_coeff(cls, ops, kwargs):
    """"""
    coeffs, nops = zip(*map(_coeff_term, ops))
    coeff = 1
    for c in coeffs:
        coeff *= c
    if coeff == 1:
        return nops, coeffs
    else:
        return coeff * cls.create(*nops, **kwargs)
60547
def pq(self) -> PyQuery:
        
        if self._pq is None:
            self._pq = PyQuery(self.lxml)

        return self._pq