mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2013-02-15, 19:21   #1
mahnouman
 
Feb 2013

23 Posts
Smile Best Way to find large factors

Hello,
Which tests are more likely to find out large factors:
Trial Factoring or P-1?

I know that a trial factoring test will run for a day or so, what about P-1 tests, how long usually they run for?

Best Regards
mahnouman is offline   Reply With Quote
Old 2013-02-15, 19:45   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160358 Posts
Default

Mmm. About equal, on a wall clock time basis. (At least, even to within a factor of 2, I think.)

If you're trying to decide which worktype to do, with a CPU, P-1 is definitely way more in demand.
Dubslow is offline   Reply With Quote
Old 2013-02-15, 19:54   #3
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25×149 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Mmm. About equal, on a wall clock time basis. (At least, even to within a factor of 2, I think.)

If you're trying to decide which worktype to do, with a CPU, P-1 is definitely way more in demand.
...especially if you have lots of RAM.

Luigi
ET_ is offline   Reply With Quote
Old 2013-02-15, 21:34   #4
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

63008 Posts
Default

You mention large factors. It becomes inefficient and infeasible for trial factoring to look further than about 2^70 for CPUs or 2^73 for GPUs in the range of Mersenne numbers currently being fully tested for primality, but P-1 factoring can turn up much larger factors than this if you are lucky.
Brian-E is offline   Reply With Quote
Old 2013-02-15, 21:54   #5
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

296710 Posts
Default

P-1 will also run in around 1 day (anywhere from 12 hours to 2-3 days probably) depending on how much RAM you give it and how fast your CPU is.

It's almost a "waste" now to trialfactor on a CPU since GPU's are so much faster at it and P-1 is more needed atm, but it is of course up to you what you want to do.

For P-1 you should give at least 300 Mb RAM for every thread that runs P-1, and the more the better.
ATH is offline   Reply With Quote
Old 2013-02-15, 22:10   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160358 Posts
Default

Quote:
Originally Posted by Brian-E View Post
You mention large factors. It becomes inefficient and infeasible for trial factoring to look further than about 2^70 for CPUs or 2^73 for GPUs in the range of Mersenne numbers currently being fully tested for primality, but P-1 factoring can turn up much larger factors than this if you are lucky.
<insert ATH's avatar here>

Of course this is a much better response to OP's question. Sorry OP

Here's some links with "interesting" P-1 factors. "Bits" means log base 2 of the factor, so the number of characters in its binary representation (which is roughly log2(10)~3.3 as many times as decimal digits). As Brian mentions, TF can only go up to 73 or 74 bits effectively, while these (admittedly rare) P-1 factors are north of 100 bits. Even discounting these rare ones, almost any P-1 job that finds a factor (somewhere between 1 in 20 and 1 in 60) will be larger than what TF can find.
Dubslow is offline   Reply With Quote
Old 2013-02-17, 16:12   #7
flashjh
 
flashjh's Avatar
 
"Jerry"
Nov 2011
Vancouver, WA

21438 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Even discounting these rare ones, almost any P-1 job that finds a factor (somewhere between 1 in 20 and 1 in 60) will be larger than what TF can find.
It will always be larger if TF was done properly.

[clarification]edit: properly = without error
[/clarification]

Last fiddled with by flashjh on 2013-02-17 at 16:13
flashjh is offline   Reply With Quote
Old 2013-02-17, 19:48   #8
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

63008 Posts
Default

Quote:
Originally Posted by flashjh View Post
It will always be larger if TF was done properly.

[clarification]edit: properly = without error
[/clarification]
Is that true now? It didn't use to be. P-1 used to be performed before the last bit or two of TF, so theoretically the P-1 factoring could find a factor which the subsequent TF would otherwise have found.
Brian-E is offline   Reply With Quote
Old 2013-02-17, 20:20   #9
flashjh
 
flashjh's Avatar
 
"Jerry"
Nov 2011
Vancouver, WA

1,123 Posts
Default

I don't remember that, but it's possible that was done because it was mathematically better to P-1 before spending more CPU time on TF.
flashjh is offline   Reply With Quote
Old 2013-02-17, 20:36   #10
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

26×3×17 Posts
Default

Quote:
Originally Posted by flashjh View Post
I don't remember that, but it's possible that was done because it was mathematically better to P-1 before spending more CPU time on TF.
Yes, that was the reason. I appreciate that the TF situation has changed radically since GPUto72 began, and I know you are very heavily involved in that yourself, whilst I am not, so I was just wondering how it works nowadays with the timing of the P-1 factoring relative to the extra TF bits which GPUs can turn in.
Brian-E is offline   Reply With Quote
Old 2013-02-17, 21:28   #11
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

Quote:
Originally Posted by flashjh View Post
It will always be larger if TF was done properly.

[clarification]edit: properly = without error
[/clarification]
I meant what was in the realm of possibility. So, for instance, P-1 could find a low-75 bit factor (or 74 bit) -- that's within the range of what TF *can* do, even if no exponents are supposed to be taken that high.
Dubslow is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Find factors for non base2 candidates pepi37 GMP-ECM 2 2017-03-07 20:13
Fails to find very small factors. Mr. P-1 FactorDB 6 2013-03-22 02:30
What way would you find numbers with a set number of factors? nibble4bits Puzzles 18 2006-01-07 10:40
How to find factors I found with TF? edorajh PrimeNet 3 2004-10-01 19:16
How large a factor can P-1 testing find ? dsouza123 Software 3 2003-12-11 00:48

All times are UTC. The time now is 09:16.

Fri Oct 23 09:16:09 UTC 2020 up 43 days, 6:27, 0 users, load averages: 1.38, 1.69, 1.75

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