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

정의 (소수와 합성수)
    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은 합성수이다.
    

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

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

=begin
  Execution Examples:

      Prompt> ruby divideEach.rb 1234567812343
      1234567812343 = 1 * 1234567812343
      1234567812343 is a prime
      Elapsed time: 2.875000 sec
 
      Prompt> ruby divideEach.rb 9999994200000841
      9999994200000841 = 99999971 * 99999971
      9999994200000841 is a not prime
      Elapsed time: 258.906000 sec

      Prompt> ruby divideEach.rb 18446744073709551617
      18446744073709551617 = 274177 * 67280421310721
      18446744073709551617 is a not prime
      Elapsed time: 0.766000 sec

      Prompt> ruby divideEach.rb 10023859281455311421
      10023859281455311421 = 1308520867 * 7660450463
      10023859281455311421 is a not prime
      Elapsed time: 3521.562000 sec
=end

n = 10006099720301
if ARGV.length > 0:
    n = ARGV[0].to_i
end

z = n / 2
if n == 2*z
    print "%d = %d * %d\n" % [n, 2, z]
end

time1 = Time.now.to_f

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

time2 = Time.now.to_f

print "%d = %d * %d\n" % [n, d, n/d]
if d == 1
    print "%d is a prime\n" % n
else
    print "%d is a not prime\n" % n
end

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

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

#  Filename: pollardRho.rb
#
#  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: ruby pollardRho.rb [integer]
#
#     Date:  2009/03/23
#   Author:  PH Kim   [ pkim ((AT)) scripts.pe.kr ]

=begin
  Execution Examples:

      Prompt> ruby pollardRho.rb 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: 104.188000

      Prompt> ruby pollardRho.rb 9999994200000841
      Try first the Pollard rho algorithm with c = 2
      d = 99999971, count = 3593
      9999994200000841 = 99999971 * 99999971
      Elapsed time: 0.234000

      Prompt> ruby pollardRho.rb 18446744073709551617
      Try first the Pollard rho algorithm with c = 2
      d = 274177, count = 1028
      18446744073709551617 = 274177 * 67280421310721
      Elapsed time: 0.078000

      Prompt> ruby pollardRho.rb 10023859281455311421
      Try first the Pollard rho algorithm with c = 2
      d = 1308520867, count = 20350
      10023859281455311421 = 1308520867 * 7660450463
      Elapsed time: 1.531000
=end

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

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

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

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\n" % c)
    while d == 1 and count*count <= n
        x = f(x, c, n)
        if x == savedX
         print("It is cyclic.  x = %d\n" % x)
         break
        end
        y = g(y, c, n)
        d = gcd((x - y).abs, n)
        count = count + 1
        # if count % 5000 == 0
        #  print("  count = %d\n" % count)
        # end
    end

    print("d = %d, count = %d\n" % [d, count])
    if d > 1 and d < n
        return d
    end

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

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

    return d
end

n = 9991
if ARGV.length > 0
    n = ARGV[0].to_i
end

time1 = Time.now.to_f

k = pollardRho(n)
z = n/k
# if n == k*z
    print("%d = %d * %d\n" % [n, k, z])
# end

time2 = Time.now.to_f
print("Elapsed time: %f\n" % (time2 - time1))

 
 

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

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