Factorisation semi-prime la plus rapide

Écrivez un programme pour factoriser un nombre semi-premier en un minimum de temps.

À des fins de test, utilisez ceci: 38! +1 (523022617466601111760007224100074291200000001)

Il est égal à: 14029308060317546154181 × 37280713718589679646221

Python (avec PyPy JIT v1.9) ~ 1,9 s

Utilisation d'un tamis quadratique polynomial multiple . J'ai considéré cela comme un défi de code, j'ai donc choisi de ne pas utiliser de bibliothèques externes (autres que la logfonction standard , je suppose). Lors du chronométrage, le PyPy JIT doit être utilisé, car il se traduit par des synchronisations 4 à 5 fois plus rapides que celles de cPython .

Mise à jour (2013-07-29):
depuis la publication initiale, j'ai apporté plusieurs modifications mineures, mais importantes, qui augmentent la vitesse globale d'un facteur d'environ 2,5 fois.

Mise à jour (2014-08-27):
Étant donné que ce message continue de recevoir de l'attention, j'ai mis à jour la my_math.pycorrection de deux erreurs, pour tous ceux qui pourraient l'utiliser:

• isqrtétait défectueux, produisant parfois une sortie incorrecte pour des valeurs très proches d'un carré parfait. Cela a été corrigé et les performances ont augmenté en utilisant une bien meilleure graine.
• is_primea été mis à jour. Ma tentative précédente de supprimer un carré parfait de 2 sprps était au mieux timide. J'ai ajouté une vérification 3 sprp - une technique utilisée par Mathmatica - pour s'assurer que la valeur testée est sans carré.

Mise à jour (2014-11-24):
Si à la fin du calcul aucune congruence non triviale n'est trouvée, le programme tamise maintenant des polynômes supplémentaires. Cela était auparavant marqué dans le code comme TODO.

mpqs.py

from my_math import *
from math import log
from time import clock
from argparse import ArgumentParser

