mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-05-16, 20:57   #1
sean
 
sean's Avatar
 
Aug 2004
New Zealand

32·52 Posts
Thumbs up C151 118!+1 by GNFS finished

Today I completed the factorization of the C151 cofactor of 118!+1 by
GNFS. Total calendar time for this factorization was 49 days.

118!+1 = 46757 * 82219 * 1871263 *
11294645177647665140920980967 (Andrew Walker, 1998) *
26722464573695888110450933578985133184055013159596413387712641189727401257 *
215755998310817447135361660925170571172035520281882810599201805043440117717351

For this factorization I used the implementation of Franke, Kleinjung,
and Bahr. Polynomial selection was by Kleinjung's method. Thanks also
to Jes Hansen for scripts which made this task easier.

BEGIN POLY #skewness 221289.42 norm 8.93e+20 alpha -6.67 Murphy_E 4.66e-12
X5 72496440
X4 -8531351692062
X3 -16095568481020701977
X2 -237475459914786872640202
X1 66015102678891792487030736008
X0 8378573736183516069721926682785600
Y1 370663252551053891
Y0 -38028101219232514145714792201

I did lattice sieving for all special q between 20e6 and 93.3e6 using
factor base bounds of 16e6 on the algebraic side and 10e6 on the
rational side. The bounds for large primes were 2^32. Sieving ran
for just under a month from 2005-03-29 to 2005-04-26 on a range of
machines. After filtering the matrix was 5096931 * 5097029 which just
squeezed into 2GB RAM. My first attempt to reduce the matrix failed
when my hard-drive died (fortunately the factor data was on another
disk). The second run started on 2005-04-27 and completed on
2005-05-15. The factor was found on the third dependency.

Originally I thought this would put me safely in the top 10; but the
other two really big factorizations this month have seen this result
squeezed precariously to tenth or maybe out of the top 10 altogether
if I am missing other recent results.

RSA-200 2005 2799 C200=P100*P100 GNFS Bahr/Franke/Kleinjung/et al.
11^281+1 2005 1009 C176=P87*P89 GNFS Aoki, Kida, Shimoyama, Ueda
RSA-576 2003 1881 C174=P87*P87 GNFS Bahr/Franke/Kleinjung/Montgomery/te Riele/Leclair/Leyland/Wackerbarth
2^1826+1 2003 9758 C164=P68*P97 GNFS Aoki, Kida, Shimoyama, Sonoda, Ueda
RSA-160 2003 2152 C160=P80*P80 GNFS Bahr/Franke/Kleinjung/Lochter/Bohm
2^953+1 2002 3950 C158=P73*P86 GNFS Bahr/Franke/Kleinjung
RSA-155 1999 1094 C155=P78*P78 GNFS te Riele/CWI et al.
Code Book 2000 1074 C155=P78*P78 GNFS Almgren/Andersson/Granlund/Ivansson/Ulfberg
HP49(95) 2003 2651 C153=P68*P85 GNFS Kruppa/Leyland
118!+1 2005 5765 C151=P74*P78 GNFS Irvine
HP49(97) 2003 1268 C151=P55*P96 GNFS Kruppa/Leyland

For more information on the n!-1 and n!+1 factoring project see
http://www.uow.edu.au/%7Eajw01/ecm/curves.html

Sean Irvine
sean is offline   Reply With Quote
Old 2005-05-17, 01:06   #2
dleclair
 
dleclair's Avatar
 
Mar 2003

10011102 Posts
Default

Quote:
Today I completed the factorization of the C151 cofactor of 118!+1 by
GNFS. Total calendar time for this factorization was 49 days.
Very impressive, congratulations!

Out of curiosity, how many machines (and of what average processing power) did you use for the sieving and for the linear algebra?

In case you are interested in a significantly smaller but comparable benchmark I finished a 3.30M matrix not too long ago on an Athlon XP 2500+ in 15 days using the CWI suite.

-Don Leclair
dleclair is offline   Reply With Quote
Old 2005-05-17, 01:33   #3
sean
 
sean's Avatar
 
Aug 2004
New Zealand

32×52 Posts
Default

The matrix reduction was done on a 2.8 GHz Pentium 4 with 2GB of RAM
(which happens to be my desktop machine, so had to share this with X
etc.)

It is harder for my to characterize the CPU power available for
sieving. The specs of the machines used for sieving are as follows
but these machines are shared for our real work. I guess I averaged
about 10 GHz over the time sieving occurred.

2 * 800 MHz P-III
2 * 866 MHz P-III
2 * 2.8 GHz P-IV
1 * 3.2 GHz P-IV
1 * 1.6 GHz Athlon

In my experience the Franke lanczos implementation is faster than CWI
on Pentium machines and perhaps Athlons as well.
sean is offline   Reply With Quote
Old 2005-05-17, 03:40   #4
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

3·23 Posts
Default

Congratulations on this achievement. Just 11 bits longer and it could have been a 512-bit RSA key. It amazes me that something like this can be done with 8 or 9 commodity machines now.
trilliwig is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
137!+1 C159 finished by GNFS sean Factoring 11 2006-03-24 01:22
The factorization of 6,257+.c151 xilman NFSNET Discussion 1 2004-10-14 13:29
37M finished to 60 bit hbock Lone Mersenne Hunters 0 2004-07-21 20:30
25.48M to 25.5M up to 2^58 finished Thomas11 Lone Mersenne Hunters 0 2003-03-05 18:57
25.5M to 26M up to 2^58 finished Thomas11 Lone Mersenne Hunters 5 2003-03-04 09:55

All times are UTC. The time now is 20:33.


Tue Jan 18 20:33:03 UTC 2022 up 179 days, 15:02, 0 users, load averages: 2.18, 1.74, 1.52

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.

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