Factorizations of Cyclotomic Numbers

since 21 January 1999 Counter - 20,000

Update

Whatsnew, history, errata (September 16, 2013)

(These results are updating so frequently. Please check every day.)

These numbers are under computation. (September 16, 2013)

(To avoid duplication, please check above numbers.)

Old logs (index)

2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999

How to compute the Cyclotomic Numbers

Table 2

φ(n)nCunningham formlast updateunfactoredwho are factoring
60 61x61- 1Sep. 17, 2012Complete !!!Katsuyuki Okeya, Andy Steward,
Masaki Ukai (last number)
77x77- 1Mar. 23, 2013Complete !!!Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara, Tomoya Adachi,
Masaki Ukai (last number)
93x93- 1May. 11, 2013118Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara, Tomoya Adachi, Masaki Ukai
99x99- 1Nov. 27, 2012Complete !!!Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara,
Tomoya Adachi (last number)
122x61+ 1Aug. 16, 2012Complete !!!Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara,
Tomoya Adachi (last number)
124x62+ 1Jun. 24, 2012Complete !!!Aiichi Yamasaki, Katsuyuki Okeya,
Tomoya Adachi (last number)
154x77+ 1Dec. 13, 2011Complete !!!Aiichi Yamasaki, Hisanori Mishima, Takahiro Nohara,
Tomoya Adachi (last number)
186x93+ 1Jul. 25, 2009Complete !!!Aiichi Yamasaki, Hisanori Mishima, Joe Leherbauer,
Tomoya Adachi (last number)
198x99+ 1Sep. 15, 2008Complete !!!Aiichi Yamasaki, Hisanori Mishima, Joe Leherbauer,
Tomoya Adachi (last number)
64 85x85- 1Nov. 27, 2012284Tetsuya Kobayashi, Hisanori Mishima
128x64+ 1Oct. 09, 2010Complete !!!David A. Miller, Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima,
Tomoya Adachi (last number)
136x68+ 1Jul. 17, 2012333Tetsuya Kobayashi, Hisanori Mishima
160x80+ 1Mar. 04, 2013136Tetsuya Kobayashi, Takahiro Nohara
170x85+ 1Jul. 17, 2012362Tetsuya Kobayashi, Satoshi Tomabechi, Hisanori Mishima
192x96+ 1Sep. 17, 2012361Tetsuya Kobayashi, David A. Miller
204x102+ 1Sep. 17, 2012352Tetsuya Kobayashi, Satoshi Tomabechi, Joe Leherbauer, Hisanori Mishima, Tomoya Adachi
240x120+ 1Sep. 17, 2012338Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima, Tomoya Adachi
66 67x67- 1Jan. 29, 2013342Sinkiti Sibata, Sean Irvine, Hisanori Mishima, Tomoya Adachi
134x67+ 1Sep. 17, 2012381Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima, Tomoya Adachi
70 71x71- 1Dec. 27, 2012395Tetsuya Kobayashi, Masaki Ukai, Andy Steward, Sean Irvine, Tomoya Adachi
142x71+ 1May 07, 2012310Tetsuya Kobayashi, Tomoya Adachi

Table 3

φ(n)nCunningham formlast updateunfactoredwho's factoring
72 73x73- 1Jan. 31, 2013320 
91x91- 1Sep. 17, 2012452 
95x95- 1Sep. 17, 2012439 
111x111- 1Sep. 17, 2012394 
117x117- 1Sep. 17, 2012402 
135x135- 1Apr. 17, 2013441 
146x73+ 1Sep. 17, 2012386 
148x74+ 1Sep. 17, 2012473 
152x76+ 1Sep. 17, 2012485 
182x91+ 1May 07, 2012466 
190x95+ 1Sep. 17, 2012490 
216x108+ 1Sep. 17, 2012523 
222x111+ 1Nov. 04, 2008514 
228x114+ 1Sep. 17, 2012436 
234x117+ 1Sep. 17, 2012495 
252x126+ 1Sep. 17, 2012509 
270x135+ 1Sep. 17, 2012520 
78 79x79- 1Sep. 17, 2012520 
158x79+ 1Sep. 17, 2012552 
80 123x123- 1Sep. 17, 2012577 
164x82+ 1Nov. 23, 2011543 
165x165- 1Nov. 23, 2011502 
176x88+ 1Sep. 17, 2012517 
200x100+ 1Sep. 17, 2012587 
220x110+ 1Sep. 17, 2012531 
246x123+ 1Nov. 23, 2011548 
264x132+ 1May 07, 2012583 
300x150+ 1Sep. 17, 2012561 
330x165+ 1Nov. 23, 2011576 

