python फास्ट प्राइम कारकेशन मॉड्यूल




algorithm prime-factoring (7)

यदि आप पहिया को फिर से शुरू नहीं करना चाहते हैं, तो लाइब्रेरी sympy उपयोग करें

pip install sympy

समारोह sympy.ntheory.factorint प्रयोग करें

>>> from sympy.ntheory import factorint
>>> factorint(10**20+1)
{73: 1, 5964848081: 1, 1676321: 1, 137: 1}

आप कुछ बहुत बड़ी संख्याओं को कारक बना सकते हैं:

>>> factorint(10**100+1)
{401: 1, 5964848081: 1, 1676321: 1, 1601: 1, 1201: 1, 137: 1, 73: 1, 129694419029057750551385771184564274499075700947656757821537291527196801: 1}

मैं किसी भी पाइथन, स्यूडोकोड या अन्यथा अच्छी तरह से पठनीय में एन के प्रमुख कारककरण के लिए कार्यान्वयन या स्पष्ट एल्गोरिदम की तलाश में हूं। कुछ मांग / तथ्यों हैं:

  • एन 1 और ~ 20 अंकों के बीच है
  • कोई पूर्व-गणना की गई लुकअप तालिका नहीं है, हालांकि यादें ठीक है।
  • गणितीय साबित होने की आवश्यकता नहीं है (उदाहरण के लिए यदि आवश्यक हो तो गोल्डबैक अनुमान पर निर्भर हो सकता है)
  • सटीक होने की आवश्यकता नहीं है, यदि आवश्यक हो तो संभाव्य / निर्धारिक होने की अनुमति है

मुझे न केवल अपने लिए, बल्कि यूलर फाई (एन) की गणना करने जैसे कई अन्य एल्गोरिदम में उपयोग के लिए एक तेज़ प्राइम कारकराइजेशन एल्गोरिदम चाहिए।

मैंने विकिपीडिया से अन्य एल्गोरिदम की कोशिश की है और ऐसे में या तो मैं उन्हें समझ नहीं पाया (ईसीएम) या मैं एल्गोरिदम (पोलार्ड-ब्रेंट) से एक कार्य कार्यान्वयन नहीं कर सका।

मैं वास्तव में पोलार्ड-ब्रेंट एल्गोरिदम में रूचि रखता हूं, इसलिए इस पर कोई और जानकारी / कार्यान्वयन वास्तव में अच्छा होगा।

धन्यवाद!

संपादित करें

थोड़ा सा गड़बड़ करने के बाद मैंने एक सुंदर तेज प्राइम / कारक बनाने वाला मॉड्यूल बनाया है। यह एक अनुकूलित परीक्षण प्रभाग एल्गोरिदम, पोलार्ड-ब्रेंट एल्गोरिदम, एक मिलर-राबिन प्राइमिटी टेस्ट और इंटरनेट पर सबसे तेज़ प्राइमविइम को जोड़ता है। जीसीडी एक नियमित यूक्लिड का जीसीडी कार्यान्वयन है (बाइनरी यूक्लिड की जीसीडी नियमित रूप से धीमी है)।

इनाम

ओह खुशी, एक उपहार प्राप्त किया जा सकता है! लेकिन मैं इसे कैसे जीत सकता हूं?

  • मेरे मॉड्यूल में इष्टतमरण या बग खोजें।
  • वैकल्पिक / बेहतर एल्गोरिदम / कार्यान्वयन प्रदान करें।

उत्तर जो सबसे पूर्ण / रचनात्मक है वह बक्षीस प्राप्त करता है।

और अंत में मॉड्यूल स्वयं:

import random

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

smallprimeset = set(primesbelow(100000))
_smallprimeset = 100000
def isprime(n, precision=7):
    # http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
    if n < 1:
        raise ValueError("Out of bounds, first argument must be > 0")
    elif n <= 3:
        return n >= 2
    elif n % 2 == 0:
        return False
    elif n < _smallprimeset:
        return n in smallprimeset


    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for repeat in range(precision):
        a = random.randrange(2, n - 2)
        x = pow(a, d, n)

        if x == 1 or x == n - 1: continue

        for r in range(s - 1):
            x = pow(x, 2, n)
            if x == 1: return False
            if x == n - 1: break
        else: return False

    return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