# Multiple Polynomial Quadratic Sieve
def mpqs(n, verbose=False):
  if verbose:
    time1 = clock()

  root_n = isqrt(n)
  root_2n = isqrt(n+n)

  # formula chosen by experimentation
  # seems to be close to optimal for n < 10^50
  bound = int(5 * log(n, 10)**2)

  prime = []
  mod_root = []
  log_p = []
  num_prime = 0

  # find a number of small primes for which n is a quadratic residue
  p = 2
  while p < bound or num_prime < 3:

    # legendre (n|p) is only defined for odd p
    if p > 2:
      leg = legendre(n, p)
    else:
      leg = n & 1

    if leg == 1:
      prime += [p]
      mod_root += [int(mod_sqrt(n, p))]
      log_p += [log(p, 10)]
      num_prime += 1
    elif leg == 0:
      if verbose:
        print 'trial division found factors:'
        print p, 'x', n/p
      return p

    p = next_prime(p)

  # size of the sieve
  x_max = len(prime)*60

  # maximum value on the sieved range
  m_val = (x_max * root_2n) >> 1

  # fudging the threshold down a bit makes it easier to find powers of primes as factors
  # as well as partial-partial relationships, but it also makes the smoothness check slower.
  # there's a happy medium somewhere, depending on how efficient the smoothness check is
  thresh = log(m_val, 10) * 0.735

  # skip small primes. they contribute very little to the log sum
  # and add a lot of unnecessary entries to the table
  # instead, fudge the threshold down a bit, assuming ~1/4 of them pass
  min_prime = int(thresh*3)
  fudge = sum(log_p[i] for i,p in enumerate(prime) if p < min_prime)/4
  thresh -= fudge

  if verbose:
    print 'smoothness bound:', bound
    print 'sieve size:', x_max
    print 'log threshold:', thresh
    print 'skipping primes less than:', min_prime

  smooth = []
  used_prime = set()
  partial = {}
  num_smooth = 0
  num_used_prime = 0
  num_partial = 0
  num_poly = 0
  root_A = isqrt(root_2n / x_max)

  if verbose:
    print 'sieving for smooths...'
  while True:
    # find an integer value A such that:
    # A is =~ sqrt(2*n) / x_max
    # A is a perfect square
    # sqrt(A) is prime, and n is a quadratic residue mod sqrt(A)
    while True:
      root_A = next_prime(root_A)
      leg = legendre(n, root_A)
      if leg == 1:
        break
      elif leg == 0:
        if verbose:
          print 'dumb luck found factors:'
          print root_A, 'x', n/root_A
        return root_A

    A = root_A * root_A

    # solve for an adequate B
    # B*B is a quadratic residue mod n, such that B*B-A*C = n
    # this is unsolvable if n is not a quadratic residue mod sqrt(A)
    b = mod_sqrt(n, root_A)
    B = (b + (n - b*b) * mod_inv(b + b, root_A))%A

    # B*B-A*C = n <=> C = (B*B-n)/A
    C = (B*B - n) / A

    num_poly += 1

    # sieve for prime factors
    sums = [0.0]*(2*x_max)
    i = 0
    for p in prime:
      if p < min_prime:
        i += 1
        continue
      logp = log_p[i]

      inv_A = mod_inv(A, p)
      # modular root of the quadratic
      a = int(((mod_root[i] - B) * inv_A)%p)
      b = int(((p - mod_root[i] - B) * inv_A)%p)

      k = 0
      while k < x_max:
        if k+a < x_max:
          sums[k+a] += logp
        if k+b < x_max:
          sums[k+b] += logp
        if k:
          sums[k-a+x_max] += logp
          sums[k-b+x_max] += logp

        k += p
      i += 1

    # check for smooths
    i = 0
    for v in sums:
      if v > thresh:
        x = x_max-i if i > x_max else i
        vec = set()
        sqr = []
        # because B*B-n = A*C
        # (A*x+B)^2 - n = A*A*x*x+2*A*B*x + B*B - n
        #               = A*(A*x*x+2*B*x+C)
        # gives the congruency
        # (A*x+B)^2 = A*(A*x*x+2*B*x+C) (mod n)
        # because A is chosen to be square, it doesn't need to be sieved
        val = sieve_val = A*x*x + 2*B*x + C

        if sieve_val < 0:
          vec = set([-1])
          sieve_val = -sieve_val

        for p in prime:
          while sieve_val%p == 0:
            if p in vec:
              # keep track of perfect square factors
              # to avoid taking the sqrt of a gigantic number at the end
              sqr += [p]
            vec ^= set([p])
            sieve_val = int(sieve_val / p)

        if sieve_val == 1:
          # smooth
          smooth += [(vec, (sqr, (A*x+B), root_A))]
          used_prime |= vec
        elif sieve_val in partial:
          # combine two partials to make a (xor) smooth
          # that is, every prime factor with an odd power is in our factor base
          pair_vec, pair_vals = partial[sieve_val]
          sqr += list(vec & pair_vec) + [sieve_val]
          vec ^= pair_vec
          smooth += [(vec, (sqr + pair_vals[0], (A*x+B)*pair_vals[1], root_A*pair_vals[2]))]
          used_prime |= vec
          num_partial += 1
        else:
          # save partial for later pairing
          partial[sieve_val] = (vec, (sqr, A*x+B, root_A))
      i += 1

    num_smooth = len(smooth)
    num_used_prime = len(used_prime)

    if verbose:
      print 100 * num_smooth / num_prime, 'percent complete\r',

    if num_smooth > num_used_prime:
      if verbose:
        print '%d polynomials sieved (%d values)'%(num_poly, num_poly*x_max*2)
        print 'found %d smooths (%d from partials) in %f seconds'%(num_smooth, num_partial, clock()-time1)
        print 'solving for non-trivial congruencies...'

      used_prime_list = sorted(list(used_prime))

      # set up bit fields for gaussian elimination
      masks = []
      mask = 1
      bit_fields = [0]*num_used_prime
      for vec, vals in smooth:
        masks += [mask]
        i = 0
        for p in used_prime_list:
          if p in vec: bit_fields[i] |= mask
          i += 1
        mask <<= 1

      # row echelon form
      col_offset = 0
      null_cols = []
      for col in xrange(num_smooth):
        pivot = col-col_offset == num_used_prime or bit_fields[col-col_offset] & masks[col] == 0
        for row in xrange(col+1-col_offset, num_used_prime):
          if bit_fields[row] & masks[col]:
            if pivot:
              bit_fields[col-col_offset], bit_fields[row] = bit_fields[row], bit_fields[col-col_offset]
              pivot = False
            else:
              bit_fields[row] ^= bit_fields[col-col_offset]
        if pivot:
          null_cols += [col]
          col_offset += 1

      # reduced row echelon form
      for row in xrange(num_used_prime):
        # lowest set bit
        mask = bit_fields[row] & -bit_fields[row]
        for up_row in xrange(row):
          if bit_fields[up_row] & mask:
            bit_fields[up_row] ^= bit_fields[row]

      # check for non-trivial congruencies
      for col in null_cols:
        all_vec, (lh, rh, rA) = smooth[col]
        lhs = lh   # sieved values (left hand side)
        rhs = [rh] # sieved values - n (right hand side)
        rAs = [rA] # root_As (cofactor of lhs)
        i = 0
        for field in bit_fields:
          if field & masks[col]:
            vec, (lh, rh, rA) = smooth[i]
            lhs += list(all_vec & vec) + lh
            all_vec ^= vec
            rhs += [rh]
            rAs += [rA]
          i += 1

        factor = gcd(list_prod(rAs)*list_prod(lhs) - list_prod(rhs), n)
        if factor != 1 and factor != n:
          break
      else:
        if verbose:
          print 'none found.'
        continue
      break

  if verbose:
    print 'factors found:'
    print factor, 'x', n/factor
    print 'time elapsed: %f seconds'%(clock()-time1)
  return factor

