Factorizations of Cyclotomic Numbers

since 21 January 1999

- 20,000

Update

Whatsnew, history, errata (November 23, 2011)

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

These numbers are under computation. (July 04, 2011)

(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	Jul. 04, 2011	78	Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Greg Childers, Hisanori Mishima, Sander Hoogendoorn, Tim Morrow
	116	x⁵⁸+ 1	Nov. 23, 2011	196	Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Hisanori Mishima, Sander Hoogendoorn, Greg Childers
	174	x⁸⁷+ 1	Nov. 23, 2011	214	Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Hisanori Mishima, Sander Hoogendoorn
58	59	x⁵⁹- 1	Nov. 23, 2011	96	Masaki Ukai, Takahiro Nohara, Sinkiti Sibata, Andy Steward, Robert Backstrom, Hisanori Mishima, Yeong Uk Jo, Kenji Ibusuki
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. 04, 2011	249	Katsuyuki Okeya, Andy Steward
	77	x⁷⁷- 1	Nov. 23, 2011	310	Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
	93	x⁹³- 1	Nov. 23, 2011	328	Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
	99	x⁹⁹- 1	Jul. 04, 2011	319	Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
	122	x⁶¹+ 1	Nov. 23, 2011	316	Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
	124	x⁶²+ 1	Jul. 04, 2011	306	Aiichi Yamasaki, Katsuyuki Okeya
	154	x⁷⁷+ 1	Nov. 23, 2011	35	Aiichi Yamasaki, Hisanori Mishima, Takahiro Nohara
	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. 04, 2011	351	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	Nov. 23, 2011	339	Tetsuya Kobayashi, Hisanori Mishima
	160	x⁸⁰+ 1	Nov. 23, 2011	362	Tetsuya Kobayashi, Takahiro Nohara
	170	x⁸⁵+ 1	Nov. 23, 2011	369	Tetsuya Kobayashi, Satoshi Tomabechi, Hisanori Mishima
	192	x⁹⁶+ 1	Jul. 04, 2011	369	Tetsuya Kobayashi, David A. Miller
	204	x¹⁰²+ 1	Aug. 09, 2010	455	Tetsuya Kobayashi, Satoshi Tomabechi, Joe Leherbauer, Hisanori Mishima
	240	x¹²⁰+ 1	Nov. 23, 2011	456	Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima
66	67	x⁶⁷- 1	Nov. 23, 2011	402	Sinkiti Sibata, Sean Irvine, Hisanori Mishima
66	134	x⁶⁷+ 1	Jul. 04, 2011	435	Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima
70	71	x⁷¹- 1	Nov. 23, 2011	423	Tetsuya Kobayashi, Masaki Ukai, Andy Steward, Sean Irvine
70	142	x⁷¹+ 1	Nov. 23, 2011	313	Tetsuya Kobayashi, Tomoya Adachi

Table 3

φ(n)	n	Cunningham form	last update	unfactored
72	73	x⁷³- 1	Nov. 23, 2011	399
	91	x⁹¹- 1	Nov. 23, 2011	457
	95	x⁹⁵- 1	Nov. 23, 2011	449
	111	x¹¹¹- 1	Jun. 20, 2009	399
	117	x¹¹⁷- 1	Feb. 17, 2009	404
	135	x¹³⁵- 1	Nov. 23, 2011	443
	146	x⁷³+ 1	Nov. 23, 2011	496
	148	x⁷⁴+ 1	Nov. 23, 2011	477
	152	x⁷⁶+ 1	Nov. 23, 2011	490
	182	x⁹¹+ 1	Nov. 23, 2011	467
	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	Nov. 14, 2010	500
	252	x¹²⁶+ 1	Jul. 04, 2011	517
	270	x¹³⁵+ 1	Nov. 23, 2011	522
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	Nov. 23, 2011	519
	200	x¹⁰⁰+ 1	Jul. 04, 2011	590
	220	x¹¹⁰+ 1	Aug. 10, 2009	534
	246	x¹²³+ 1	Nov. 23, 2011	548
	264	x¹³²+ 1	Jun. 15, 2010	584
	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	Nov. 23, 2011	551
82	166	x⁸³+ 1	Nov. 23, 2011	599
84	129	x¹²⁹- 1	Oct. 18, 2010	646
	147	x¹⁴⁷- 1	Nov. 23, 2011	626
	172	x⁸⁶+ 1	Nov. 23, 2011	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	Nov. 23, 2011	615
	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	614
	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	Sep. 21, 2009	639
	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	Nov. 23, 2011	658
	260	x¹³⁰+ 1	Nov. 23, 2011	638
	280	x¹⁴⁰+ 1	Nov. 23, 2011	678
	288	x¹⁴⁴+ 1	Nov. 17, 2008	665
	306	x¹⁵³+ 1	Oct. 12, 2008	636
	312	x¹⁵⁶+ 1	Aug. 03, 2008	685
	336	x¹⁶⁸+ 1	Nov. 23, 2011	680
	360	x¹⁸⁰+ 1	Nov. 23, 2011	665
	390	x¹⁹⁵+ 1	Nov. 23, 2011	666
	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	Dec. 31, 2009	658

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

Table 1

Up to φ(n) ≤ 46 are completely factored (Table 1).

φ(n)	n	publication
1	1, 2	not published
2	3, 4, 6
4	5, 8, 10, 12
6	7, 9, 14, 18
8	15, 16, 20, 24, 30
10	11, 22
12	13, 21, 26, 28, 36, 42
16	17, 32, 34, 40, 48, 60	Factorization of Cyclotomic Numbers (Sophia Kokyuroku in Mathematics 26, November 1987)
18	19, 27, 38, 54
20	25, 33, 44, 50, 66	Factorization of Cyclotomic Numbers 2 (Sophia Kokyuroku in Mathematics 29, February 1989)
22	23, 46
24	35, 39, 45, 52, 56, 70, 72, 78, 84, 90	Factorization of Cyclotomic Numbers 3 (Sophia Kokyuroku in Mathematics 35, July 1992)
28	29, 58
30	31, 62	Factorization of Cyclotomic Numbers 4 (Sophia Kokyuroku in Mathematics 42, July 1999)
32	51, 64, 68, 80, 96, 102, 120
36	37, 57, 63, 74, 76, 108, 114, 126	(not published yet)
40	41, 55, 75, 82, 88, 100, 110, 132, 150	(not published yet)
42	43, 49, 86, 98	(not published yet)
44	69, 92, 138	(not published yet.)
46	47, 94	(not published yet.)
48	65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210	(not published yet.)

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