mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2003-05-30, 13:48   #1
ThomRuley
 
ThomRuley's Avatar
 
May 2003

4438 Posts
Default 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? :?
ThomRuley is offline   Reply With Quote
Old 2003-05-30, 14:00   #2
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25·3 Posts
Default

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.
Axel Fox is offline   Reply With Quote
Old 2003-05-30, 14:54   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2003-05-30, 17:51   #4
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

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
smh is offline   Reply With Quote
Old 2003-05-30, 18:30   #5
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22×3×11 Posts
Default

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.
NickGlover is offline   Reply With Quote
Old 2003-05-30, 20:34   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts
Default

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.
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Automatic fetch of Trial Factoring work for GPU mfakt* LaurV GPU to 72 81 2020-12-02 05:17
Simple Script to get Trial Factoring Work jfamestad PrimeNet 3 2016-11-06 20:32
Why trial factoring work chopped into chunks? lidocorc PrimeNet 4 2008-11-06 18:48
over trial factoring JFB Software 23 2004-08-22 05:37
How does the trial factoring work with 15K*2^n-1 jocelynl 15k Search 0 2003-07-11 14:23

All times are UTC. The time now is 03:29.


Thu Oct 6 03:29:23 UTC 2022 up 49 days, 57 mins, 0 users, load averages: 1.32, 1.09, 1.09

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.

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