Factorizations of Cyclotomic Numbers

since 21 January 1999

- 20,000

Update

Whatsnew, history, errata (November 17, 2009)

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

These numbers are under computation. (September 21, 2009)

(To avoid duplication, please check above numbers.)

Old logs (index)

2008 ( Sep - Dec, Aug - May, Apr - Jan, 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
52	53	x⁵³- 1	Jul. 01, 2006	Complete !!!	Masaki Ukai, Greg Childers, Andy Steward, Robert Backstrom, Hisanori Mishima, Alexander Kruppa (last number)
52	106	x⁵³+ 1	Feb. 27, 2007	Complete !!!	Takahiro Nohara, Masaki Ukai, Hisanori Mishima, Greg Childers (last number)
54	81	x⁸¹- 1	Nov. 16, 2006	Complete !!!	Masaki Ukai, Sinkiti Sibata, Hisanori Mishima, Greg Childers (last number)
54	162	x⁸¹+ 1	Feb. 17, 2007	Complete !!!	Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Sinkiti Sibata, Hisanori Mishima, Tomoya Adachi (last number)
56	87	x⁸⁷- 1	Sep. 21, 2009	97	Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Greg Childers, Hisanori Mishima, Sander Hoogendoorn, Tim Morrow
	116	x⁵⁸+ 1	Sep. 21, 2009	225	Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Hisanori Mishima, Sander Hoogendoorn, Greg Childers
	174	x⁸⁷+ 1	Nov. 17, 2008	237	Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Hisanori Mishima, Sander Hoogendoorn
58	59	x⁵⁹- 1	Sep. 21, 2009	265	Masaki Ukai, Takahiro Nohara, Sinkiti Sibata, Andy Steward, Robert Backstrom, Hisanori Mishima, Yeong Uk Jo
58	118	x⁵⁹+ 1	Sep. 19, 2008	Complete !!!	Masaki Ukai, Aiichi Yamasaki, Sinkiti Sibata, Hisanori Mishima, Greg Childers (last number)
60	61	x⁶¹- 1	Sep. 21, 2009	258	Katsuyuki Okeya, Andy Steward
	77	x⁷⁷- 1	Sep. 21, 2009	322	Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
	93	x⁹³- 1	May 12, 2008	336	Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
	99	x⁹⁹- 1	Oct. 22, 2007	325	Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
	122	x⁶¹+ 1	Jul. 15, 2008	328	Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
	124	x⁶²+ 1	Sep. 21, 2009	320	Aiichi Yamasaki, Katsuyuki Okeya
	154	x⁷⁷+ 1	Sep. 21, 2009	323	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	Sep. 21, 2009	355	Tetsuya Kobayashi, Hisanori Mishima
	128	x⁶⁴+ 1	Sep. 21, 2009	336	David A. Miller, Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima
	136	x⁶⁸+ 1	Sep. 21, 2009	354	Tetsuya Kobayashi, Hisanori Mishima
	160	x⁸⁰+ 1	Sep. 21, 2009	448	Tetsuya Kobayashi, Takahiro Nohara
	170	x⁸⁵+ 1	Sep. 21, 2009	417	Tetsuya Kobayashi, Satoshi Tomabechi, Hisanori Mishima
	192	x⁹⁶+ 1	Nov. 17, 2008	379	Tetsuya Kobayashi, David A. Miller
	204	x¹⁰²+ 1	May 12, 2008	456	Tetsuya Kobayashi, Satoshi Tomabechi, Joe Leherbauer, Hisanori Mishima
	240	x¹²⁰+ 1	May 08, 2007	463	Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima
66	67	x⁶⁷- 1	Sep. 21, 2009	444	Sinkiti Sibata, Sean Irvine, Hisanori Mishima
66	134	x⁶⁷+ 1	Sep. 21, 2009	456	Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima
70	71	x⁷¹- 1	Sep. 21, 2009	447	Tetsuya Kobayashi, Masaki Ukai, Andy Steward, Sean Irvine
70	142	x⁷¹+ 1	Sep. 21, 2009	400	Tetsuya Kobayashi, Tomoya Adachi

Table 3

φ(n)	n	Cunningham form	last update	unfactored
72	73	x⁷³- 1	Nov. 17, 2009	427
	91	x⁹¹- 1	Sep. 21, 2009	472
	95	x⁹⁵- 1	Feb. 08, 2009	453
	111	x¹¹¹- 1	Jun. 20, 2009	399
	117	x¹¹⁷- 1	Feb. 17, 2009	404
	135	x¹³⁵- 1	Feb. 19, 2009	445
	146	x⁷³+ 1	Sep. 21, 2009	511
	148	x⁷⁴+ 1	Sep. 21, 2009	486
	152	x⁷⁶+ 1	Sep. 21, 2009	503
	182	x⁹¹+ 1	Sep. 21, 2009	472
	190	x⁹⁵+ 1	Feb. 08, 2009	500
	216	x¹⁰⁸+ 1	Nov. 17, 2008	524
	222	x¹¹¹+ 1	Nov. 04, 2008	514
	228	x¹¹⁴+ 1	Feb. 08, 2009	443
	234	x¹¹⁷+ 1	Jul. 22, 2009	502
	252	x¹²⁶+ 1	Jan. 30, 2009	519
	270	x¹³⁵+ 1	Feb. 17, 2009	522
78	79	x⁷⁹- 1	Feb. 08, 2009	550
78	158	x⁷⁹+ 1	Feb. 08, 2009	570
80	123	x¹²³- 1	Dec. 30, 2008	579
	164	x⁸²+ 1	Sep. 21, 2009	552
	165	x¹⁶⁵- 1	Aug. 12, 2008	503
	176	x⁸⁸+ 1	Sep. 21, 2009	527
	200	x¹⁰⁰+ 1	Sep. 21, 2009	595
	220	x¹¹⁰+ 1	Aug. 10, 2009	534
	246	x¹²³+ 1	Dec. 30, 2008	550
	264	x¹³²+ 1	Aug. 10, 2009	585
	300	x¹⁵⁰+ 1	Aug. 10, 2009	563
	330	x¹⁶⁵+ 1	Oct. 12, 2008	576

Table 4

φ(n)	n	Cunningham form	last update	unfactored
82	83	x⁸³- 1	Sep. 21, 2009	577
82	166	x⁸³+ 1	Sep. 21, 2009	611
84	129	x¹²⁹- 1	Sep. 21, 2009	647
	147	x¹⁴⁷- 1	May 12, 2008	628
	172	x⁸⁶+ 1	Sep. 21, 2009	605
	196	x⁹⁸+ 1	Sep. 21, 2009	623
	258	x¹²⁹+ 1	Jan. 15, 2008	643
	294	x¹⁴⁷+ 1	Nov. 17, 2008	656
88	89	x⁸⁹- 1	Sep. 21, 2009	650
	115	x¹¹⁵- 1	May 12, 2008	677
	178	x⁸⁹+ 1	Sep. 21, 2009	658
	184	x⁹²+ 1	Feb. 08, 2009	632
	230	x¹¹⁵+ 1	May 12, 2008	680
	276	x¹³⁸+ 1	Oct. 13, 2008	638
92	141	x¹⁴¹- 1	Dec. 29, 2008	615
	188	x⁹⁴+ 1	Dec. 29, 2008	621
	282	x¹⁴¹+ 1	Nov. 17, 2008	640
96	97	x⁹⁷- 1	Sep. 21, 2009	658
	119	x¹¹⁹- 1	Sep. 21, 2009	639
	153	x¹⁵³- 1	Nov. 17, 2008	639
	194	x⁹⁷+ 1	Sep. 21, 2009	633
	195	x¹⁹⁵- 1	Nov. 17, 2008	655
	208	x¹⁰⁴+ 1	Nov. 17, 2008	648
	224	x¹¹²+ 1	Dec. 29, 2008	643
	238	x¹¹⁹+ 1	Sep. 29, 2008	659
	260	x¹³⁰+ 1	Feb. 08, 2009	640
	280	x¹⁴⁰+ 1	Nov. 17, 2008	682
	288	x¹⁴⁴+ 1	Nov. 17, 2008	666
	306	x¹⁵³+ 1	Oct. 12, 2008	636
	312	x¹⁵⁶+ 1	Aug. 03, 2008	685
	336	x¹⁶⁸+ 1	Sep. 21, 2009	680
	360	x¹⁸⁰+ 1	Nov. 17, 2008	665
	390	x¹⁹⁵+ 1	Nov. 17, 2008	666
	420	x²¹⁰+ 1	Sep. 21, 2009	627
100	101	x¹⁰¹- 1	Dec. 29, 2008	632
	125	x¹²⁵- 1	Feb. 08, 2009	632
	202	x¹⁰¹+ 1	Nov. 17, 2008	649
	250	x¹²⁵+ 1	Sep. 21, 2009	659

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