Table 4

φ(n)nCunningham formlast updateunfactoredwho's factoring
82 83x83- 1Jan. 07, 2013479 
166x83+ 1Sep. 17, 2012539 
84 129x129- 1May 11, 2013588 
147x147- 1May 11, 2013565 
172x86+ 1May 11, 2013534 
196x98+ 1May 11, 2013558 
258x129+ 1May 11, 2013570 
294x147+ 1May 11, 2013612 
88 89x89- 1Aug. 09, 2012612 
115x115- 1Dec. 27, 2012674 
178x89+ 1Sep. 17, 2012647 
184x92+ 1Nov. 23, 2011621 
230x115+ 1Nov. 23, 2011677 
276x138+ 1Nov. 23, 2011637 
92 141x141- 1Nov. 23, 2011615 
188x94+ 1Nov. 23, 2011617 
282x141+ 1Nov. 23, 2011638 
96 97x97- 1May 16, 2013634 
119x119- 1Dec. 27, 2012631 
153x153- 1Nov. 23, 2011638 
194x97+ 1Jul. 04, 2011630 
195x195- 1Nov. 17, 2008655 
208x104+ 1Nov. 23, 2011646 
224x112+ 1Oct. 18, 2010642 
238x119+ 1Dec. 25, 2011655 
260x130+ 1Nov. 23, 2011638 
280x140+ 1Nov. 23, 2011678 
288x144+ 1Nov. 17, 2008665 
306x153+ 1Aug. 16, 2012631 
312x156+ 1May 07, 2012676 
336x168+ 1Nov. 23, 2011680 
360x180+ 1Nov. 23, 2011665 
390x195+ 1May 07, 2012663 
420x210+ 1Jun. 15, 2010626 
100 101x101- 1Feb. 04, 2013609 
125x125- 1Dec. 27, 2012631 
202x101+ 1Nov. 17, 2008649 
250x125+ 1May 07, 2012657 

Contributors

(alphabetical order of last name : 50 members are now challenging.)

No.NameFactoring NumbersProgram
1Richard Brent Brent-Montgomery-te Riele tables
xn +/- 1 (n=13..99)
GMP-ecm, snfs (original), ppmpqs (original)
2Robert Backstrom
3Conrad Curry
4Nicolas Daminelli
5Jens Franke
6Sean Irvine
7Joe Leherbauer
8David A. Miller
9Gerhard Niklasch
10Henrik Olsen
11Carsten Pedersen
12Warut Roonguthai
13Jo Yeong Uk
14Andy StewardGeneralised Repunits
(xn-1)/(x-1)
n=41,43,47,49,53,61, ... up to 99
ecm (original), ppmpqs, p-1 (original)
15Tomoya Adachi104GMP-ecm, ppsiqs
16Mark Belangee57, 63, 108, 114, 126MPQS (in Pari)
17Marco Bodrato360, 420GMP-ecm
18Tom Cageall (from small digits)MPQS
19Greg Childers53, 87GMP-ecm, ppsiqs
20Jun Eto92GMP-ecm, ppmpqs
21Sander HoogendoornallGMP-ecm
22Tetsuya Izu41, 132, 150ecm (GMP and original), ppmpqs, snfs
23Yuji Kidaφ(n) > 46 and large digitsecm (original), ppmpqs (original), snfs (original)
24Toshifusa Kinsho142GMP-ecm, snfs
25Thorsten Kleinjung150snfs
26Tetsuya Kobayashi57, 63, 75, 150, 69, 92, 138, 94GMP-ecm, ppmpqs
27Alexander Kruppa86mpqs4 (Jens Franke)
28Shusuke KubotaallGMP-ecm
29Hisanori Mishima114, 126, 100, all Table 2 by ecmGMP-ecm, ppmpqs, snfs
30Kunihiko Miyazaki49GMP-ecm, ppmpqs
31Mitsuo Morimotoφ(n) > 46ecm, ppmpqs, snfs
32Tim Morrowφ(165), φ(n)=100GMP-ecm
33Souichi MurataallGMP-ecm
34Takahiro Nohara69, 59ecm, ppmpqs, snfs
35Katsuyuki Okeya82, 88, 75, 61, 77, 93, 122, 124snfs (Kida), ppmpqs
36Igor Scheinall (from small digits)MPQS (in Pari)
37Frank Schickel83GMP-ecm
38Sinkiti Sibata59, 67, 81GMP-ecm, snfs
39Philippe Strohl180PPSIQS
40Tetsuya Taniguchi65GMP-ecm
41Satoshi Tomabechi82, 100, 49snfs (original), ppmpqs (original)
42Yasunobu Torii63, 108, 126snfs (original)
43Masaki Ukaiall by GMP-ecmGMP-ecm, ppmpqs
44Steven Whitaker100, 104ppmpqs
45Thomas Wuall (from small digits)GMP-ecm
46Aiichi Yamasaki57, 63, 114, 126ecm, ppmpqs, snfs
47-50Maksym Voznyy, Lesya,
Anton & Roman
87GMP-ecm

