Cyclotomic Number 186 222 has a factor ...
 

Jason,

SIQS found P38 and P50
[code]
Factorizations of Cyclotomic Numbers
[url]http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm[/url]

(186 222 (198066751 8289526543 93798454291 7411673576815285902799837) (C 87))


g4-867:~/Desktop/QS08 k5gj$ ./cyclotomic 186 222
606918416359848914892488149252083484249659540496775857983786413070674354213271198384897683999541852516980609099940210868246465068783784687639
g4-867:~/Desktop/QS08 k5gj$


n = 606918416359848914892488149252083484249659540496775857983786413070674354213271198384897683999541852516980609099940210868246465068783784687639
w = n ÷ 198066751;
x = w ÷ 8289526543;
y = x ÷ 93798454291;
z = y ÷ 7411673576815285902799837

Out[2]:= 531712715349831090290118766862743492257188595090356599187201421502078139168063424507169
Out[3]:= False
Out[4]:= 87

/******************************************************************************/

Script started on Mon Dec 6 13:18:52 2004
gigabyte#
gigabyte# time ./qs086 < c87.txt

Msieve v. 0.86
random seeds: 00000520 41b4b0a9
input to factor: factoring 531712715349831090290118766862743492257188595090356599187201421502078139168063424507169
Mon Dec 6 13:19:05 2004
using multiplier of 1
Mon Dec 6 13:19:07 2004
using sieve block of 65536
using a sieve bound of 1499041 (56956 primes)
using large prime bound of 119923280
using double large prime bound of 348358300445040

sieving in progress (press Ctrl-C to pause)
found 25 relations (25 full + 0 partial), need 57084
found 50 relations (50 full + 0 partial), need 57084
|
|found 57116 relations (15833 full + 41283 partial), need 57084
found 57116 relations (15833 full + 41283 partial), need 57084
begin with 600477 relations
reduce to 124112 relations in 10 passes
attempting to read 15833 full and 124112 partial relations
recovered 15833 full and 124112 partial relations
recovered 49472 polynomials
attempting to build 42624 cycles
found 42632 cycles in 3 passes
distribution of cycle lengths:
length 2 : 11826
length 3 : 10519
length 4 : 7593
length 5 : 5280
length 6 : 3312
length 7 : 1923
length 8 : 1081
length 9+: 1098
largest cycle: 16 relations
Mon Dec 6 14:40:35 2004
56956 x 57020 system, weight 2989676 (avg 52.43/col)
reduce to 55254 x 55318 in 3 passes
lanczos halted after 875 iterations
recovered 59 nontrivial dependencies
Mon Dec 6 14:41:09 2004
probable prime factor: 34543507606944891438763472234686599133
probable prime factor: 15392551370287929071160080311864176726373928476693
Mon Dec 6 14:41:28 2004
4915.755u 16.593s 1:22:22.73 99.7% 71+56517k 0+340io 0pf+0w
gigabyte#
gigabyte#
gigabyte# exit
Script done on Mon Dec 6 14:46:25 2004

/******************************************************************************/

n = 34543507606944891438763472234686599133 * 15392551370287929071160080311864176726373928476693
Out[2]:=531712715349831090290118766862743492257188595090356599187201421502078139168063424507169
Out[3]:= False
Out[4]:= 87

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/[/code]

[QUOTE]What if we put a short list of numbers and coordinate the effort of both trying msieve and help factorization? [/QUOTE]
What projects are you interested in and numbers of what size?

A lot of factorization projects have most (if not all) numbers below 100 digits factored.

I know cyclotomic factorizations and factorizations of partition numbers have quite a few left. There might be others too.

If you want to factor numbers in the 105-110 range there's more to choose from.

Cyclotomic Number 186 284 has a factor
 

Jason,

SIQS found P32 and P56.

I started this number on 2 different computers. After combining
the .dat files, I moved msieve.dat to a 3rd computer. It worked
correctly.
[code]
Factorizations of Cyclotomic Numbers
[url]http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm[/url]

