RSA Factoring Challenge를 해결하려면 어떤 시간 복잡성이 필요합니까?

Question

도전은 오래전에 끝났지 만 다소 지겨워서 숫자 중 일부를 분석하려고하기로 결정했습니다.

처음에는 O (n) 알고리즘이 있었지만 큰 O 표기법을 연구하기로 결정했습니다.

O (n) 알고리즘과 O (2n) 알고리즘은 기본적으로 동일한 실행 시간을가집니다. O (n)과 O (4n) 알고리즘도 그렇습니다. 실제로 O (n) 및 O (cn) 알고리즘 (여기서 c는 정수)은 본질적으로 동일한 실행 시간을가집니다.

이제 O (8n) 알고리즘이 있지만 77 비트 숫자는 빠르지 않습니다.

처음 몇 개의 RSA 번호 (5-ish 분 미만)를 생성하려면 어떤 종류의 시간 복잡성이 필요합니까?

내 O (8N) 알고리즘 :

import math 

num = int(input()) 

sq = math.sqrt(num) 

if num % 2 == 0: 
    print(2, int(num/2)) 

elif sq % 1 == sq: 
    print(int(sq), int(sq)) 

else: 

    sq = round(sq) 

    a = 3 
    b = sq + (1 - (sq % 2)) 

    c = ((b + 1)/2) 
    d = ((b + 1)/2) 
    c -= (1 - (c % 2)) 
    d += (1 - (d % 2)) 

    e = ((c + 1)/2) 
    f = ((c + 1)/2) 
    e -= (1 - (e % 2)) 
    f += (1 - (f % 2)) 
    g = ((d + 1)/2) + d 
    h = ((d + 1)/2) + d 
    g -= (1 - (g % 2)) 
    h += (1 - (h % 2)) 


    while a <= sq and num % a != 0 and b > 2 and num % b != 0 and c <= sq and num % c != 0 and d > 2 and num % d != 0 and e <= sq and num % e != 0 and f > 2 and num % f != 0 and g <= sq and num % g != 0 and h > 2 and num % h != 0: 

    a += 2 
    b -= 2 
    c += 2 
    d -= 2 
    e += 2 
    f -= 2 
    g += 2 
    h -= 2 


    if num % a == 0: 
    print(a, int(num/a)) 
    elif num % b == 0: 
    print(b, int(num/b)) 
    elif num % c == 0: 
    print(c, int(num/c)) 
    elif num % d == 0: 
    print(d, int(num/d)) 
    elif num % e == 0: 
    print(e, int(num/e)) 
    elif num % f == 0: 
    print(f, int(num/f)) 
    elif num % g == 0: 
    print(g, int(num/g)) 
    elif num % h == 0: 
    print(h, int(num/h)) 

Answer 1

귀하의 알고리즘이 제대로 구현되어 재판 부문. 멀리 던져.

여기에 제 기본 소수 라이브러리가 있습니다. 에라 토 스테 네스의 체를 사용하여 소수를 나열하고, Miller-Rabin 알고리즘을 사용하여 소수를 인식하고 휠 분해를 수행 한 다음 Pollard의 rho 알고리즘을 사용하여 합성물을 배제합니다.

function primes(n) 
    i, p, ps, m := 0, 3, [2], n // 2 
    sieve := makeArray(0..m-1, True) 
    while i < m 
     if sieve[i] 
      ps := p :: ps # insert at head of list 
      for j from (p*p-3)/2 to m step p 
       sieve[i] := False 
     i, p := i+1, p+2 
    return reverse(ps) 

function isPrime(n, k=5) 
    if n < 2 then return False 
    for p in [2,3,5,7,11,13,17,19,23,29] 
     if n % p == 0 then return n == p 
    s, d = 0, n-1 
    while d % 2 == 0 
     s, d = s+1, d/2 
    for i from 0 to k 
     x = powerMod(randint(2, n-1), d, n) 
     if x == 1 or x == n-1 then next i 
     for r from 1 to s 
      x = (x * x) % n 
      if x == 1 then return False 
      if x == n-1 then next i 
     return False 
    return True 

function factors(n, limit=10000) 
    wheel := [1,2,2,4,2,4,2,4,6,2,6] 
    w, f, fs := 0, 2, [] 
    while f*f <= n and f < limit 
     while n % f == 0 
      fs, n := f :: fs, n/f 
     f, w := f + wheel[w], w+1 
     if w = 11 then w = 3 
    if n == 1 return fs 
    h, t, g, c := 1, 1, 1, 1 
    while not isPrime(n) 
     repeat 
      h := (h*h+c) % n # the hare runs 
      h := (h*h+c) % n # twice as fast 
      t := (t*t+c) % n # as the tortoise 
      g := gcd(t-h, n) 
     while g == 1 
     if isPrime(g) 
      while n % g == 0 
       fs, n := g :: fs, n/g 
     h, t, g, c := 1, 1, 1, c+1 
    return sort(n :: fs) 

function powerMod(b, e, m) 
    x := 1 
    while e > 0 
     if e%2 == 1 
      x, e := (x*b)%m, e-1 
     else b, e := (b*b)%m, e//2 
    return x 

function gcd(a, b) 
    if b == 0 then return a 
    return gcd(b, a % b) 

올바르게 구현 된 알고리즘은 79 비트 수를 거의 즉시 고려해야합니다.

큰 숫자를 계산하려면 더 열심히해야합니다. 자신을 구현할 수있는 인수 분해 알고리즘을 찾으려면 "타원 곡선 인수 분해"및 "자가 초기화 2 차 체"를 찾으십시오.