C o C++: ¿Bibliotecas para factorizar enteros?

Parece que hay varios algoritmos de factorización primos realmente rápidos (uno que parece ideal es el tamizado cuadrático). Sin embargo, en lugar de realizar mi propia implementación (probablemente deficiente), me gustaría utilizar una biblioteca preparada para simplificar.C o C++: ¿Bibliotecas para factorizar enteros?

Necesito factorizar enteros de hasta 15 dígitos de manera eficiente. Por eso, no estoy buscando el algoritmo que necesariamente escala asintóticamente mejor, ya que podemos suponer que los números que se factorizan son menos de 10 .

Ya he echado un vistazo a algunas de las implementaciones enumeradas en Wikipedia's Quadratic Sieve page. Sin embargo, algunas implementaciones no parecen estar bien mantenidas; algunos no tienen documentación; ¡y así! Comprobé si algunas bibliotecas conocidas, como Boost, tenían métodos de factorización pero no parecen.

¿Alguien puede recomendar una biblioteca que cumpla con los criterios anteriores?

Fuente

2009-05-24 Anonymous

"Las preguntas que nos piden que recomiendemos o busquemos un libro, herramienta, biblioteca de software, tutorial u otro recurso externo están fuera del tema de Stack Overflow ya que tienden a atraer respuestas obstinadas y correo no deseado. y lo que se ha hecho hasta ahora para resolverlo ". – genpfault

@genpfault La cuenta de OP se ha eliminado ... esta pregunta tiene 8 años. – qxz

Echa un vistazo a MSIEVE biblioteca para factorizar números enteros grandes de Jason Papadopoulos.

Msieve es el resultado de mis esfuerzos para comprender y optimizar la forma en enteros se tienen en cuenta el uso de los más poderosos algoritmos modernos.

Esta documentación corresponde a la versión 1.46 de la biblioteca Msieve. No esperes convertirte en un experto en factoraje solo leyéndolo. Tengo incluida una lista relativamente completa de referencias que usted puede y debe buscar si desea tratar el código como más que un recuadro negro para resolver sus problemas de factorización.

Fuente

2009-05-24 12:15:25

Una vez más, no puedo encontrar ninguna documentación real sobre él. No estoy seguro de cómo se integraría con mi programa y, por lo tanto, si funcionaría. –

Bueno, dije que podrías ... :) También estoy interesado en la factorización. La factorización es un problema difícil y probablemente será difícil encontrar una biblioteca documentada y * rápida *. –

Estoy de acuerdo; especialmente con la exclusividad casi mutua de la documentación y la velocidad de un proyecto. ;) –

-1

¿Qué tal GMP-ECM?

Fuente

2009-05-24 11:21:52

No puedo encontrar ningún documento sobre eso (su sección "Documentos" está vacía). Su nombre también parece insinuar que utiliza GMP para almacenar enteros. Preferiría usar enteros de 64 bits (dado que corro en una computadora de 64 bits). –

¿Revisó el archivo readme.lib en la distribución fuente? No es la documentación más detallada, pero explica cómo funciona. (Sin embargo, usa gmp, y no enteros de 64 bits). – Soroosh

C o C++: ¿Bibliotecas para factorizar enteros?

Respuesta

Cuestiones relacionadas