if __name__ == "__main__":
  parser =ArgumentParser(description='Uses a MPQS to factor a composite number')
  parser.add_argument('composite', metavar='number_to_factor', type=long,
      help='the composite number to factor')
  parser.add_argument('--verbose', dest='verbose', action='store_true',
      help="enable verbose output")
  args = parser.parse_args()

  if args.verbose:
    mpqs(args.composite, args.verbose)
  else:
    time1 = clock()
    print mpqs(args.composite)
    print 'time elapsed: %f seconds'%(clock()-time1)

my_math.py

# divide and conquer list product
def list_prod(a):
  size = len(a)
  if size == 1:
    return a[0]
  return list_prod(a[:size>>1]) * list_prod(a[size>>1:])

# greatest common divisor of a and b
def gcd(a, b):
  while b:
    a, b = b, a%b
  return a

# modular inverse of a mod m
def mod_inv(a, m):
  a = int(a%m)
  x, u = 0, 1
  while a:
    x, u = u, x - (m/a)*u
    m, a = a, m%a
  return x

# legendre symbol (a|m)
# note: returns m-1 if a is a non-residue, instead of -1
def legendre(a, m):
  return pow(a, (m-1) >> 1, m)

# modular sqrt(n) mod p
# p must be prime
def mod_sqrt(n, p):
  a = n%p
  if p%4 == 3:
    return pow(a, (p+1) >> 2, p)
  elif p%8 == 5:
    v = pow(a << 1, (p-5) >> 3, p)
    i = ((a*v*v << 1) % p) - 1
    return (a*v*i)%p
  elif p%8 == 1:
    # Shank's method
    q = p-1
    e = 0
    while q&1 == 0:
      e += 1
      q >>= 1

    n = 2
    while legendre(n, p) != p-1:
      n += 1

    w = pow(a, q, p)
    x = pow(a, (q+1) >> 1, p)
    y = pow(n, q, p)
    r = e
    while True:
      if w == 1:
        return x

      v = w
      k = 0
      while v != 1 and k+1 < r:
        v = (v*v)%p
        k += 1

      if k == 0:
        return x

      d = pow(y, 1 << (r-k-1), p)
      x = (x*d)%p
      y = (d*d)%p
      w = (w*y)%p
      r = k
  else: # p == 2
    return a

