Factorizations of Cyclotomic Numbers

since 21 January 1999

- 20,000

Update

Whatsnew, history, errata (July 22, 2012)

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

These numbers are under computation. (July 17, 2012)

(To avoid duplication, please check above numbers.)

Old logs (index)

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

How to compute the Cyclotomic Numbers

How to compute the Cyclotomic Numbers(GMP program by Mr. Alexander Kruppa) (Nov. 25, 2001)
How to compute the Cyclotomic Numbers(UBASIC program)
How to compute the Cyclotomic polynomials(UBASIC program)

Table 2

φ(n)	n	Cunningham form	last update	unfactored	who's factoring
56	87	x⁸⁷- 1	Jan 28, 2012	Complete !!!	Tetsuya Kobayashi, Aiichi Yamasaki, Greg Childers, Hisanori Mishima, Sander Hoogendoorn, Tim Morrow, Masaki Ukai (last number)
	116	x⁵⁸+ 1	Mar. 21, 2012	Complete !!!	Tetsuya Kobayashi, Aiichi Yamasaki, Hisanori Mishima, Sander Hoogendoorn, Greg Childers, Masaki Ukai (last number)
	174	x⁸⁷+ 1	Jun. 16, 2012	Complete !!!	Tetsuya Kobayashi, Aiichi Yamasaki, Hisanori Mishima, Sander Hoogendoorn, Masaki Ukai (last number)
58	59	x⁵⁹- 1	Nov. 28, 2011	Complete !!!	Takahiro Nohara, Sinkiti Sibata, Andy Steward, Robert Backstrom, Hisanori Mishima, Yeong Uk Jo, Kenji Ibusuki, Masaki Ukai (last number)
58	118	x⁵⁹+ 1	Sep. 19, 2008	Complete !!!	Masaki Ukai, Aiichi Yamasaki, Sinkiti Sibata, Hisanori Mishima, Greg Childers (last number)
60	61	x⁶¹- 1	Jul. 17, 2012	211	Katsuyuki Okeya, Andy Steward
	77	x⁷⁷- 1	Jul. 17, 2012	277	Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara, Tomoya Adachi
	93	x⁹³- 1	Jul. 17, 2012	290	Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara, Tomoya Adachi
	99	x⁹⁹- 1	Jul. 22, 2012	244	Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara, Tomoya Adachi
	122	x⁶¹+ 1	Jul. 22, 2012	194	Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
	124	x⁶²+ 1	Jun. 24, 2012	Complete !!!	Aiichi Yamasaki, Katsuyuki Okeya, Tomoya Adachi (last number)
	154	x⁷⁷+ 1	Dec. 13, 2011	Complete !!!	Aiichi Yamasaki, Hisanori Mishima, Takahiro Nohara, Tomoya Adachi (last number)
	186	x⁹³+ 1	Jul. 25, 2009	Complete !!!	Aiichi Yamasaki, Hisanori Mishima, Joe Leherbauer, Tomoya Adachi (last number)
	198	x⁹⁹+ 1	Sep. 15, 2008	Complete !!!	Aiichi Yamasaki, Hisanori Mishima, Joe Leherbauer, Tomoya Adachi (last number)
64	85	x⁸⁵- 1	Jul. 17, 2012	342	Tetsuya Kobayashi, Hisanori Mishima
	128	x⁶⁴+ 1	Oct. 09, 2010	Complete !!!	David A. Miller, Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima, Tomoya Adachi (last number)
	136	x⁶⁸+ 1	Jul. 17, 2012	333	Tetsuya Kobayashi, Hisanori Mishima
	160	x⁸⁰+ 1	Jul. 22, 2012	330	Tetsuya Kobayashi, Takahiro Nohara
	170	x⁸⁵+ 1	Jul. 17, 2012	362	Tetsuya Kobayashi, Satoshi Tomabechi, Hisanori Mishima
	192	x⁹⁶+ 1	Jul. 04, 2011	369	Tetsuya Kobayashi, David A. Miller
	204	x¹⁰²+ 1	Jul. 17, 2012	364	Tetsuya Kobayashi, Satoshi Tomabechi, Joe Leherbauer, Hisanori Mishima, Tomoya Adachi
	240	x¹²⁰+ 1	Jul. 17, 2012	345	Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima, Tomoya Adachi
66	67	x⁶⁷- 1	May 07, 2012	350	Sinkiti Sibata, Sean Irvine, Hisanori Mishima, Tomoya Adachi
66	134	x⁶⁷+ 1	May 07, 2012	390	Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima, Tomoya Adachi
70	71	x⁷¹- 1	May 07, 2012	400	Tetsuya Kobayashi, Masaki Ukai, Andy Steward, Sean Irvine, Tomoya Adachi
70	142	x⁷¹+ 1	May 07, 2012	310	Tetsuya Kobayashi, Tomoya Adachi

Table 3