def pollard_brent(n):
    if n % 2 == 0: return 2
    if n % 3 == 0: return 3

    y, c, m = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1)
    g, r, q = 1, 1, 1
    while g == 1:
        x = y
        for i in range(r):
            y = (pow(y, 2, n) + c) % n

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

    return g

smallprimes = primesbelow(1000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000
def primefactors(n, sort=False):
    factors = []

    for checker in smallprimes:
        while n % checker == 0:
            factors.append(checker)
            n //= checker
        if checker > n: break

    if n < 2: return factors

    while n > 1:
        if isprime(n):
            factors.append(n)
            break
        factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent
        factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent
        n //= factor

    if sort: factors.sort()

    return factors

def factorization(n):
    factors = {}
    for p1 in primefactors(n):
        try:
            factors[p1] += 1
        except KeyError:
            factors[p1] = 1
    return factors

totients = {}
def totient(n):
    if n == 0: return 1

    try: return totients[n]
    except KeyError: pass

    tot = 1
    for p, exp in factorization(n).items():
        tot *= (p - 1)  *  p ** (exp - 1)

    totients[n] = tot
    return tot

def gcd(a, b):
    if a == b: return a
    while b > 0: a, b = b, a % b
    return a

def lcm(a, b):
    return abs((a // gcd(a, b)) * b)

smallprimes का उपयोग कर primesbelow smallprimes गणना करने की कोई आवश्यकता नहीं है, इसके लिए smallprimeset उपयोग करें।

smallprimes = (2,) + tuple(n for n in xrange(3,1000,2) if n in smallprimeset)

अपने primefactors को smallprimes - smallprimes और दूसरे को pollard_brent लिए संभालने के लिए दो कार्यों में विभाजित करें, यह कुछ पुनरावृत्तियों को बचा सकता है क्योंकि छोटे-छोटे समय की सभी शक्तियां एन से विभाजित की जाएंगी।

def primefactors(n, sort=False):
    factors = []

    limit = int(n ** .5) + 1
    for checker in smallprimes:
        print smallprimes[-1]
        if checker > limit: break
        while n % checker == 0:
            factors.append(checker)
            n //= checker


    if n < 2: return factors
    else : 
        factors.extend(bigfactors(n,sort))
        return factors

def bigfactors(n, sort = False):
    factors = []
    while n > 1:
        if isprime(n):
            factors.append(n)
            break
        factor = pollard_brent(n) 
        factors.extend(bigfactors(factor,sort)) # recurse to factor the not necessarily prime factor returned by pollard-brent
        n //= factor

    if sort: factors.sort()    
    return factors

Pomerance, Selfridge और Wagstaff और Jaeschke के सत्यापित परिणामों पर विचार करके, आप मिलर-राबिन प्राथमिकता परीक्षण का उपयोग करने वाले isprime में पुनरावृत्ति को कम कर सकते हैं। Wiki से

  • यदि n <1,373,653, तो यह = 2 और 3 का परीक्षण करने के लिए पर्याप्त है;
  • यदि n <9,080,191, यह = 31 और 73 का परीक्षण करने के लिए पर्याप्त है;
  • अगर एन <4,75 9, 123,141, यह = 2, 7, और 61 का परीक्षण करने के लिए पर्याप्त है;
  • यदि n <2,152,302,898,747, तो यह = 2, 3, 5, 7, और 11 का परीक्षण करने के लिए पर्याप्त है;
  • यदि n <3,474,749,660,383, तो यह = 2, 3, 5, 7, 11, और 13 का परीक्षण करने के लिए पर्याप्त है;
  • यदि n <341,550,071,728,321, तो यह = 2, 3, 5, 7, 11, 13, और 17 का परीक्षण करने के लिए पर्याप्त है।

संपादित करें 1 : प्राइमफैक्टरों में कारकों के लिए bigfactors को जोड़ने के लिए सही वापसी कॉल।


संख्या 2**1427 * 31 फैक्टरिंग करते समय मैं बस इस कोड में एक बग में भाग गया।

  File "buckets.py", line 48, in prettyprime
    factors = primefactors.primefactors(n, sort=True)
  File "/private/tmp/primefactors.py", line 83, in primefactors
    limit = int(n ** .5) + 1
OverflowError: long int too large to convert to float

यह कोड स्निपेट:

limit = int(n ** .5) + 1
for checker in smallprimes:
    if checker > limit: break
    while n % checker == 0:
        factors.append(checker)
        n //= checker
        limit = int(n ** .5) + 1
        if checker > limit: break

में फिर से लिखा जाना चाहिए

for checker in smallprimes:
    while n % checker == 0:
        factors.append(checker)
        n //= checker
    if checker > n: break

जो वैसे भी यथार्थवादी इनपुट पर तेजी से प्रदर्शन करेगा। स्क्वायर रूट धीमा है - मूल रूप से कई smallprimes के समतुल्य - smallprimes केवल कुछ दर्जन सदस्य होते हैं, और इस तरह हम कड़े आंतरिक लूप से n ** .5 की गणना को हटाते हैं, जो निश्चित रूप से उपयोगी होता है जब फैक्टरिंग संख्या 2**1427sqrt(2**1427) , sqrt(2**1426) , sqrt(2**1425) इत्यादि की गणना करने का कोई कारण नहीं है, जब हम सभी की देखभाल करते हैं "क्या [चेकर का] वर्ग है n से अधिक "।

पुनर्लेखित कोड बड़ी संख्याओं के साथ प्रस्तुत किए जाने पर अपवाद नहीं फेंकता है, और समय timeit अनुसार लगभग दोगुना तेज़ होता है (नमूना इनपुट 2 और 2**718 * 31 )।

यह भी ध्यान दें कि isprime(2) गलत परिणाम देता है, लेकिन यह ठीक है जब तक हम उस पर भरोसा नहीं करते हैं। IMHO आपको उस फ़ंक्शन के परिचय को फिर से लिखना चाहिए

if n <= 3:
    return n >= 2
...

आप एक सीमा तक कारक बना सकते हैं और फिर उच्च कारकों को प्राप्त करने के लिए ब्रेंट का उपयोग कर सकते हैं

from fractions import gcd
from random import randint

def brent(N):
   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 factorize(n1):
    if n1==0: return []
    if n1==1: return [1]
    n=n1
    b=[]
    p=0
    mx=1000000
    while n % 2 ==0 : b.append(2);n//=2
    while n % 3 ==0 : b.append(3);n//=3
    i=5
    inc=2
    while i <=mx:
       while n % i ==0 : b.append(i); n//=i
       i+=inc
       inc=6-inc
    while n>mx:
      p1=n
      while p1!=p:
          p=p1
          p1=brent(p)
      b.append(p1);n//=p1 
    if n!=1:b.append(n)   
    return sorted(b)

from functools import reduce
#n= 2**1427 * 31 #
n= 67898771  * 492574361 * 10000223 *305175781* 722222227*880949 *908909
li=factorize(n)
print (li)
print (n - reduce(lambda x,y :x*y ,li))

आपको शायद कुछ प्रमुख पहचान करना चाहिए जो आप यहां देख सकते हैं, प्राइम नंबर खोजने के लिए फास्ट एल्गोरिदम?

आपको उस पूरे ब्लॉग को पढ़ना चाहिए, हालांकि कुछ एल्गोरिदम हैं जिन्हें उन्होंने प्रारंभिकता के परीक्षण के लिए सूचीबद्ध किया है।


वर्तमान में भी, कई स्थानों पर ध्यान दिया जाना चाहिए।

  1. checker*checker न करें checker*checker हर लूप checker*checker , s=ceil(sqrt(num)) checher < s s=ceil(sqrt(num)) और checher < s
  2. चेचर को प्रत्येक बार प्लस 2 होना चाहिए, 2 को छोड़कर सभी संख्याओं को अनदेखा करें
  3. % और // बजाय divmod प्रयोग करें





prime-factoring