#integer sqrt of n
def isqrt(n):
  c = n*4/3
  d = c.bit_length()

  a = d>>1
  if d&1:
    x = 1 << a
    y = (x + (n >> a)) >> 1
  else:
    x = (3 << a) >> 2
    y = (x + (c >> a)) >> 1

  if x != y:
    x = y
    y = (x + n/x) >> 1
    while y < x:
      x = y
      y = (x + n/x) >> 1
  return x

# strong probable prime
def is_sprp(n, b=2):
  if n < 2: return False
  d = n-1
  s = 0
  while d&1 == 0:
    s += 1
    d >>= 1

  x = pow(b, d, n)
  if x == 1 or x == n-1:
    return True

  for r in xrange(1, s):
    x = (x * x)%n
    if x == 1:
      return False
    elif x == n-1:
      return True

  return False

# lucas probable prime
# assumes D = 1 (mod 4), (D|n) = -1
def is_lucas_prp(n, D):
  P = 1
  Q = (1-D) >> 2

  # n+1 = 2**r*s where s is odd
  s = n+1
  r = 0
  while s&1 == 0:
    r += 1
    s >>= 1

  # calculate the bit reversal of (odd) s
  # e.g. 19 (10011) <=> 25 (11001)
  t = 0
  while s:
    if s&1:
      t += 1
      s -= 1
    else:
      t <<= 1
      s >>= 1

  # use the same bit reversal process to calculate the sth Lucas number
  # keep track of q = Q**n as we go
  U = 0
  V = 2
  q = 1
  # mod_inv(2, n)
  inv_2 = (n+1) >> 1
  while t:
    if t&1:
      # U, V of n+1
      U, V = ((U + V) * inv_2)%n, ((D*U + V) * inv_2)%n
      q = (q * Q)%n
      t -= 1
    else:
      # U, V of n*2
      U, V = (U * V)%n, (V * V - 2 * q)%n
      q = (q * q)%n
      t >>= 1

  # double s until we have the 2**r*sth Lucas number
  while r:
    U, V = (U * V)%n, (V * V - 2 * q)%n
    q = (q * q)%n
    r -= 1

  # primality check
  # if n is prime, n divides the n+1st Lucas number, given the assumptions
  return U == 0

# primes less than 212
small_primes = set([
    2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
   73, 79, 83, 89, 97,101,103,107,109,113,
  127,131,137,139,149,151,157,163,167,173,
  179,181,191,193,197,199,211])

# pre-calced sieve of eratosthenes for n = 2, 3, 5, 7
indices = [
    1, 11, 13, 17, 19, 23, 29, 31, 37, 41,
   43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
   89, 97,101,103,107,109,113,121,127,131,
  137,139,143,149,151,157,163,167,169,173,
  179,181,187,191,193,197,199,209]

# distances between sieve values
offsets = [
  10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6,
   6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4,
   2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
   4, 2, 4, 6, 2, 6, 4, 2, 4, 2,10, 2]

max_int = 2147483647

# an 'almost certain' primality check
def is_prime(n):
  if n < 212:
    return n in small_primes

  for p in small_primes:
    if n%p == 0:
      return False

  # if n is a 32-bit integer, perform full trial division
  if n <= max_int:
    i = 211
    while i*i < n:
      for o in offsets:
        i += o
        if n%i == 0:
          return False
    return True

  # Baillie-PSW
  # this is technically a probabalistic test, but there are no known pseudoprimes
  if not is_sprp(n, 2): return False

  # idea shamelessly stolen from Mathmatica
  # if n is a 2-sprp and a 3-sprp, n is necessarily square-free
  if not is_sprp(n, 3): return False

  a = 5
  s = 2
  # if n is a perfect square, this will never terminate
  while legendre(a, n) != n-1:
    s = -s
    a = s-a
  return is_lucas_prp(n, a)

