GCD de um par de produtos

8

Eu tenho dois números, que são cada um o produto de um grande número de números menores que eu conheço. Quero encontrar o MDC (maior divisor comum) desses dois números. Existe alguma maneira de fazer uso da fatoração parcial que tenho para acelerar o processo?

Em particular, cada número maior é o produto de números menores, cada um da ordem de . Não sei nada sobre a fatoração de números menores.21524000

Editar: Enquanto os números de entrada são de cerca de 120.000.000 de bits, o GCD é de cerca de 500.000 de bits. Os fatores dos números são particularmente em sequência. Todos são números inteiros em um intervalo consecutivo.

Todos os algoritmos GCD que eu vi usam os números diretamente, não de forma parcialmente fatorada ou algo assim. Existem algoritmos que poderiam incorporar essas informações para acelerar as coisas?

algorithms number-theory performance isaacg
fonte
Então, só para esclarecer, seus produtos têm algo como 130.000.000 de bits? Estou meio curioso sobre o motivo pelo qual você deseja encontrar GCDs de números dessa magnitude.
precisa saber é o seguinte
@DavidRicherby Isso mesmo. Estou tentando maneiras de resolver o problema aproximado de GCD, que é um problema criptográfico no qual as pessoas construíram sistemas de criptografia. Resolver grandes problemas de GCD é uma maneira de resolver problemas aproximados de tamanho razoável.
Isaacg
1
Possivelmente relacionado: cs.stackexchange.com/q/75387/755 , cs.stackexchange.com/q/28044/755 , factorable.net/weakkeys12.extended.pdf , cr.yp.to/factorization/smoothparts-20040510.pdf , cr.yp.to/smallfactors.html , cr.yp.to/lineartime/dcba-20040404.pdf . Assintoticamente, você pode calcular os MDCs em tempo quase linear, para que não haja muito espaço para acelerar se nos preocuparmos apenas com assintóticos, embora possa haver na prática, pois os assintóticos podem ser enganosos devido às constantes envolvidas.
DW
@DW Atualmente, estou usando o algoritmo GCD quase linear do GMP.
Isaacg

Respostas:

1

Você pode calcular os GCDs aos pares dos fatores. Você precisa dividir as GCDs dos fatores para evitar encontrar o mesmo fator GCD duas vezes:

a[1...m] = [given factors of A]
b[1...n] = [given factors of B]
g = 1
for i from 1 to m do
    c = a[i]
    for j from 1 to n do
        d = gcd(c, b[j])
        g = g * d
        c = a[i] / d
        b[j] = b[j] / d
return g

Infelizmente, acho que isso não é notavelmente mais rápido que o cálculo do MDC dos dois números A e B.

Clemens
fonte
0

Houve um problema semelhante que foi resolvido de maneira razoavelmente eficiente: suponha que você esteja usando o RSA, que é todo construído em produtos de dois primos grandes, nos quais os produtos não podem ser fatorados em tempo razoável. Mas se você tiver dois produtos pq e p'q 'e p = p' ou q = q ', poderá calcular o MDC e obter p = p' ou q = q 'e o outro fator é trivial. Obviamente, se p = p 'e também q = q', então isso não ajuda.

Não imagine que alguém gere um bilhão desses produtos e seja um pouco descuidado. Um hacker descobre que alguns números são idênticos, então p = p 'e q = q', então é um bom palpite que alguns pares tenham um gcd ≠ 1. E isso aconteceu na vida real com roteadores cuja criptografia poderia ser rachado como resultado.

Desculpe, não tenho nenhuma referência e a história é um pouco antiga, mas você deve encontrá-la. Faz alguns anos, talvez seis ou mais.

gnasher729
fonte
Infelizmente, nenhum dos fatores dos dois números é igual, então não posso tirá-los dessa maneira.
Isaacg