Help using Msieve library

h5law · 2022-12-03, 16:26

Hi,

I am doing some research into different integer factorisation techniques. I am a first-year CS student at uni and thought here would be a good place to seek some advice.

I am implementing the Morrison-Brillhart CFRAC method myself but have decided to use Msieve to test the NFS technique of factorising large numbers. I am wondering if there is any advice on actually using the C library out there or if anyone here could help me I can't seem to find any documentation besides the demo.c file - which I can't actually compile for some reason ahah. I can build the Msieve program itself but I need to have the output in a certain format so as to best collect my data. I am sure I am doing something wrong. I am not really experienced with C at all.

The only way I can see that happening is by using the Msieve library and formatting the output myself.

Any and all help would be greatly appreciated.

Thanks in advance.

kruoli · 2022-12-03, 17:24

Which version are you using? There is a version with a lot of improvements (especially the linked branch). And on which OS are you trying to compile it?

I am not sure about more detailed documentation; you might have to refer how msieve itself implements its NFS steps. Another program that uses the msieve-API (for post processing) is YAFU, but indeed in a weird way (a custom header file, not the header file from msieve).

VBCurtis · 2022-12-03, 23:34

Msieve doesn't do NFS, at least not in the customary way with a lattice siever. You should not expect msieve's line siever for NFS to function- development was abandoned on it over ten years ago, and it was never fast enough for useful work.

YAFU is a nice wrapper for the various phases of GNFS: msieve for polynomial selection, ggnfs for sieving, msieve again for filtering, matrix generation, matrix solving, and square root.
Yafu manages the program calls, passes parameters to the individual programs, and yields output factors.

For smaller inputs, YAFU has its own quadratic sieve implementation, as does msieve. These are fast up to around 100 digits, while yafu's is usable up to 110 or 120 but far slower than GNFS. Someone learning to implement algos would be wise to study QS before GNFS.

Sorry, no experience using the C library interface.

h5law · 2022-12-04, 18:57

Thanks for the replies! I will look into YAFU, I managed to write a wrapper for Msieve in Go to work around my output issue. I am doing research on the optimum RSA modulus size ranges for a number of different integer factorisation techniques so if Msieve is not strictly NFS I will probably have to swap it out. I looked into CADO-NFS as well for this purpose. Thanks again for the guidance!

h5law · 2022-12-04, 18:59

I am building it all on Fedora 37, I will check out the improved version you linked as well as YAFU thanks!

2022-12-03, 16:26	#1
h5law "Harry" Dec 2022 UK 3 Posts	Help using Msieve library Hi, I am doing some research into different integer factorisation techniques. I am a first-year CS student at uni and thought here would be a good place to seek some advice. I am implementing the Morrison-Brillhart CFRAC method myself but have decided to use Msieve to test the NFS technique of factorising large numbers. I am wondering if there is any advice on actually using the C library out there or if anyone here could help me I can't seem to find any documentation besides the demo.c file - which I can't actually compile for some reason ahah. I can build the Msieve program itself but I need to have the output in a certain format so as to best collect my data. I am sure I am doing something wrong. I am not really experienced with C at all. The only way I can see that happening is by using the Msieve library and formatting the output myself. Any and all help would be greatly appreciated. Thanks in advance.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
GMP Library and C IDE	Deuterium	Software	5	2022-08-27 00:20
OPN Library website	ThomRuley	Factoring	9	2021-01-04 13:40
Quickest fft library	nuggetprime	Software	3	2011-01-09 01:24
Msieve: problem linking with other C library	srawlins	Msieve	6	2010-04-02 02:05
GWNUM library and llr	leizhoucn	Programming	2	2007-11-05 09:34

2022-12-03, 17:24	#2
kruoli "Oliver" Sep 2017 Porta Westfalica, DE 2×11×61 Posts	Which version are you using? There is a version with a lot of improvements (especially the linked branch). And on which OS are you trying to compile it? I am not sure about more detailed documentation; you might have to refer how msieve itself implements its NFS steps. Another program that uses the msieve-API (for post processing) is YAFU, but indeed in a weird way (a custom header file, not the header file from msieve).

2022-12-03, 23:34	#3
VBCurtis "Curtis" Feb 2005 Riverside, CA 3³×11×19 Posts	Msieve doesn't do NFS, at least not in the customary way with a lattice siever. You should not expect msieve's line siever for NFS to function- development was abandoned on it over ten years ago, and it was never fast enough for useful work. YAFU is a nice wrapper for the various phases of GNFS: msieve for polynomial selection, ggnfs for sieving, msieve again for filtering, matrix generation, matrix solving, and square root. Yafu manages the program calls, passes parameters to the individual programs, and yields output factors. For smaller inputs, YAFU has its own quadratic sieve implementation, as does msieve. These are fast up to around 100 digits, while yafu's is usable up to 110 or 120 but far slower than GNFS. Someone learning to implement algos would be wise to study QS before GNFS. Sorry, no experience using the C library interface.

2022-12-04, 18:57	#4
h5law "Harry" Dec 2022 UK 3₁₆ Posts	Thanks for the replies! I will look into YAFU, I managed to write a wrapper for Msieve in Go to work around my output issue. I am doing research on the optimum RSA modulus size ranges for a number of different integer factorisation techniques so if Msieve is not strictly NFS I will probably have to swap it out. I looked into CADO-NFS as well for this purpose. Thanks again for the guidance!

2022-12-04, 18:59	#5
h5law "Harry" Dec 2022 UK 3 Posts	I am building it all on Fedora 37, I will check out the improved version you linked as well as YAFU thanks!