python类gcd()的实例源码

def __init__(self, jobs):
        """
        Create a new Scheduler.

        >>> s = Scheduler([Job(1, max, 100, 200)])
        >>> for jobs in s:
        ...    time.sleep(s.tick_duration)

        :param jobs: Sequence of jobs to schedule
        """
        periodicities = {job.periodicity for job in jobs}
        self.tick_duration = reduce(lambda x, y: fractions.gcd(x, y),
                                    periodicities)
        self._ticks = self.find_minimum_ticks_required(self.tick_duration,
                                                       periodicities)
        self._jobs = jobs
        self._current_tick = 0
        logger.debug('Scheduler has {} ticks, each one is {} seconds'.
                     format(self._ticks, self.tick_duration))

def __new__(cls, name, bases, attrs):
        # A list of all functions which is marked as 'is_cronjob=True'
        cron_jobs = []

        # The min_tick is the greatest common divisor(GCD) of the interval of cronjobs
        # this value would be queried by scheduler when the project initial loaded.
        # Scheudler may only send _on_cronjob task every min_tick seconds. It can reduce
        # the number of tasks sent from scheduler.
        min_tick = 0

        for each in attrs.values():
            if inspect.isfunction(each) and getattr(each, 'is_cronjob', False):
                cron_jobs.append(each)
                min_tick = fractions.gcd(min_tick, each.tick)
        newcls = type.__new__(cls, name, bases, attrs)
        newcls._cron_jobs = cron_jobs
        newcls._min_tick = min_tick
        return newcls

def __init__(self, lattice, m, n):
        self.lattice = lattice
        self.m = m
        self.n = n

        # Chiral vector
        self.c = lattice.pos(m,n)
        self.magC = mag(self.c)
        # Translation vector 
        d = gcd(2*n+m,2*m+n)
        self.t = lattice.pos((2*n+m)/d, -(2*m+n)/d);
        self.magT = mag(self.t)
        # Chiral rotation matrix (rotate a1 along x-axis)
        self.theta = acos(norm(self.c)[0]*copysign(1, self.c[1]))
        self.rotM = np.array([
                [cos(self.theta), sin(self.theta)],
                [-sin(self.theta), cos(self.theta)]]).T

        # Calculate atoms and bonds in unit cell
        self._boundsErr = mag(lattice.pos(0,0,0) - lattice.pos(0,0,1))
        self.indices = self._calcIndices(m, n)
        self.atoms = self._calcAtoms(self.indices)
        self.bonds = self._calcBonds(self.indices)

def lissajous(a, b, d):
  # request a,b integers, so we have closed, periodic curves
  n = gcd(a,b)
  N = (a/n) * (b/n) # number of periods before looping

  # error test input
  if N > 1e4:       # non-integer (a,b) or otherwise too irregular
    raise Exception('Non-periodic', 'a,b must be integers (of moderate size)')

  # compute a set of interpolation points
  numb_pts = max(3*N, 100) # using 3N interpolation points is decent enough
  t = np.linspace(0,2*pi/n, numb_pts)
  x = np.array([np.sin(a*t + d), np.sin(b*t)])

  # do a cubic curve interpolation with periodic boundary conditions
  return curves.cubic_curve(x.T, curves.Boundary.PERIODIC)


### main program ###

# create the curve
# crv = lissajous(60, 44, pi/2);

def brent(N):
   # brent returns a divisor not guaranteed to be prime, returns n if n prime
   if N%2==0: return 2
   y,c,m = randint(1, N-1),randint(1, N-1),randint(1, N-1)
   g,r,q = 1,1,1
   while g==1:             
       x = y
       for i in range(r):
          y = ((y*y)%N+c)%N
       k = 0
       while (k<r and g==1):
          ys = y
          for i in range(min(m,r-k)):
             y = ((y*y)%N+c)%N
             q = q*(abs(x-y))%N
          g = gcd(q,N)
          k = k + m
       r = r*2
   if g==N:
       while True:
          ys = ((ys*ys)%N+c)%N
          g = gcd(abs(x-ys),N)
          if g>1:  break
   return g