(186 284 (19531 1263697490114153509936871293 75855712674567017156832568711) (C 87))

g4-867:~/Desktop/QS08 k5gj$ ./cyclotomic 186 284
1587182636842032608648908139013625640090109463475745874524492780047330388332199125716299641751391798557156202913562104218049051128034107299264260701
g4-867:~/Desktop/QS08 k5gj$


n = 1587182636842032608648908139013625640090109463475745874524492780047330388332199125716299641751391798557156202913562104218049051128034107299264260701
x = n ÷ 19531;
y = x ÷ 1263697490114153509936871293;
z = y ÷ 75855712674567017156832568711

Out[2]:= 847756264967589555093489603701176712466045979605096185419530442561195713232111810813477
Out[3]:= False
Out[4]:= 87

/******************************************************************************/

F:\>
F:\>ver
Microsoft Windows 2000 [Version 5.00.2195]
F:\>
F:\>msieve < c87.txt

Msieve v. 0.86
random seeds: 00000724 41b4bc3b
input to factor: factoring 847756264967589555093489603701176712466045979605096185419530442561195713232111810813477
Mon Dec 06 14:08:27 2004
using multiplier of 1
Mon Dec 06 14:08:28 2004
using sieve block of 65536
using a sieve bound of 1497281 (57000 primes)
using large prime bound of 119782480
using double large prime bound of 347622531945200

received signal 2; shutting down
found 6788 relations (4893 full + 1895 partial), need 57128
Mon Dec 06 14:36:51 2004
F:\>

g4-867:~/Desktop/QS08 k5gj$
g4-867:~/Desktop/QS08 k5gj$ ./qs086 < c87.txt

Msieve v. 0.86
random seeds: 00000260 41b4bb9a
input to factor: factoring 847756264967589555093489603701176712466045979605096185419530442561195713232111810813477
Mon Dec 6 14:05:46 2004
using multiplier of 1
Mon Dec 6 14:05:51 2004
using sieve block of 32768
using a sieve bound of 1497281 (57000 primes)
using large prime bound of 119782480
using double large prime bound of 347622531945200

sieving in progress (press Ctrl-C to pause)
found 25 relations (25 full + 0 partial), need 57128
found 50 relations (50 full + 0 partial), need 57128
|
|
found 2092 relations (1884 full + 208 partial), need 57128
found 2120 relations (1909 full + 211 partial), need 57128
^C
received signal 2; shutting down
found 2139 relations (1926 full + 213 partial), need 57128
found 2139 relations (1926 full + 213 partial), need 57128
Mon Dec 6 14:41:00 2004
g4-867:~/Desktop/QS08 k5gj$

concatenate the .dat files

g4-867:~/Desktop/QS08 k5gj$ ./qs086 < c87.txt

Msieve v. 0.86
random seeds: 00000275 41b4c444
input to factor: factoring 847756264967589555093489603701176712466045979605096185419530442561195713232111810813477
Mon Dec 6 14:42:44 2004
using multiplier of 1
Mon Dec 6 14:42:50 2004
using sieve block of 32768
using a sieve bound of 1497281 (57000 primes)
using large prime bound of 119782480
using double large prime bound of 347622531945200
restarting with 6819 full and 264616 partial relations

sieving in progress (press Ctrl-C to pause)
^Cund 13011 relations (7546 full + 5465 partial), need 57128
received signal 2; shutting down
found 13038 relations (7554 full + 5484 partial), need 57128
Mon Dec 6 14:56:16 2004
g4-867:~/Desktop/QS08 k5gj$

move to 3rd system.

gigabyte#
gigabyte# ./qs086 < c87.txt
Msieve v. 0.86
random seeds: 00000604 41b4c7f6
input to factor: factoring 847756264967589555093489603701176712466045979605096185419530442561195713232111810813477
Mon Dec 6 14:58:30 2004
using multiplier of 1
Mon Dec 6 14:58:31 2004
using sieve block of 65536
using a sieve bound of 1497281 (57000 primes)
using large prime bound of 119782480
using double large prime bound of 347622531945200
restarting with 7554 full and 291901 partial relations

