Pollard's rho method 소개: 정수의 인수분해(factorizing integers) with Python

정의 (소수와 합성수)
    1보다 큰 양의 정수 n에 대하여
    (i) n = a * b 를 만족하고 1보다 큰 두 양의 정수 a와 b가 존재하면,
        n을 합성수(合成數, composite number)라고 한다. 참고로 이 경우,
        a, b 중에 적어도 하나는 sqrt(n) 보다 작거나 같다.
        합성수의 예로는 4, 6, 9, 24, 143 등이 있다.
    (ii) n = a * b 를 만족하고 1보다 큰 두 양의 정수 a와 b가 존재하지 않으면,
         즉 n을 두 양의 정수의 곱으로 표현하는 방법이 1*n과 n*1 두 가지 뿐이면,
         n을 소수(素數, prime number)라고 한다.  소수의 예로는 2, 3, 5, 7, 11 등이 있다.
         n이 소수인지 아닌지 확인하려면, 
         n을 2 보다 크거나 같고 sqrt(n) 보다 작거나 같은 모든 정수로 나누어 본다.
         이 경우 언제나 나누어 떨어지지  않으면 n은 소수이고, 그렇지 않으면 n은 합성수이다.
    

우선 다음의 Python 소스 코드는 명령행 인자로 전달 받은 양의 정수 n을
2 및 3, 5, 7, ... , sqrt(n) 이하의 홀수들로 나누어 보아 n이 합성수인지 아닌지
확인하는 애플리케이션 소스이다. 확인하는데 걸린 경과 시간도 알려준다.

#  Filename: divideEach.py
#
#  Purpose:  Determine whether the given integer is a prime or not.
#
#  Execute: python divideEach.py [integer]
#
#     Date:  2009/03/23
#   Author:  PH Kim   [ pkim ((AT)) scripts.pe.kr ]

"""
  Execution Examples:
      Prompt> python divideEach.py 1234567812343
      1234567812343 = 1 * 1234567812343
      1234567812343 is a prime
      Elapsed time: 0.562000 sec
 
      Prompt> python divideEach.py 9999994200000841
      9999994200000841 = 99999971 * 99999971
      9999994200000841 is a not prime
      Elapsed time: 51.437000 sec
 
      Prompt> python divideEach.py 18446744073709551617
      18446744073709551617 = 274177 * 67280421310721
      18446744073709551617 is a not prime
      Elapsed time: 0.141000 sec

      Prompt> python divideEach.py 10023859281455311421
      10023859281455311421 = 1308520867 * 7660450463
      10023859281455311421 is a not prime
      Elapsed time: 705.016000 sec
 """

import sys
import math
from time import *

n = 10006099720301
if len(sys.argv) > 1:
    n = int(sys.argv[1])

z = int(n / 2)
if n == 2*z:
    print "%d = %d * %d" % (n, 2, z)

time1 = time()

d = 1
k = 3
while k*k <= n:
    z = n // k
    if n == k*z:
        d = k
        break
    k = k + 2

time2 = time()

print "%d = %d * %d" % (n, d, n/d)
if d == 1:
    print "%d is a prime" % n
else:
    print "%d is a not prime" % n

print "Elapsed time: %f sec" % (time2 - time1)

이제 다음은 정수의 인수분해 능력이 뛰어난  Pollard의 rho 방법(일명 거북이와 토끼 알고리즘, tortoise-hair algorithm)을 구현한  Python 소스 코드이다. 이 알고리즘은 소수에 대해서는 시간이 많이 걸리지만, 합성수에 대해서는 시간이 매우 적게 걸린다는 것이 특징이다.

 

#  Filename: pollardRho.py
#
#  Purpose:  By using the pollard rho method,
#            determine whether the given integer is a prime or not.
#
#      See:  http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
#            http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare#
#
#  Execute: python pollardRho.py [integer]
#
#     Date:  2009/03/23
#   Author:  PH Kim   [ pkim ((AT)) scripts.pe.kr ]

"""
  Execution Examples:
      Prompt> python pollardRho.py 1234567812343
      Try first the Pollard rho algorithm with c = 2
      d = 1234567812343, count = 466951
      Try second the Pollard rho algorithm with c = 3
      d = 1, count = 1111112
      Try third the Pollard rho algorithm with c = 1
      d = 1234567812343, count = 799441
      1234567812343 = 1234567812343 * 1
      Elapsed time: 28.656000 sec

      Prompt> python pollardRho.py 9999994200000841
      Try first the Pollard rho algorithm with c = 2
      d = 99999971, count = 3593
      9999994200000841 = 99999971 * 99999971
      Elapsed time: 0.062000 sec

      Prompt> python pollardRho.py 18446744073709551617
      Try first the Pollard rho algorithm with c = 2
      d = 274177, count = 1028
      18446744073709551617 = 274177 * 67280421310721
      Elapsed time: 0.016000 sec

      Prompt> python pollardRho.py 10023859281455311421
      Try first the Pollard rho algorithm with c = 2
      d = 1308520867, count = 20350
      10023859281455311421 = 1308520867 * 7660450463
      Elapsed time: 0.375000 sec
"""

import sys
from time import *

def f(x, c, n):
    return (x*x + c) % n

def g(x, c, n):
    return f(f(x, c, n), c, n)

def gcd(x, y):
    a = abs(x)
    b = abs(y)
    if b == 0:
        return a
    while b != 0:
        t = a % b
        a = b
        b = t
    return a

def pollardRho(n):
    c = 2
    x = 1
    y = 1
    d = 1
    savedX = x
    count = 0
    print "Try first the Pollard rho algorithm with c = %d" % c
    while d == 1 and count*count <= n:
        x = f(x, c, n)
        if x == savedX:
         print "It is cyclic.  x = %d" % x
         break
        y = g(y, c, n)
        d = gcd(abs(x - y), n)
        count = count + 1
        # if count % 5000 == 0:
        #  print "  count = %d" % count

    print "d = %d, count = %d" % (d, count)
    if d > 1 and d < n:
        return d

    c = 3
    x = 1
    y = 1
    d = 1
    savedX = x
    count = 0
    print "Try second the Pollard rho algorithm with c = %d" % c
    while d == 1 and count*count <= n:
        x = f(x, c, n)
        if x == savedX:
         print "It is cyclic.  x = %d" % x
         break
        y = g(y, c, n)
        d = gcd(abs(x - y), n)
        count = count + 1
        # if count % 5000 == 0:
        #  print "  : count = %d" % count

    print "d = %d, count = %d" % (d, count)
    if d > 1 and d < n:
        return d

    c = 1
    x = 1
    y = 1
    d = 1
    savedX = x
    count = 0
    print "Try third the Pollard rho algorithm with c = %d" % c
    while d == 1 and count*count <= n:
        x = f(x, c, n)
        if x == savedX:
         print "It is cyclic.  x = %d" % x
         break
        y = g(y, c, n)
        d = gcd(abs(x - y), n)
        count = count + 1
        # if count % 5000 == 0:
        #  print "  : count = %d" % count

    print "d = %d, count = %d" % (d, count)

    return d

n = 9991
if len(sys.argv) > 1:
    n = int(sys.argv[1])

time1 = time()

k = pollardRho(n)

time2 = time()

z = n/k
if n == k*z:
    print "%d = %d * %d" % (n, k, z)

print "Elapsed time: %f sec" % (time2 - time1)

 

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.