# next prime strictly larger than n
def next_prime(n):
  if n < 2:
    return 2
  # first odd larger than n
  n = (n + 1) | 1
  if n < 212:
    while True:
      if n in small_primes:
        return n
      n += 2

  # find our position in the sieve rotation via binary search
  x = int(n%210)
  s = 0
  e = 47
  m = 24
  while m != e:
    if indices[m] < x:
      s = m
      m = (s + e + 1) >> 1
    else:
      e = m
      m = (s + e) >> 1

  i = int(n + (indices[m] - x))
  # adjust offsets
  offs = offsets[m:] + offsets[:m]
  while True:
    for o in offs:
      if is_prime(i):
        return i
      i += o

Exemple d'E / S:

$ pypy mpqs.py --verbose 94968915845307373740134800567566911
smoothness bound: 6117
sieve size: 24360
log threshold: 14.3081031579
skipping primes less than: 47
sieving for smooths...
144 polynomials sieved (7015680 values)
found 405 smooths (168 from partials) in 0.513794 seconds
solving for non-trivial congruencies...
factors found:
216366620575959221 x 438925910071081891
time elapsed: 0.685765 seconds

$ pypy mpqs.py --verbose 523022617466601111760007224100074291200000001
smoothness bound: 9998
sieve size: 37440
log threshold: 15.2376302725
skipping primes less than: 59
sieving for smooths...
428 polynomials sieved (32048640 values)
found 617 smooths (272 from partials) in 1.912131 seconds
solving for non-trivial congruencies...
factors found:
14029308060317546154181 x 37280713718589679646221
time elapsed: 2.064387 seconds

Remarque: ne pas utiliser l' --verboseoption donnera des délais légèrement meilleurs:

$ pypy mpqs.py 94968915845307373740134800567566911
216366620575959221
time elapsed: 0.630235 seconds

$ pypy mpqs.py 523022617466601111760007224100074291200000001
14029308060317546154181
time elapsed: 1.886068 seconds

Concepts de base

En général, un tamis quadratique est basé sur l'observation suivante: tout composite impair n peut être représenté comme:

Ce n'est pas très difficile à confirmer. Puisque n est impair, la distance entre deux cofacteurs quelconques de n doit être pair 2d , où x est le point médian entre eux. De plus, la même relation vaut pour tout multiple de n

Notez que si de tels x et d peuvent être trouvés, il en résultera immédiatement un facteur (pas nécessairement premier) de n , car x + d et x - d divisent tous deux n par définition. Cette relation peut être encore affaiblie - en conséquence de permettre des congruences triviales potentielles - à la forme suivante:

Donc en général, si nous pouvons trouver deux carrés parfaits qui sont équivalents mod n , alors il est assez probable que nous puissions produire directement un facteur de n à la gcd (x ± d, n) . Semble assez simple, non?

Sauf que ce n'est pas le cas. Si nous avions l'intention de mener une recherche exhaustive sur tous les x possibles , nous aurions besoin de rechercher toute la plage de [ √ n , √ ( 2n ) ], qui est légèrement plus petite que la division d'essai complète, mais nécessite également une is_squareopération coûteuse à chaque itération jusqu'à confirmer la valeur de d . À moins que l'on sache à l'avance que n a des facteurs très proches de √ n , la division d'essai sera probablement plus rapide.

Peut-être pouvons-nous affaiblir encore plus cette relation. Supposons que nous choisissions un x , tel que pour

une factorisation complète de y est facilement connue. Si nous avions suffisamment de telles relations, nous devrions pouvoir construire un d adéquat , si nous choisissons un nombre de y tel que leur produit soit un carré parfait; c'est-à-dire que tous les facteurs premiers sont utilisés un nombre pair de fois. En fait, si nous avons plus de tels y que le nombre total de facteurs premiers uniques qu'ils contiennent, une solution est garantie d'exister; Il devient un système d'équations linéaires. La question devient maintenant, comment choisissons-nous un tel x ? C'est là que le tamisage entre en jeu.

Le tamis

Considérez le polynôme:

Alors pour tout p premier et entier k , ce qui suit est vrai:

Cela signifie qu'après avoir résolu les racines du mod polynomial p - c'est-à-dire que vous avez trouvé un x tel que y (x) ≡ 0 (mod p) , ergo y est divisible par p - alors vous avez trouvé un nombre infini de tels x . De cette façon, vous pouvez passer au crible une plage de x , en identifiant les petits facteurs premiers de y , en espérant trouver certains pour lesquels tous les facteurs premiers sont petits. Ces nombres sont connus sous le nom de k-smooth , où k est le plus grand facteur premier utilisé.

