mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2022-12-03, 16:26   #1
h5law
 
h5law's Avatar
 
"Harry"
Dec 2022
UK

3 Posts
Default 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.
h5law is offline   Reply With Quote
Old 2022-12-03, 17:24   #2
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

2×11×61 Posts
Default

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).
kruoli is online now   Reply With Quote
Old 2022-12-03, 23:34   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

33×11×19 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2022-12-04, 18:57   #4
h5law
 
h5law's Avatar
 
"Harry"
Dec 2022
UK

316 Posts
Default

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 is offline   Reply With Quote
Old 2022-12-04, 18:59   #5
h5law
 
h5law's Avatar
 
"Harry"
Dec 2022
UK

3 Posts
Default

I am building it all on Fedora 37, I will check out the improved version you linked as well as YAFU thanks!
h5law is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 19:10.


Tue Feb 7 19:10:34 UTC 2023 up 173 days, 16:39, 1 user, load averages: 0.53, 0.83, 0.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