mersenneforum.org How does trial-factoring work?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2003-05-30, 13:48 #1 ThomRuley     May 2003 1001000112 Posts How does trial-factoring work? I had a quick question about how the trial-factoring in Prime95 works. Does the program trial-divide by prime numbers in order or does it try them randomly until one works? :?
 2003-05-30, 14:00 #2 Axel Fox     May 2003 6016 Posts Trial factoring tries all possible dividers up to a certain limit, which depends on the exponent you are testing (or which you set yourself with the FactorOverride option). However, not all prime numbers are tried, because there is a theorem that if a number divides a Mersenne number, it MUST be of the form 2*k*p+1 where p is the exponent of the number you are testing. So it only tries to devide the Mersenne by these kind of numbers. How the program tries to divide it exactly, I don't know myself. I don't know the exact algorithm for it, but I know that it is waaaay faster than just trying to numerically divide it. Axel Fox.
 2003-05-30, 14:54 #3 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×641 Posts Prime95 trial-factoring is orderly. It's designed to ensure that once it reports that there's no factor up to 2^m, it really does mean that no potential factor below 2^m divides the Mnumber it tested, so any factor of that Mnumber must be greater than 2^m.
2003-05-30, 17:51   #4
smh

"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts

Quote:
 Prime95 trial-factoring is orderly.
I'm not sure about this. I remember from the old days that the client used 16 passes while trail factoring. I believe those 16 passes are still in there.

The program does however try all numbers below a bit length before moving to the next though.

Below is a message from George to the mersenne mailing list on 08 may 1996

Quote:
 Hi all, David M. Einstein writes: > I see that your new version is facoring in two passes. I assume that these > are numbers +-1 mod 8. Your guess is correct. For those of you wondering why this is a good idea - consider a one pass algorithm that first clears every 3 mod 8 and 5 mod 8 sieve bit. Then you clear every 3rd bit, every 5th bit, etc. Well, half the time you clear a bit because it it a multiple of 3, 5, 7, etc. it was already cleared because the factor was 3 mod 8 or 5 mod 8. The two pass approach avoids this waste by using two sieves, one for the 1 mod 8 factors and another for the 7 mod 8 factors. > Would it be worthwhile to do it in 16 passes with numbers > +-1 mod 8, +-1 mod 3, +-1,2 mod 5, or even in two stages say first seiving the > interval from 0 to 8*3*5*7*11*13, and then seiving the residue classes found in the > first pass mod the other primes before 'trial dividing', or would the cost of > reinitializing the seive be too great? Good idea! It's already on my to-do list. If I remember correctly, 20% of the time spent factoring is attributed to the cost of sieving. Thus going to a four pass approach would save 1/3 of 20% or about 7%. A 16-pass approach would save a total of 9.3%. The cost of reinitializing the sieve is not that great. As was pointed out earlier, doubling the factoring speed results in a 2% overall improvement, so this item is not high on my priority list. Regards, George

2003-05-30, 18:30   #5
NickGlover

Aug 2002
Richland, WA

22·3·11 Posts

Quote:
 Originally Posted by Axel Fox How the program tries to divide it exactly, I don't know myself. I don't know the exact algorithm for it, but I know that it is waaaay faster than just trying to numerically divide it.
The algorithm is described at the top of The GIMPS Math page.

2003-05-30, 20:34   #6
cheesehead

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 I'm not sure about this. I remember from the old days that the client used 16 passes while trail factoring. I believe those 16 passes are still in there.
That's why I wrote "orderly" rather than "sequentially" or "strictly linearly". :)

And if no factor is found, then the progress as measured at the standard powers-of-2 breakpoints is sequential.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post LaurV GPU to 72 81 2020-12-02 05:17 jfamestad PrimeNet 3 2016-11-06 20:32 lidocorc PrimeNet 4 2008-11-06 18:48 JFB Software 23 2004-08-22 05:37 jocelynl 15k Search 0 2003-07-11 14:23

All times are UTC. The time now is 04:46.

Sat Feb 4 04:46:57 UTC 2023 up 170 days, 2:15, 1 user, load averages: 0.54, 0.92, 1.09

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.

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