mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-05-17, 12:55   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

645410 Posts
Default Have a look at the partition numbers

If you want the opportunity of running ECM 24/7 and getting a freshly-baked factor per CPU in your inbox most mornings, can I commend to you the partition numbers from

http://www.asahi-net.or.jp/~KC2H-MSM/mathland/part/

I am currently clearing up the 13000-13500 range and running ECM on the 20000-21000 range, but in other ranges there are literally thousands of numbers as small as C101 that have seen only ECM with B1=50k, and others that have been well-ECMed and are just sitting there begging to be GNFSed. Come on in, fill your boots!

There *are* interesting divisibility properties to be found among the partition numbers: the famous 5|p(5n+4), 7|p(7n+5), 11|p(11n+6), and infinitely many (see http://www.sciencenews.org/articles/20050618/bob9.asp ) weirder ones (for example, part(17303n+237) is divisible by 13), but I'm fairly sure they don't apply for factors this big; on the other hand, there being no strong mathematical use for the factors is scarcely a disincentive for other factorisation projects.

Trying to sound like an advocate for the Oregon Trail,

Tom

Last fiddled with by fivemack on 2007-05-17 at 13:21
fivemack is offline   Reply With Quote
Old 2007-05-17, 13:19   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts
Default

Quote:
Originally Posted by fivemack View Post
If you want the opportunity of running ECM 24/7 and getting a freshly-baked factor per CPU in your inbox most mornings, can I commend to you the partition numbers from

http://www.asahi-net.or.jp/~KC2H-MSM/mathland/part/

I am currently clearing up the 13000-13500 range and running ECM on the 20000-21000 range, but in other ranges there are literally thousands of numbers as small as C100 that have seen only ECM with B1=50k, and even some small enough that QS is the right method. Come on in, fill your boots!

There *are* interesting divisibility properties to be found among the partition numbers: the famous 5|p(5n+4), 7|p(7n+5), 11|p(11n+6), and infinitely many (see http://www.sciencenews.org/articles/20050618/bob9.asp ) weirder ones (for example, part(17303n+237) is divisible by 13), but I'm fairly sure they don't apply for factors this big; on the other hand, there being no strong mathematical use for the factors is scarcely a disincentive for other factorisation projects.

Trying to sound like an advocate for the Oregon Trail,

Tom
You should be aware that the partition numbers were part of the RSA
Challenge contest back in the 90's. They were restricted to those
with prime indices, but a VERY LARGE NUMBER of them were fully factored.
Check the RSA website to see if the data is still available.

I will check to see if I still have a copy of the data.

Bob
R.D. Silverman is offline   Reply With Quote
Old 2007-05-17, 13:36   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
You should be aware that the partition numbers were part of the RSA
Challenge contest back in the 90's. They were restricted to those
with prime indices, but a VERY LARGE NUMBER of them were fully factored.
Check the RSA website to see if the data is still available.

I will check to see if I still have a copy of the data.

Bob
That data has already been merged into Mishima's tables; at least, I looked at http://www.ontko.com/~rayo/primes/ to get the RSA-challenge data, then grepped the Mishima tables for some of the largish factors from http://www.ontko.com/~rayo/primes/hr_p135.txt and found them all.
fivemack is offline   Reply With Quote
Old 2007-05-17, 14:17   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

11101010010002 Posts
Default

Quote:
Originally Posted by fivemack View Post
That data has already been merged into Mishima's tables; at least, I looked at http://www.ontko.com/~rayo/primes/ to get the RSA-challenge data, then grepped the Mishima tables for some of the largish factors from http://www.ontko.com/~rayo/primes/hr_p135.txt and found them all.
That is good news. I am glad that the data did not get lost.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-17, 15:34   #5
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

9B216 Posts
Default

Reserving 14984 c104 for msieve (QS)
Andi47 is offline   Reply With Quote
Old 2007-05-17, 15:56   #6
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

24×3×101 Posts
Default

Quote:
Originally Posted by Andi47 View Post
Reserving 14984 c104 for msieve (QS)
Should we tell Mishima about our reservation?

Luigi
ET_ is offline   Reply With Quote
Old 2007-05-17, 16:36   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default

I don't think there are all that many people working on these numbers ... contributions this year have, with one exception, been by me or by Hisanori Mishima himself, which is really why I posted here to drum up more interest. It would be nice to tell him about the reservations, but he manages the site manually so we don't want to overload him entirely.
fivemack is offline   Reply With Quote
Old 2007-05-17, 16:39   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

Out of curiosity, I collected all the cofactors together, and did 35 rounds of GCD(product of half the cofactors selected at random, product of the other half), all of which returned 1. So I think it's quite unlikely (IE there are about 2^24 pairs, and for any pair the probability is 2^-34 that both were on the same side all 35 times) that any number will divide more than one of the cofactors.
fivemack is offline   Reply With Quote
Old 2007-05-17, 18:46   #9
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

9B216 Posts
Default

Reserving 29328 c101 and 28819 c102 (as an attempt to compare msieve's QS and GNFS with numbers in similar size)
Andi47 is offline   Reply With Quote
Old 2007-05-17, 19:04   #10
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

4A516 Posts
Default

Quote:
Originally Posted by fivemack View Post
I don't think there are all that many people working on these numbers ... contributions this year have, with one exception, been by me or by Hisanori Mishima himself, which is really why I posted here to drum up more interest. It would be nice to tell him about the reservations, but he manages the site manually so we don't want to overload him entirely.
I've done quite a few last year before cleaning up the small composites on the cyclotomic tables. Most < 110 digits are done now (I did 7-800 between 100 and 110 digits in the last few months) so i might return to the partition tables. Most composites above 20K haven't had enough ecm though. Last time i found quite a few factors with GNFS in the 30 digit range.

I also has been a long time i did any numbers of the (Generalized) Cullen and Woodall numbers so i might return there first.
smh is offline   Reply With Quote
Old 2007-05-17, 20:02   #11
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
You should be aware that the partition numbers were part of the RSA
Challenge contest back in the 90's. They were restricted to those
with prime indices, but a VERY LARGE NUMBER of them were fully factored.
Check the RSA website to see if the data is still available.

I will check to see if I still have a copy of the data.

Bob
As I recall, Paul Zimmermann and Arjen are still waiting for the
last quarter's prize. We quit when the prizes were no longer
being given. But my recollection is that there was another round
of factors waiting for the quarter to finish (to be eligible for the next
quarter's prize), and that some of the later ones that we did
submit never got included.

I can check, but it has been quite some time. Again, we were only
doing the ones of prime index (the thought being that there were
too many of each given size, otherwise). Also, aside from the wish
that there might be instances of new congruences/divisibilities found,
these are (iirc) only gnfs candidates, with no chance of snfs --- that
was one of the appeals, in our case. Most of our early gnfs trials were
taken from the partition list, the first ones for gnfs above c110,
including c112, c119, c116 from our Crypto'95 paper on the cycle explosion
(gnfs with four large primes). -Bruce

PS -- sentance fragment patched. There are also some of our
factors on one of Brent's early pages, from back when he was taking all
ecm factors above p40 (especially the year or two when we were
working toward p50, finished with Curry's p53).

Last fiddled with by bdodson on 2007-05-17 at 20:12 Reason: "memory rot" - cf. Thurston's version of "bit rot".
bdodson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fun with partition function Batalov And now for something completely different 49 2022-08-04 12:08
Carmichael numbers and Devaraj numbers devarajkandadai Number Theory Discussion Group 0 2017-07-09 05:07
Partition number congruences fivemack Math 0 2007-05-18 19:39
Linux/SUSE noob trouble - Resize partition OmbooHankvald Linux 19 2005-11-18 10:39
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25

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


Thu Dec 1 19:32:49 UTC 2022 up 105 days, 17:01, 0 users, load averages: 1.69, 1.19, 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.

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