Il y a cependant quelques problèmes avec cette approche. Toutes les valeurs de x ne sont pas adéquates, en fait, il n'y en a que très peu, centrées autour de √ n . Les valeurs plus petites deviendront largement négatives (en raison du terme -n ), et les valeurs plus grandes deviendront trop grandes, de sorte qu'il est peu probable que leur factorisation principale ne soit constituée que de petits nombres premiers. Il y aura un certain nombre de ces x , mais à moins que le composite que vous factorisez soit très petit, il est très peu probable que vous trouviez suffisamment de lissages pour entraîner une factorisation. Et donc, pour un n plus grand , il devient nécessaire de tamiser plusieurs polynômes d'une forme donnée.

Polynômes multiples

Il nous faut donc plus de polynômes pour tamiser? Que dis-tu de ça:

Ça va marcher. Notez que A et B peuvent littéralement être n'importe quelle valeur entière, et les calculs sont toujours valables. Tout ce que nous devons faire est de choisir quelques valeurs aléatoires, de résoudre la racine du polynôme et de tamiser les valeurs proches de zéro. À ce stade, nous pourrions simplement dire que c'est assez bon: si vous jetez suffisamment de pierres dans des directions aléatoires, vous risquez de briser une fenêtre tôt ou tard.

Sauf qu'il y a aussi un problème avec ça. Si la pente du polynôme est grande à l'ordonnée à l'origine, ce qu'elle sera si elle n'est pas relativement plate, il n'y aura que quelques valeurs appropriées à tamiser par polynôme. Cela fonctionnera, mais vous finirez par tamiser beaucoup de polynômes avant d'obtenir ce dont vous avez besoin. Pouvons-nous faire mieux?

On peut faire mieux. Une observation, à la suite de Montgomery est la suivante: si A et B sont choisis de telle sorte qu'il existe un certain C satisfaisant

alors le polynôme entier peut être réécrit

De plus, si A est choisi pour être un carré parfait, le premier terme A peut être négligé pendant le tamisage, ce qui donne des valeurs beaucoup plus petites et une courbe beaucoup plus plate. Pour qu'une telle solution existe, n doit être un résidu quadratique mod √ A , qui peut être connu immédiatement en calculant le symbole de Legendre :
( n | √A ) = 1 . Notez que pour résoudre B , une factorisation complète de √A doit être connue (afin de prendre la racine carrée modulaire √n (mod √A) ), c'est pourquoi √A est généralement choisi pour être premier.

On peut alors montrer que si , alors pour toutes les valeurs de x ∈ [ -M, M ] :

Et maintenant, enfin, nous avons tous les composants nécessaires pour mettre en œuvre notre tamis. Ou le faisons-nous?

Pouvoirs des primes comme facteurs

Notre tamis, comme décrit ci-dessus, a un défaut majeur. Il peut identifier quelles valeurs de x résulteront en un y divisible par p , mais il ne peut pas identifier si oui ou non ce y est divisible par une puissance de p . Afin de déterminer cela, nous aurions besoin d'effectuer une division d'essai sur la valeur à tamiser, jusqu'à ce qu'elle ne soit plus divisible par p . Nous semblions avoir atteint une impasse: tout l'intérêt du tamis était de ne pas avoir à le faire. Il est temps de vérifier le playbook.

Cela semble assez utile. Si la somme de ln de tous les petits facteurs premiers de y est proche de la valeur attendue de ln (y) , alors il est presque certain que y n'a pas d'autres facteurs. De plus, si nous ajustons un peu la valeur attendue, nous pouvons également identifier des valeurs aussi lisses qui ont plusieurs puissances de nombres premiers comme facteurs. De cette façon, nous pouvons utiliser le tamis comme un processus de «présélection» et ne prendre en compte que les valeurs susceptibles d'être lisses.