sieving in progress (press Ctrl-C to pause)
found 13044 relations (7579 full + 5465 partial), need 57128
found 13122 relations (7604 full + 5518 partial), need 57128
|
|
found 57144 relations (15669 full + 41475 partial), need 57128
found 57144 relations (15669 full + 41475 partial), need 57128
begin with 602700 relations
reduce to 124782 relations in 9 passes
attempting to read 15669 full and 124782 partial relations
recovered 15669 full and 124782 partial relations
recovered 52363 polynomials
attempting to build 42798 cycles
found 42835 cycles in 4 passes
distribution of cycle lengths:
length 2 : 11715
length 3 : 10525
length 4 : 7810
length 5 : 5299
length 6 : 3373
length 7 : 1970
length 8 : 1071
length 9+: 1072
largest cycle: 16 relations
Mon Dec 6 15:42:41 2004
57000 x 57064 system, weight 3062629 (avg 53.67/col)
reduce to 55314 x 55378 in 3 passes
lanczos halted after 876 iterations
recovered 60 nontrivial dependencies
Mon Dec 6 15:43:15 2004
probable prime factor: 35249411841626844966940712882101
probable prime factor: 24050224405913479450695270469205252610010708484047321777
Mon Dec 6 15:43:34 2004
gigabyte#

/******************************************************************************/

n = 35249411841626844966940712882101 * 24050224405913479450695270469205252610010708484047321777
Out[2]:= 847756264967589555093489603701176712466045979605096185419530442561195713232111810813477
Out[3]:= False
Out[4]:= 87

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/[/code]

Cyclotomic number 99 826 has a factor ...
 

SIQS found P36 and P47.
[code]
Factorizations of Cyclotomic Numbers
[url]http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm[/url]

(99 826 (6511033 3071523709 37199281416067 9270431275041380019786037653079 306749588201882934841179865914409) (C 82))

g4-867:~/Desktop/QS08 k5gj$ ./cyclotomic 99 826
10442460434811543851036603116280792918175239938509535428619629668182981000768788211708006666701576905805359769691592884119271682210601590467509227406223163692777321119078231001
g4-867:~/Desktop/QS08 k5gj$


n = 10442460434811543851036603116280792918175239938509535428619629668182981000768788211708006666701576905805359769691592884119271682210601590467509227406223163692777321119078231001
v = n ÷ 6511033;
w = v ÷ 3071523709;
x = w ÷ 37199281416067;
y = x ÷ 9270431275041380019786037653079;
z = y ÷ 306749588201882934841179865914409

Out[2]:= 4936061843453811016829313414572461525885255047597169452505157331447823187855089609
Out[3]:= False
Out[4]:= 82

/******************************************************************************/

Script started on Tue 07 Dec 2004 06:50:21 PM CST
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# uname -a
Linux k8-2200.k5gj 2.6.9-1.667 #1 Tue Nov 2 14:50:10 EST 2004 x86_64 x86_64 x86_64 GNU/Linux
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# gcc -v
Reading specs from /usr/lib/gcc/x86_64-redhat-linux/3.4.2/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --disable-checking --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-languages=c,c++,objc,java,f77 --enable-java-awt=gtk --host=x86_64-redhat-linux
Thread model: posix
gcc version 3.4.2 20041017 (Red Hat 3.4.2-6.fc3)
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# gcc -O3 -march=k8 *.c -o qs086 -lm
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# time ./qs086 < c82.txt

Msieve v. 0.86
random seeds: 000010f3 41b65005
input to factor: factoring 4936061843453811016829313414572461525885255047597169452505157331447823187855089609
Tue Dec 7 18:51:17 2004
using multiplier of 1
Tue Dec 7 18:51:18 2004
using sieve block of 65536
using a sieve bound of 1347473 (51765 primes)
using large prime bound of 64678704