def smallPrimes(self,n="n",upperlimit=1000000):
        if(n=="n"): n = self.modulus
        from sympy import sieve
        for i in sieve.primerange(1,upperlimit):
            if(n % i == 0):
                self.p = i
                self.q = n // i
                return

    #-----------------END SMALL PRIME SECTION-----------------#
    #----------------BEGIN POLLARDS P-1 SECTION---------------#

    #Pollard P minus 1 factoring, using the algorithm as described by
    # https://math.berkeley.edu/~sagrawal/su14_math55/notes_pollard.pdf
    # Then I further modified it by using the standard "B" as the limit, and only
    # taking a to the power of a prime. Then from looking at wikipedia and such,
    # I took the gcd out of the loop, and put it at the end.
    # TODO Update this to official wikipedia definition, once I find an explanation of
    # Wikipedia definition. (I.e. Why it works)

def __init__( s, GcdUnit, src_msgs, sink_msgs,
                src_delay, sink_delay,
                dump_vcd=False, test_verilog=False ):

    # Instantiate models

    s.src  = TestSource ( GcdUnitReqMsg(), src_msgs,  src_delay  )
    s.gcd  = GcdUnit    ()
    s.sink = TestSink   ( Bits(16),        sink_msgs, sink_delay )

    # Dump VCD

    if dump_vcd:
      s.gcd.vcd_file = dump_vcd

    # Translation

    if test_verilog:
      s.gcd = TranslationTool( s.gcd )

    # Connect

    s.connect( s.src.out,  s.gcd.req  )
    s.connect( s.gcd.resp, s.sink.in_ )

def __init__( s ):

    # Interface

    s.req    = InValRdyBundle  ( GcdUnitReqMsg() )
    s.resp   = OutValRdyBundle ( Bits(16)        )

    # Adapters

    s.req_q  = InValRdyQueueAdapter  ( s.req  )
    s.resp_q = OutValRdyQueueAdapter ( s.resp )

    # Concurrent block

    @s.tick_fl
    def block():
      req_msg = s.req_q.popleft()
      result = gcd( req_msg.a, req_msg.b )
      s.resp_q.append( result )

  # Line tracing

def break_gcd_cipher():
    from crypto.designs.integers.gcd import encrypt, decrypt
    from os import urandom        
    for _m in range(1, 256):
        m = 0
        while not m:
            m = ord(urandom(1))
        k = ord(urandom(1))

        def point_generator(m, k, point_count=32):
            for count in range(point_count):
                yield encrypt(m, k)[0]
        recovered_m = find_basis(point_generator(m, k))
        assert recovered_m == m, (recovered_m, m)
        print("Recovered m: {}".format(recovered_m))
    # conclusion: The error in pq + e should be random/should not be kept fixed

def canMeasureWater(self, x, y, z):
        """
        :type x: int
        :type y: int
        :type z: int
        :rtype: bool
        """
        import fractions
        if z > y + x:
            return False
        gcd = fractions.gcd(x, y)
        if gcd == 0:
            if x == z or y == z:
                return True
            else:
                return False
        elif z % gcd == 0:
            return True
        else:
            return False

def calculate_alloc_stats(self):
        """Calculates the minimum_size and alignment_gcd to determine "virtual allocs" when read lengths of data
           It's particularly important to cast all numbers to ints, since they're used a lot and object take effort to reread.
        """
        available_allocs = list(self.get_available_allocs())

        self.minimum_size = int(min([size for _, size in available_allocs]))
        accumulator = self.minimum_size
        for start, _ in available_allocs:
            if accumulator is None and start > 1:
                accumulator = start
            if accumulator and start > 0:
                accumulator = fractions.gcd(accumulator, start)
        self.alignment_gcd = int(accumulator)
        # Pick an arbitrary cut-off that'll lead to too many reads
        if self.alignment_gcd < 0x4:
            debug.warning("Alignment of " + self.__class__.__name__ + " is too small, plugins will be extremely slow")