Cela présente également quelques autres avantages. Notez que les petits nombres premiers contribuent très peu à la somme ln , mais pourtant ils nécessitent le plus de temps de tamisage. Le tamisage de la valeur 3 nécessite plus de temps que 11, 13, 17, 19 et 23 combinés . Au lieu de cela, nous pouvons simplement ignorer les premiers nombres premiers et ajuster le seuil en conséquence, en supposant qu'un certain pourcentage d'entre eux aurait passé.

Un autre résultat est qu'un certain nombre de valeurs seront autorisées à passer, qui sont pour la plupart lisses, mais contiennent un seul grand cofacteur. Nous pourrions simplement supprimer ces valeurs, mais supposons que nous ayons trouvé une autre valeur généralement lisse, avec exactement le même cofacteur. Nous pouvons alors utiliser ces deux valeurs pour construire un y utilisable ; puisque leur produit contiendra ce grand cofacteur au carré, il n'est plus nécessaire de le considérer.

Mettre tous ensemble

La dernière chose que nous devons faire est d'utiliser ces valeurs de y pour construire un x et un d adéquats . Supposons que nous ne considérions que les facteurs non carrés de y , c'est-à-dire les facteurs premiers d'une puissance impaire. Ensuite, chaque y peut être exprimé de la manière suivante:

qui peut s'exprimer sous forme matricielle:

Le problème devient alors de trouver un vecteur v tel que vM = ⦳ (mod 2) , où ⦳ est le vecteur nul. C'est, pour résoudre l'espace null gauche de M . Cela peut être fait de plusieurs manières, la plus simple étant d'effectuer une élimination gaussienne sur M ^T , en remplaçant l'opération d'addition de ligne par un xor de ligne . Il en résultera un certain nombre de vecteurs de base d'espace nul, dont toute combinaison produira une solution valide.

La construction de x est assez simple. C'est simplement le produit de Ax + B pour chacun des y utilisés. La construction de d est un peu plus compliquée. Si nous devions prendre le produit de tout y , nous finirons avec une valeur de 10s de milliers, sinon de 100s de milliers de chiffres, pour laquelle nous devons trouver la racine carrée. Cette calcination est peu coûteuse. Au lieu de cela, nous pouvons suivre les puissances paires des nombres premiers pendant le processus de tamisage, puis utiliser les opérations et et xor sur les vecteurs de facteurs non carrés pour reconstruire la racine carrée.

Il me semble avoir atteint la limite de 30000 caractères. Ahh bien, je suppose que c'est assez bon.

Eh bien, votre 38! +1 a cassé mon script php, je ne sais pas pourquoi. En fait, tout semi-prime de plus de 16 chiffres rompt mon script.

Cependant, en utilisant 8980935344490257 (86028157 * 104395301), mon script a réussi un temps de 25,963 secondes sur mon ordinateur personnel (2,61 GHz AMD Phenom 9950). Beaucoup plus rapide que mon ordinateur de travail qui était de près de 31 secondes à 2,93 GHz Core 2 Duo.

php - 757 caractères incl. nouvelles lignes

<?php
function getTime() {
    $t = explode( ' ', microtime() );
    $t = $t[1] + $t[0];
    return $t;
}
function isDecimal($val){ return is_numeric($val) && floor($val) != $val;}
$start = getTime();
$semi_prime = 8980935344490257;
$slice      = round(strlen($semi_prime)/2);
$max        = (pow(10, ($slice))-1);
$i          = 3;
echo "\nFactoring the semi-prime:\n$semi_prime\n\n";

while ($i < $max) {
    $sec_factor = ($semi_prime/$i);
    if (isDecimal($sec_factor) != 1) {
        $mod_f = bcmod($i, 1);
        $mod_s = bcmod($sec_factor, 1);
        if ($mod_f == 0 && $mod_s == 0) {
            echo "First factor = $i\n";
            echo "Second factor = $sec_factor\n";
            $end=getTime();
            $xtime=round($end-$start,4).' seconds';
            echo "\n$xtime\n";
            exit();
        }
    }
    $i += 2;
}
?>

Je serais intéressé de voir ce même algorithme en c ou dans un autre langage compilé.