Factorizations of Cyclotomic Numbers

since 21 January 1999 Counter - 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

Table 2

φ(n)nCunningham formlast updateunfactoredwho's factoring
52 53x53- 1Jul. 01, 2006Complete !!!Masaki Ukai, Greg Childers, Andy Steward, Robert Backstrom, Hisanori Mishima,
Alexander Kruppa (last number)
106x53+ 1Feb. 27, 2007Complete !!!Takahiro Nohara, Masaki Ukai, Hisanori Mishima,
Greg Childers (last number)
54 81x81- 1Nov. 16, 2006Complete !!!Masaki Ukai, Sinkiti Sibata, Hisanori Mishima,
Greg Childers (last number)
162x81+ 1Feb. 17, 2007Complete !!!Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Sinkiti Sibata, Hisanori Mishima, Tomoya Adachi (last number)
56 87x87- 1Sep. 21, 200997Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Greg Childers, Hisanori Mishima, Sander Hoogendoorn, Tim Morrow
116x58+ 1Sep. 21, 2009225Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Hisanori Mishima, Sander Hoogendoorn, Greg Childers
174x87+ 1Nov. 17, 2008237Tetsuya Kobayashi, Masaki Ukai, Aiichi Yamasaki, Hisanori Mishima, Sander Hoogendoorn
58 59x59- 1Sep. 21, 2009265Masaki Ukai, Takahiro Nohara, Sinkiti Sibata, Andy Steward, Robert Backstrom, Hisanori Mishima, Yeong Uk Jo
118x59+ 1Sep. 19, 2008Complete !!!Masaki Ukai, Aiichi Yamasaki, Sinkiti Sibata, Hisanori Mishima,
Greg Childers (last number)
60 61x61- 1Sep. 21, 2009258Katsuyuki Okeya, Andy Steward
77x77- 1Sep. 21, 2009322Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
93x93- 1May 12, 2008336Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
99x99- 1Oct. 22, 2007325Aiichi Yamasaki, Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
122x61+ 1Jul. 15, 2008328Katsuyuki Okeya, Joe Leherbauer, Takahiro Nohara
124x62+ 1Sep. 21, 2009320Aiichi Yamasaki, Katsuyuki Okeya
154x77+ 1Sep. 21, 2009323Aiichi Yamasaki, Hisanori Mishima, Takahiro Nohara
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- 1Sep. 21, 2009355Tetsuya Kobayashi, Hisanori Mishima
128x64+ 1Sep. 21, 2009336David A. Miller, Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima
136x68+ 1Sep. 21, 2009354Tetsuya Kobayashi, Hisanori Mishima
160x80+ 1Sep. 21, 2009448Tetsuya Kobayashi, Takahiro Nohara
170x85+ 1Sep. 21, 2009417Tetsuya Kobayashi, Satoshi Tomabechi, Hisanori Mishima
192x96+ 1Nov. 17, 2008379Tetsuya Kobayashi, David A. Miller
204x102+ 1May 12, 2008456Tetsuya Kobayashi, Satoshi Tomabechi, Joe Leherbauer, Hisanori Mishima
240x120+ 1May 08, 2007463Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima
66 67x67- 1Sep. 21, 2009444Sinkiti Sibata, Sean Irvine, Hisanori Mishima
134x67+ 1Sep. 21, 2009456Tetsuya Kobayashi, Joe Leherbauer, Hisanori Mishima
70 71x71- 1Sep. 21, 2009447Tetsuya Kobayashi, Masaki Ukai, Andy Steward, Sean Irvine
142x71+ 1Sep. 21, 2009400Tetsuya Kobayashi, Tomoya Adachi

Table 3

φ(n)nCunningham formlast updateunfactoredwho's factoring
72 73x73- 1Nov. 17, 2009427 
91x91- 1Sep. 21, 2009472 
95x95- 1Feb. 08, 2009453 
111x111- 1Jun. 20, 2009399 
117x117- 1Feb. 17, 2009404 
135x135- 1Feb. 19, 2009445 
146x73+ 1Sep. 21, 2009511 
148x74+ 1Sep. 21, 2009486 
152x76+ 1Sep. 21, 2009503 
182x91+ 1Sep. 21, 2009472 
190x95+ 1Feb. 08, 2009500 
216x108+ 1Nov. 17, 2008524 
222x111+ 1Nov. 04, 2008514 
228x114+ 1Feb. 08, 2009443 
234x117+ 1Jul. 22, 2009502 
252x126+ 1Jan. 30, 2009519 
270x135+ 1Feb. 17, 2009522 
78 79x79- 1Feb. 08, 2009550 
158x79+ 1Feb. 08, 2009570 
80 123x123- 1Dec. 30, 2008579 
164x82+ 1Sep. 21, 2009552 
165x165- 1Aug. 12, 2008503 
176x88+ 1Sep. 21, 2009527 
200x100+ 1Sep. 21, 2009595 
220x110+ 1Aug. 10, 2009534 
246x123+ 1Dec. 30, 2008550 
264x132+ 1Aug. 10, 2009585 
300x150+ 1Aug. 10, 2009563 
330x165+ 1Oct. 12, 2008576 

Table 4

φ(n)nCunningham formlast updateunfactoredwho's factoring
82 83x83- 1Sep. 21, 2009577 
166x83+ 1Sep. 21, 2009611 
84 129x129- 1Sep. 21, 2009647 
147x147- 1May 12, 2008628 
172x86+ 1Sep. 21, 2009605 
196x98+ 1Sep. 21, 2009623 
258x129+ 1Jan. 15, 2008643 
294x147+ 1Nov. 17, 2008656 
88 89x89- 1Sep. 21, 2009650 
115x115- 1May 12, 2008677 
178x89+ 1Sep. 21, 2009658 
184x92+ 1Feb. 08, 2009632 
230x115+ 1May 12, 2008680 
276x138+ 1Oct. 13, 2008638 
92 141x141- 1Dec. 29, 2008615 
188x94+ 1Dec. 29, 2008621 
282x141+ 1Nov. 17, 2008640 
96 97x97- 1Sep. 21, 2009658 
119x119- 1Sep. 21, 2009639 
153x153- 1Nov. 17, 2008639 
194x97+ 1Sep. 21, 2009633 
195x195- 1Nov. 17, 2008655 
208x104+ 1Nov. 17, 2008648 
224x112+ 1Dec. 29, 2008643 
238x119+ 1Sep. 29, 2008659 
260x130+ 1Feb. 08, 2009640 
280x140+ 1Nov. 17, 2008682 
288x144+ 1Nov. 17, 2008666 
306x153+ 1Oct. 12, 2008636 
312x156+ 1Aug. 03, 2008685 
336x168+ 1Sep. 21, 2009680 
360x180+ 1Nov. 17, 2008665 
390x195+ 1Nov. 17, 2008666 
420x210+ 1Sep. 21, 2009627 
100 101x101- 1Dec. 29, 2008632 
125x125- 1Feb. 08, 2009632 
202x101+ 1Nov. 17, 2008649 
250x125+ 1Sep. 21, 2009659 

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

Table 1

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

φ(n)npublication
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
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