C o C++: librerie per il factoring degli interi?

Sembra che ci siano diversi algoritmi di fattorizzazione primaria molto veloci in giro (uno che sembra ideale per la quadratura). Tuttavia, piuttosto che implementare la mia (probabilmente povera) implementazione, mi piacerebbe utilizzare una libreria già pronta per la semplicità.C o C++: librerie per il factoring degli interi?

Devo essere in grado di calcolare in modo efficiente numeri interi fino a 15 cifre. Per questo motivo, non sto cercando l'algoritmo che si adatta necessariamente asintoticamente meglio poiché possiamo supporre che i numeri presi in considerazione siano inferiori a 10 .

ho già avuto uno sguardo ad alcune delle implementazioni quotate in Wikipedia's Quadratic Sieve page. Tuttavia, alcune delle implementazioni non sembrano ben mantenute; alcuni non hanno documentazione; e così via! Ho controllato se alcune librerie conosciute, come Boost, avessero metodi di fattorizzazione, ma non sembra.

Qualcuno può consigliare una libreria che soddisfi i criteri sopra indicati?

fonte

2009-05-24 Anonymous

"Le domande che ci chiedono di consigliare o trovare un libro, uno strumento, una libreria di software, un'esercitazione o altre risorse fuori sede sono off-topic per Stack Overflow in quanto tendono ad attirare risposte e spam. e cosa è stato fatto finora per risolverlo. " – genpfault

@genpfault L'account dell'OP è stato cancellato ... questa domanda ha 8 anni. – qxz

Partenza MSIEVE libreria per fattorizzazione di grandi numeri da Jason Papadopoulos.

Msieve è il risultato dei miei sforzi per comprendere e ottimizzare il modo in cui gli interi vengono calcolati utilizzando i più potenti algoritmi moderni.

Questa documentazione corrisponde alla versione 1.46 della libreria Msieve. Non aspettarti di diventare un esperto di factoring solo leggendolo. Ho incluso un elenco relativamente completo di riferimenti che è possibile e dovrebbe cercare se si desidera trattare il codice come più di una scatola nera per risolvere i problemi di factoring.

fonte

2009-05-24 12:15:25

Ancora una volta, non riesco a trovare alcuna documentazione reale su di esso. Non sono sicuro di come si integrerebbe con il mio programma e, quindi, se avrebbe funzionato! –

Beh, ho detto che potresti ... :) Mi interessa anche la fattorizzazione. La fattorizzazione è un problema difficile e probabilmente sarà difficile trovare una libreria documentata e * veloce *. –

Sono d'accordo; soprattutto con l'esclusività quasi reciproca di documentazione e velocità di un progetto. ;) –

-1

Che ne dici di GMP-ECM?

fonte

2009-05-24 11:21:52

Non riesco a trovare alcun documento (la sua sezione "Documenti" è vuota). Il suo nome sembra anche suggerire che usa GMP per memorizzare interi. Preferirei usare interi a 64 bit (dato che corro su un computer a 64 bit). –

Hai controllato il file readme.lib nella distribuzione di origine? Non è la documentazione più dettagliata, ma spiega come funziona. (Tuttavia, usa gmp, e non interi a 64 bit). – Soroosh

C o C++: librerie per il factoring degli interi?

risposta

Problemi correlati