φ(n)	n	Cunningham form	last update	unfactored
72	73	x⁷³- 1	Jul. 22, 2012	376
	91	x⁹¹- 1	Nov. 23, 2011	457
	95	x⁹⁵- 1	May 07, 2012	448
	111	x¹¹¹- 1	Jun. 20, 2009	399
	117	x¹¹⁷- 1	Feb. 17, 2009	404
	135	x¹³⁵- 1	Nov. 23, 2011	443
	146	x⁷³+ 1	Jul. 22, 2012	450
	148	x⁷⁴+ 1	Nov. 23, 2011	477
	152	x⁷⁶+ 1	Nov. 23, 2011	490
	182	x⁹¹+ 1	May 07, 2012	466
	190	x⁹⁵+ 1	Nov. 23, 2011	496
	216	x¹⁰⁸+ 1	Nov. 17, 2008	524
	222	x¹¹¹+ 1	Nov. 04, 2008	514
	228	x¹¹⁴+ 1	Nov. 23, 2011	441
	234	x¹¹⁷+ 1	Dec. 02, 2011	499
	252	x¹²⁶+ 1	Jul. 04, 2011	517
	270	x¹³⁵+ 1	May 07, 2012	521
78	79	x⁷⁹- 1	Nov. 23, 2011	521
78	158	x⁷⁹+ 1	Nov. 23, 2011	555
80	123	x¹²³- 1	Dec. 30, 2008	579
	164	x⁸²+ 1	Nov. 23, 2011	543
	165	x¹⁶⁵- 1	Nov. 23, 2011	502
	176	x⁸⁸+ 1	Dec. 02, 2011	518
	200	x¹⁰⁰+ 1	Jul. 04, 2011	590
	220	x¹¹⁰+ 1	Aug. 10, 2009	534
	246	x¹²³+ 1	Nov. 23, 2011	548
	264	x¹³²+ 1	May 07, 2012	583
	300	x¹⁵⁰+ 1	Dec. 31, 2009	562
	330	x¹⁶⁵+ 1	Nov. 23, 2011	576

Table 4

φ(n)	n	Cunningham form	last update	unfactored
82	83	x⁸³- 1	Jul. 22, 2012	481
82	166	x⁸³+ 1	Jul. 17, 2012	540
84	129	x¹²⁹- 1	Oct. 18, 2010	646
	147	x¹⁴⁷- 1	Nov. 23, 2011	626
	172	x⁸⁶+ 1	May 07, 2012	593
	196	x⁹⁸+ 1	Nov. 23, 2011	616
	258	x¹²⁹+ 1	Nov. 23, 2011	639
	294	x¹⁴⁷+ 1	Nov. 23, 2011	653
88	89	x⁸⁹- 1	May 07, 2012	614
	115	x¹¹⁵- 1	Jul. 04, 2011	677
	178	x⁸⁹+ 1	Nov. 23, 2011	648
	184	x⁹²+ 1	Nov. 23, 2011	621
	230	x¹¹⁵+ 1	Nov. 23, 2011	677
	276	x¹³⁸+ 1	Nov. 23, 2011	637
92	141	x¹⁴¹- 1	Nov. 23, 2011	615
	188	x⁹⁴+ 1	Nov. 23, 2011	617
	282	x¹⁴¹+ 1	Nov. 23, 2011	638
96	97	x⁹⁷- 1	Jul. 04, 2011	635
	119	x¹¹⁹- 1	Dec. 25, 2011	633
	153	x¹⁵³- 1	Nov. 23, 2011	638
	194	x⁹⁷+ 1	Jul. 04, 2011	630
	195	x¹⁹⁵- 1	Nov. 17, 2008	655
	208	x¹⁰⁴+ 1	Nov. 23, 2011	646
	224	x¹¹²+ 1	Oct. 18, 2010	642
	238	x¹¹⁹+ 1	Dec. 25, 2011	655
	260	x¹³⁰+ 1	Nov. 23, 2011	638
	280	x¹⁴⁰+ 1	Nov. 23, 2011	678
	288	x¹⁴⁴+ 1	Nov. 17, 2008	665
	306	x¹⁵³+ 1	May 07, 2012	632
	312	x¹⁵⁶+ 1	May 07, 2012	676
	336	x¹⁶⁸+ 1	Nov. 23, 2011	680
	360	x¹⁸⁰+ 1	Nov. 23, 2011	665
	390	x¹⁹⁵+ 1	May 07, 2012	663
	420	x²¹⁰+ 1	Jun. 15, 2010	626
100	101	x¹⁰¹- 1	Nov. 23, 2011	610
	125	x¹²⁵- 1	Feb. 08, 2009	632
	202	x¹⁰¹+ 1	Nov. 17, 2008	649
	250	x¹²⁵+ 1	May 07, 2012	657

Contributors

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