sieving in progress (press Ctrl-C to pause)
found 27 relations (27 full + 0 partial), need 51893
found 54 relations (54 full + 0 partial), need 51893
|
|
found 51952 relations (29581 full + 22371 partial), need 51893
found 51952 relations (29581 full + 22371 partial), need 51893
begin with 207228 relations
reduce to 41753 relations in 2 passes
attempting to read 29581 full and 41753 partial relations
recovered 29581 full and 41753 partial relations
recovered 20268 polynomials
attempting to build 22371 cycles
found 22371 cycles in 1 passes
distribution of cycle lengths:
length 2 : 22371
largest cycle: 2 relations
Tue Dec 7 19:07:58 2004
51765 x 51829 system, weight 1560004 (avg 30.10/col)
reduce to 44017 x 44081 in 4 passes
lanczos halted after 698 iterations
recovered 55 nontrivial dependencies
Tue Dec 7 19:08:12 2004
probable prime factor: 167355397701100468717339340648675161
probable prime factor: 29494488443508107148212441803298989563607043569
Tue Dec 7 19:08:18 2004

real 17m0.872s
user 16m56.694s
sys 0m0.609s
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# exit
Script done on Tue 07 Dec 2004 07:20:32 PM CST

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

n = 167355397701100468717339340648675161 * 29494488443508107148212441803298989563607043569
Out[2]:= 4936061843453811016829313414572461525885255047597169452505157331447823187855089609
Out[3]:= False
Out[4]:= 82

/******************************************************************************/[/code]

Finished a cyclotomic c92
 

Jason,
I found this thread by sheer accident, and have been following for about a week. Awesome work so far! I've been playing around with Chris Monico's GGNFS, but unfortunately I am not a tool compiler, just a tool user, so I was using a version several iterations old. I was trying to finish a c92 that I had left over from some ECM work and it finished in something <48 hours on my 500 MHz PIII. (Not sure of exact timings, since something took Windows down before it finished.) The parameters I found for the GGNFS run looked like they were probably going to take something close to a week on my PC, so I gave up and went back to running ECM until I found this thread.

Here's the end of the run for MSIEVE:

[CODE]
Msieve v. 0.86
random seeds: fffde701 41aefc11
input to factor: factoring 23937692750769546636249217580448924462754132003905656338912493086637095276379223175105431209
Sun Dec 06 03:27:13 2004
using multiplier of 5
Sun Dec 06 03:27:23 2004
using sieve block of 16384
using a sieve bound of 1635187 (61742 primes)
using large prime bound of 171694635
using double large prime bound of 664602632638035
restarting with 13095 full and 603519 partial relations

found 61882 relations (16302 full + 45580 partial), need 61870
begin with 747989 relations
reduce to 136415 relations in 12 passes
attempting to read 16302 full and 136415 partial relations
recovered 16302 full and 136415 partial relations
recovered 85892 polynomials
attempting to build 45580 cycles
found 45580 cycles in 6 passes
distribution of cycle lengths:
length 2 : 11827
length 3 : 10899
length 4 : 8288
length 5 : 5837
length 6 : 3744
length 7 : 2234
length 8 : 1333
length 9+: 1418
largest cycle: 21 relations
Sun Dec 06 09:05:09 2004
61742 x 61806 system, weight 3543269 (avg 57.33/col)
reduce to 60406 x 60470 in 3 passes
lanczos halted after 957 iterations
recovered 62 nontrivial dependencies
Sun Dec 06 09:15:49 2004
probable prime factor: 87541363466302288471663549286672626267
probable prime factor: 273444367358797147894028674749900087959879536072766027
Sun Dec 06 09:18:35 2004
[/CODE]

I've got a c86 I'm running right now.

One minor little issue I saw was with whitespace handling on the input file. When I generated the number, UBASIC put a space at the front of the number, so the first run I got a message like this: ' 283343......' is not a number.....


Keep up the good work.

Later,
Frank

[QUOTE=schickel]
I found this thread by sheer accident, and have been following for about a week. Awesome work so far!
[/QUOTE]
Thanks!
[QUOTE=schickel]
One minor little issue I saw was with whitespace handling on the input file. When I generated the number, UBASIC put a space at the front of the number, so the first run I got a message like this: ' 283343......' is not a number.....
[/QUOTE]
Easy to fix. I'll add it to the list.

