mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-10-17, 14:39   #1
mak
 
Oct 2009

210 Posts
Exclamation Msieve documentation

How can I view the complete technical documentation Msieve? For example comments and description of techniques implemented in Msieve. I want to make the modification program, but first you need to get acquainted with those that already exist, can our algorithm as it will accelerate the factorization, the existing algorithms. Thank you!
mak is offline   Reply With Quote
Old 2009-10-17, 15:47   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

5·709 Posts
Default

There is no technical documentation for msieve outside comments in the code. My spare time is so limited that I cannot afford to both write and document.

I'd be happy to answer any questions you may have...
jasonp is offline   Reply With Quote
Old 2009-10-20, 14:00   #3
mak
 
Oct 2009

216 Posts
Default

Can you describe briefly nested factorization technique? With a further description of the program, I make it out. I'll see with what I can work, and can modify the technique
mak is offline   Reply With Quote
Old 2009-10-20, 20:43   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

5·709 Posts
Default

If you mean the top-level factorization driver in driver.c, this is intended to deal with any input size by calling the appropriate algorithm, then proceeding recursively on any unfactored numbers once the factorization succeeds. Some algorithms will find small factors no matter how big the input, and others can only split an input into two (possibly composite) factors. So the procedure is therefore:
Code:
- run trial division
- run Pollard rho
- put the unfactored part remaining into a factor_list_t structure
- run ECM

for each composite number in the structure {
   test if number is a perfect power (QS and NFS won't work if it is)
   if number is small 
        use SQUFOF or a tiny QS routine
   else
        use the main QS code (and eventually use NFS if the number
        is larger than QS can be expected to handle)

   put any factors found into the factor_list_t; the act of doing
   so will remove all instances of the new factor from all numbers
   currently in the factor_list_t. Also, if GCD(new factor, old factors) > 1
   then remove the common part from the new factor and add it into
   the factor_list_t as well

   if all numbers in the factor_list_t are prime or probable prime, we're done
}
This kind of complexity was very surprising to me, but it's necessary if you want to completely factor any input with no wasted work, finding as many factors at a time as possible. What do you have in mind for improving it?
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Manual Testing LL result syntax (where to find documentation) preda GPU Computing 15 2017-04-17 15:02
Using msieve with c burrobert Msieve 9 2012-10-26 22:46
msieve help em99010pepe Msieve 23 2009-09-27 16:13
Documentation on the [worker #] section of local. edron1011 Software 5 2008-10-31 00:17
C++ documentation Guilherme Programming 2 2004-12-29 15:16

All times are UTC. The time now is 18:39.


Fri May 27 18:39:13 UTC 2022 up 43 days, 16:40, 0 users, load averages: 2.17, 2.20, 1.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

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