Up to φ(n) ≤ 58 are completely factored (Table 1, Table 2).

102 ≤ φ(n) ≤ 200 are not maintained here.
Please see Table 5, 6 and 7,

Tomoya Adachi's web site for 102 ≤ φ(n) ≤ 120.

and

Prof. Morimoto's web site for 102 ≤ φ(n) ≤ 200.

Table 5

φ(n)n
102103, 206
104159, 212, 318
106107, 214
108109, 133, 171, 189, 218, 266, 324, 342, 378
110121, 242
112113, 145, 226, 232, 290, 348
116177, 236, 354
120143, 155, 175, 183, 225, 231, 244, 248, 286, 308, 310, 350, 366, 372, 396

Table 6

φ(n)n
126127, 254
128255, 256, 272, 320, 340, 384, 408, 480, 510
130131, 262
132161, 201, 207, 268, 322, 402, 414
136137, 274
138139, 278
140213, 284, 426
144185, 219, 273, 285, 292, 296, 304, 315, 364, 370, 380, 432, 438, 444, 456, 468, 504, 540, 546, 570, 630
148149, 298
150139, 278
156157, 169, 237, 314, 316, 338, 474
160187, 205, 328, 352, 374, 400, 410, 440, 492, 528, 600, 660

Table 7

φ(n)n
162163, 243, 326, 486
164249, 332, 498
166167, 334
168203, 215, 245, 261, 344, 392, 406, 430, 490, 516, 522, 588
172173, 346
176267, 345, 356, 368, 460, 534, 552, 690
178179, 358
180181, 209, 217, 279, 297, 362, 418, 434, 558, 594
184235, 376, 470, 564
190191, 382
192193, 221, 291, 357, 386, 388, 416, 442, 448, 476, 520, 560, 576, 582, 612, 624, 672, 714, 720, 780, 840
196197, 394
198199, 398
200275, 303, 375, 404, 500, 550, 606, 750

link

Tools for factorization programmed by Mr. Satoshi Tomabechi

Mint
(Multi-precision integer library)

Mint for Linux (588 KB)
(Dec. 27, 2001)
Mint for Windows (536 KB)
(Dec. 27, 2001)
"Mint" is a library for computing multi-precision integer.
It is consisted of header files for representing multi digits numbers and
many number theoretic functions.
Especially, it includes the source files of PPSIQS and PPMPQS.
I'm convinced that this will help many programmers
who try to write effective factoring tools.

PPSIQS

Ver. 1.1 for Linux (188 KB)
(Dec. 17, 2001)
Ver. 1.1 for Windows (190 KB)
(Nov. 09, 2001)
PPSIQS is the double large primes procedure variation of the self-intializing quadratic sieve.
In general, PPSIQS is faster than PPMPQS.

Reference
Scott Contini,"Factoring integers with the self-initializing quadratic sieve" ,
Masters thesis, University of Georgia, 1997
http://www.crypto-world.com
Performance report of PPSIQS
"PPSIQS Version 1.1 of Satoshi Tomabechi: Statistics for 60 Runs",
By Tom Hill (January 21, 2003)

PPMPQS

Ver. 2.8 for Linux (184 KB)
(Dec. 17, 2001)
Ver. 2.8 for Windows (185 KB)
(Jul. 14, 2001)
If there remain composite numbers up to around 100 digits,
and you convince there are no factors which can be found by ECM,
then you should try to use this program.
The following documents are attached in the zip files.
Average time of factorization using PPMPQS

factor

Factorization program for general numbers.
It proceeds by rho (x2+1, x2-1, x2+3), p-1 and PPMPQS.
Usage is same as the following programs.

p-1 method

p-1 method

Factorization of "aba" Factorization of Various Numbers Factorization of Partition Numbers

E-mail : kc2h-msm@asahi-net.or.jp
Hisanori Mishima