jasonp

[QUOTE=schickel]I've been playing around with Chris Monico's GGNFS, but unfortunately I am not a tool compiler, just a tool user, so I was using a version several iterations old. [/quote]

It's actually very easy to compile once you've got cygwin running.

[QUOTE=schickel] I was trying to finish a c92 that I had left over from some ECM work and it finished in something <48 hours on my 500 MHz PIII.
[/Quote]

A c92 is probably faster using the quadric sieve and much easier to set up. Numbers > 100 digits or so are faster using GNFS (msieve compared to GGNFS).

[QUOTE=schickel]
One minor little issue I saw was with whitespace handling on the input file. When I generated the number, UBASIC put a space at the front of the number, so the first run I got a message like this: ' 283343......' is not a number.....[/QUOTE]

You can use cutspc() to trim the space

[Quote=smh]It's actually very easy to compile once you've got cygwin running.[/Quote]

And therein lies the problem. Too much DOS in my early years is engrained pretty deep. I'm still fumbling my way around the whole Cygwin environment right now... :unsure: I'm still working on downloading a complete enough Cygwin setup, too. I'm at the far end of a crappy dialup line, so it's pretty slow work. (Think DSL=firehose, me=soda straw....:censored:) I also have a copy of VC++ which, if I ever get the impetus, I do actually plan to try to do something with, like try to compile a (newer) W32 version...

[Quote=smh]You can use cutspc() to trim the space.[/Quote]

Well, I know for next time. I'm more of a Delphi person myself, so I usually don't even take whitespace into account.

Also, I finished two factorizations last night. I had a c91 I was working on which I put on hold to run a c86. I ran a batch to go back to the c91 when the c86 was done and found them both done this morning, which was a nice surprise. I figured the c91 was only about half done and needed at least another 12 hours or so.....:banana:


Later,
Frank

[CODE]Msieve v. 0.86
random seeds: 00000ac0 41b7744e
factoring 5261230112474183111653669424622830268152541190704276733630317107097603885173108627846505174177061801
Wed Dec 08 22:38:22 2004
using multiplier of 1
Wed Dec 08 22:38:25 2004
using sieve block of 65536
using a sieve bound of 1872109 (69946 primes)
using large prime bound of 561632700
using double large prime bound of 5610664057485900


sieving in progress (press Ctrl-C to pause)
found 70093 relations (14504 full + 55589 partial), need 70074
begin with 1556820 relations
reduce to 186145 relations in 12 passes
attempting to read 14504 full and 186145 partial relations
recovered 14504 full and 186145 partial relations
recovered 176651 polynomials
attempting to build 55589 cycles
found 55589 cycles in 7 passes
distribution of cycle lengths:
length 2 : 10615
length 3 : 10960
length 4 : 9562
length 5 : 8034
length 6 : 5615
length 7 : 4072
length 8 : 2707
length 9+: 4024
largest cycle: 28 relations
Fri Dec 10 13:23:01 2004
69946 x 70010 system, weight 5067164 (avg 72.38/col)
reduce to 69471 x 69535 in 3 passes
lanczos halted after 1100 iterations
recovered 60 nontrivial dependencies
Fri Dec 10 13:27:30 2004
probable prime factor: 866509691540844271532732996709594633227
probable prime factor: 6071749876355753270908403958358496758132678092506191524465563
Fri Dec 10 13:28:44 2004[/CODE]

On with another factorization... :wink:

Luigi

What cpu was used?

Jason, can you make a next version print the time it took to do the factorization?

[QUOTE=smh]What cpu was used?

Jason, can you make a next version print the time it took to do the factorization?[/QUOTE]
That information can be inferred from the timestamps sprinkled through
the output. It looks like ~39 hours.

Maybe I can take a lesson from ppsiqs.exe, which saves durations in
its savefiles, and can give you an accurate runtime even if it was halted
during the run.

The next version will actually be released this evening. I can put something
like this in the queue for the version after that...

jasonp