def brent(N):
   # brent returns a divisor not guaranteed to be prime, returns n if n prime
   if N%2==0: return 2
   y,c,m = randint(1, N-1),randint(1, N-1),randint(1, N-1)
   g,r,q = 1,1,1
   while g==1:             
       x = y
       for i in range(r):
          y = ((y*y)%N+c)%N
       k = 0
       while (k<r and g==1):
          ys = y
          for i in range(min(m,r-k)):
             y = ((y*y)%N+c)%N
             q = q*(abs(x-y))%N
          g = gcd(q,N)
          k = k + m
       r = r*2
   if g==N:
       while True:
          ys = ((ys*ys)%N+c)%N
          g = gcd(abs(x-ys),N)
          if g>1:  break
   return g

def lcm(*args):
    """Compute the least common multiple of some non-negative integers"""
    def lcm2(a, b):
        'compute the least common multiple of a, and b'
        if a == b: return a
        if 0 in (a,b) or 1 in (a,b):return a*b
        m,n = min(a,b), max(a,b)
        while n % m > 0 :
            m, n = divmod(n, m)[1], m
        gcd = m
        return (a*b//gcd)

    if 0 in args: return 0
    args = sorted(args, reverse=True)
    # print(args)
    res = args[0]
    for i in args:
        if res % i >0:
            res = lcm2(res, i)
        else:
            pass
        # print(res)
    return res

def exgcd(a,b):
    """
    Bézout coefficients (u,v) of (a,b) as:

        a*u + b*v = gcd(a,b)

    Result is the tuple: (u, v, gcd(a,b)). Examples:

    >>> exgcd(7*3, 15*3)
    (-2, 1, 3)
    >>> exgcd(24157817, 39088169)    #sequential Fibonacci numbers
    (-14930352, 9227465, 1)

    Algorithm source: Pierre L. Douillet
    http://www.douillet.info/~douillet/working_papers/bezout/node2.html
    """
    u,  v,  s,  t = 1, 0, 0, 1
    while b !=0:
        q, r = divmod(a,b)
        a, b = b, r
        u, s = s, u - q*s
        v, t = t, v - q*t

    return (u, v, a)

def lenstra(n, limit):
    g = n
    while g == n:
        # Randomized x and y
        q = randint(0, n - 1), randint(0, n - 1), 1
        # Randomized curve coefficient a, computed b
        a = randint(0, n - 1)
        b = (q[1] * q[1] - q[0] * q[0] * q[0] - a * q[0]) % n
        g = gcd(4 * a * a * a + 27 * b * b, n)  # singularity check
    # If we got lucky, return lucky factor
    if g > 1:
        return g
    # increase k step by step until lcm(1, ..., limit)
    for p in primes(limit):
        pp = p
        while pp < limit:
            q = elliptic_mul(p, q, a, b, n)
            # Elliptic arithmetic breaks
            if q[2] > 1:
                return gcd(q[2], n)
            pp = p * pp
    return False


# Command line tool

def distinctdegree(self):
        d = 0
        Result = []
        g = [self]
        x = self.factory.monomial(1)
        h = [x]
        while d <= ((g[d].degree() / 2) - 1):
            d = d + 1
            h.append((h[d-1]^(self.factory.q)) % g[d-1])
            aux = g[d-1].gcd(h[d] - x)
            if not aux.is_one():
                Result.append((aux,d))
            g.append(g[d-1]/aux)
        if not g[d].is_one():
            Result.append((g[d],g[d].degree()))
        return Result

def line_lattice_points(vertices):
    """ Return number of points on boundary line not including vertices
    """
    assert len(vertices)==2, "not a line: %s" % vertices
    xspan = abs(vertices[0][0] - vertices[1][0])
    yspan = abs(vertices[0][1] - vertices[1][1])
    ret = 0
    if xspan == 0 and yspan == 0:
        ret = 0
    elif xspan == 0:
        ret = yspan - 1
    elif yspan == 0:
        ret = xspan - 1
    elif xspan == yspan:
        ret = xspan - 1
    elif yspan > xspan:
        ret = gcd(yspan, xspan) - 1
    elif xspan > yspan:
        ret = gcd(xspan, yspan) - 1

    print "line_lattice_points %s=%d" % (vertices, ret)    
    return ret

def __init__(self, N=2, D=None):
        if D is None:
            D = 1
        if N < 0:
            N *= -1
            D *= -1
        if N < 2:
            raise ValueError('fraction numerator is less than 2')

        D %= N
        if D == 0:
            raise ValueError('fraction denominator is a multiple '
                             'of the numerator')
        self.parts = fractions.gcd(N, D)
        self.N = N // self.parts
        self.D = D // self.parts

def spiro(num_teeth_fixed, num_teeth_move, height, num_segs, outfile):
    N = abs(num_teeth_fixed)
    D = abs(num_teeth_move)
    side_sign = num_teeth_move/D
    height = height*D/N
    num_segs = num_segs

    turns = D/fractions.gcd(N, D)
    print('OFF\n{} 1 0'.format(num_segs), file=outfile)

    for i in range(num_segs):
        ang_fixed = 2*math.pi*turns*i/num_segs
        ang_move = side_sign * ang_fixed * N/D
        move_cent = [math.cos(ang_fixed)*(N + side_sign*D)/N,
                     math.sin(ang_fixed)*(N + side_sign*D)/N, 0]
        move_offset = [height*math.cos(ang_fixed+ang_move),
                       height*math.sin(ang_fixed+ang_move), 0]
        P = [move_cent[i] + move_offset[i] for i in range(3)]
        print(P[0], P[1], P[2], file=outfile)

    print(num_segs, *[i for i in range(num_segs)], file=outfile)

def period_to_factors(base, modulus, period):
    half_period = period // 2
    x = pow(base, half_period, modulus)
    if x**2 % modulus != 1 or x == 1 or x == -1 % modulus:
        return None

    # (x + 1) * (x - 1) = x^2 - 1^2 = 1 - 1 = 0
    # therefore (x+1)*(x-1) * k = k * modulus
    # but (x+1) and (x-1) can't be multiples of modulus
    # therefore they contain factors

    factors_1 = fractions.gcd(x + 1, modulus)
    factors_2 = fractions.gcd(x - 1, modulus)

    assert factors_1 * factors_2 == modulus
    return sorted([factors_1, factors_2])

def least_common_multiple(a, b):
    """
    Return the value of the least common multiple.
    """
    return (a * b) / gcd(a, b)



# --------------------------------------------------------
# LAYOUT

def least_common_multiple(a, b):
    """
    Return the value of the least common multiple.
    """
    return (a * b) / gcd(a, b)



# --------------------------------------------------------
# LAYOUT

def lcm(self, a: int, b: int):
        """Return the lowest common multiple of 2 numbers"""
        return a * b // gcd(a, b)

def hcf(self, a: int, b: int):
        """Return the highest common factor of 2 numbers"""
        return gcd(a,b)

def modinv(a, b):
    """Returns the modular inverse of a mod b.

    Pre: a < b and gcd(a, b) = 1

    Adapted from https://en.wikibooks.org/wiki/Algorithm_Implementation/
    Mathematics/Extended_Euclidean_algorithm#Python
    """
    saved = b
    x, y, u, v = 0, 1, 1, 0
    while a:
        q, r = b // a, b % a
        m, n = x - u*q, y - v*q
        b, a, x, y, u, v = a, r, u, v, m, n
    return x % saved

def coprime(a, b):
    """Returns True iff `gcd(a, b) == 1`, i.e. iff `a` and `b` are coprime"""
    return _fractions.gcd(a, b) == 1

def rsa_recover_prime_factors(n, e, d):
    """
    Compute factors p and q from the private exponent d. We assume that n has
    no more than two factors. This function is adapted from code in PyCrypto.
    """
    # 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

    return (p, q)

def rsa_recover_prime_factors(n, e, d):
    """
    Compute factors p and q from the private exponent d. We assume that n has
    no more than two factors. This function is adapted from code in PyCrypto.
    """
    # 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

    return (p, q)

def _lcm(a, b):
    """
    Least Common Multiple between 2 integers.
    """
    if a == 0 or b == 0:
        return 0
    else:
        return abs(a * b) // fractions.gcd(a, b)

def _check_gear_pair(g1, g2):
        assert g1.module == g2.module

        # Load sharing between teeth
        assert fractions.gcd(g1.n, g2.n) == 1