No.	Name	Factoring Numbers	Program
1	Richard Brent	Brent-Montgomery-te Riele tables xⁿ +/- 1 (n=13..99)	GMP-ecm, snfs (original), ppmpqs (original)
2	Robert Backstrom
3	Conrad Curry
4	Nicolas Daminelli
5	Jens Franke
6	Sean Irvine
7	Joe Leherbauer
8	David A. Miller
9	Gerhard Niklasch
10	Henrik Olsen
11	Carsten Pedersen
12	Warut Roonguthai
13	Jo Yeong Uk
14	Andy Steward	Generalised Repunits (xⁿ-1)/(x-1) n=41,43,47,49,53,61, ... up to 99	ecm (original), ppmpqs, p-1 (original)
15	Tomoya Adachi	104	GMP-ecm, ppsiqs
16	Mark Belangee	57, 63, 108, 114, 126	MPQS (in Pari)
17	Marco Bodrato	360, 420	GMP-ecm
18	Tom Cage	all (from small digits)	MPQS
19	Greg Childers	53, 87	GMP-ecm, ppsiqs
20	Jun Eto	92	GMP-ecm, ppmpqs
21	Sander Hoogendoorn	all	GMP-ecm
22	Tetsuya Izu	41, 132, 150	ecm (GMP and original), ppmpqs, snfs
23	Yuji Kida	φ(n) > 46 and large digits	ecm (original), ppmpqs (original), snfs (original)
24	Toshifusa Kinsho	142	GMP-ecm, snfs
25	Thorsten Kleinjung	150	snfs
26	Tetsuya Kobayashi	57, 63, 75, 150, 69, 92, 138, 94	GMP-ecm, ppmpqs
27	Alexander Kruppa	86	mpqs4 (Jens Franke)
28	Shusuke Kubota	all	GMP-ecm
29	Hisanori Mishima	114, 126, 100, all Table 2 by ecm	GMP-ecm, ppmpqs, snfs
30	Kunihiko Miyazaki	49	GMP-ecm, ppmpqs
31	Mitsuo Morimoto	φ(n) > 46	ecm, ppmpqs, snfs
32	Tim Morrow	φ(165), φ(n)=100	GMP-ecm
33	Souichi Murata	all	GMP-ecm
34	Takahiro Nohara	69, 59	ecm, ppmpqs, snfs
35	Katsuyuki Okeya	82, 88, 75, 61, 77, 93, 122, 124	snfs (Kida), ppmpqs
36	Igor Schein	all (from small digits)	MPQS (in Pari)
37	Frank Schickel	83	GMP-ecm
38	Sinkiti Sibata	59, 67, 81	GMP-ecm, snfs
39	Philippe Strohl	180	PPSIQS
40	Tetsuya Taniguchi	65	GMP-ecm
41	Satoshi Tomabechi	82, 100, 49	snfs (original), ppmpqs (original)
42	Yasunobu Torii	63, 108, 126	snfs (original)
43	Masaki Ukai	all by GMP-ecm	GMP-ecm, ppmpqs
44	Steven Whitaker	100, 104	ppmpqs
45	Thomas Wu	all (from small digits)	GMP-ecm
46	Aiichi Yamasaki	57, 63, 114, 126	ecm, ppmpqs, snfs
47-50	Maksym Voznyy, Lesya, Anton & Roman	87	GMP-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
102	103, 206
104	159, 212, 318
106	107, 214
108	109, 133, 171, 189, 218, 266, 324, 342, 378
110	121, 242
112	113, 145, 226, 232, 290, 348
116	177, 236, 354
120	143, 155, 175, 183, 225, 231, 244, 248, 286, 308, 310, 350, 366, 372, 396

Table 6

φ(n)	n
126	127, 254
128	255, 256, 272, 320, 340, 384, 408, 480, 510
130	131, 262
132	161, 201, 207, 268, 322, 402, 414
136	137, 274
138	139, 278
140	213, 284, 426
144	185, 219, 273, 285, 292, 296, 304, 315, 364, 370, 380, 432, 438, 444, 456, 468, 504, 540, 546, 570, 630
148	149, 298
150	139, 278
156	157, 169, 237, 314, 316, 338, 474
160	187, 205, 328, 352, 374, 400, 410, 440, 492, 528, 600, 660

Table 7

φ(n)	n
162	163, 243, 326, 486
164	249, 332, 498
166	167, 334
168	203, 215, 245, 261, 344, 392, 406, 430, 490, 516, 522, 588
172	173, 346
176	267, 345, 356, 368, 460, 534, 552, 690
178	179, 358
180	181, 209, 217, 279, 297, 362, 418, 434, 558, 594
184	235, 376, 470, 564
190	191, 382
192	193, 221, 291, 357, 386, 388, 416, 442, 448, 476, 520, 560, 576, 582, 612, 624, 672, 714, 720, 780, 840
196	197, 394
198	199, 398
200	275, 303, 375, 404, 500, 550, 606, 750

link

Factor Tables by Prof. Richard Brent

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 (x²+1, x²-1, x²+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