Cyclotomic 186 413 has a factor
 

Jason,

Using the user friendly directions, SIQS found P30 and P55.

Factorizations of Cyclotomic Numbers
[url]http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm[/url]

(186 413 (26041 44129185821775543 1177318602598582250299 12453627870424609391567897718097) (C 84))


Using Alex Kruppa's cyclotomic.c

root@p4-2682:/home/k5gj#
root@p4-2682:/home/k5gj# ./cyclotomic
./cyclo <N> <x>
Computes the value of the <N>th cyclotomic polynomial at point <x>.
N must be a positive integer, x must be an integer
root@p4-2682:/home/k5gj#
root@p4-2682:/home/k5gj#
root@p4-2682:/home/k5gj# ./cyclotomic 186 413
9079321246760266701196696023933865233390240946717311897322820366185366850410451211416266719958034623042003863963300317375518745442680321242772375146566517369
root@p4-2682:/home/k5gj#


Using Mathematica

In[1]:= ClearAll[]
n = 9079321246760266701196696023933865233390240946717311897322820366185366850410451211416266719958034623042003863963300317375518745442680321242772375146566517369;
w = n ÷ 26041;
x = w ÷ 44129185821775543;
y = x ÷ 1177318602598582250299;
z = y ÷ 12453627870424609391567897718097
PrimeQ[z]
Length[IntegerDigits[z]]

Out[2]:= 538864929490711709797512456311393620958529115592409693915023137785609088666438955221
Out[3]:= False
Out[4]:= 84

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

Script started on Sun Dec 5 18:30:06 2004
gigabyte#
gigabyte#
gigabyte# time ./qs086 < c84.txt
Msieve v. 0.86
random seeds: 0000021b 41b3a81c
input to factor: factoring 538864929490711709797512456311393620958529115592409693915023137785609088666438955221
Sun Dec 5 18:30:20 2004
using multiplier of 1
Sun Dec 5 18:30:21 2004
using sieve block of 65536
using a sieve bound of 1407323 (53824 primes)
using large prime bound of 95697964

sieving in progress (press Ctrl-C to pause)
found 26 relations (25 full + 1 partial), need 53952
found 52 relations (50 full + 2 partial), need 53952
|
|
found 53964 relations (27765 full + 26199 partial), need 53952
found 53964 relations (27765 full + 26199 partial), need 53952
begin with 258962 relations
reduce to 48971 relations in 2 passes
attempting to read 27765 full and 48971 partial relations
recovered 27765 full and 48971 partial relations
recovered 39950 polynomials
attempting to build 26199 cycles
found 26199 cycles in 1 passes
distribution of cycle lengths:
length 2 : 26199
largest cycle: 2 relations
Sun Dec 5 19:25:44 2004
53824 x 53888 system, weight 1658265 (avg 30.77/col)
reduce to 47581 x 47645 in 4 passes
lanczos error: not all columns used
lanczos halted after 754 iterations
linear algebra failed; retrying...
lanczos halted after 754 iterations
recovered 62 nontrivial dependencies
Sun Dec 5 19:26:18 2004
probable prime factor: 346082432810284958084726260561
probable prime factor: 1557042133329275408168212868258129061648358517436501061
Sun Dec 5 19:26:26 2004
3347.931u 11.632s 56:06.71 99.7% 71+43154k 2+158io 6pf+0w
gigabyte#
gigabyte#
gigabyte# exit
Script done on Sun Dec 5 19:27:44 2004

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

Using Mathematica

n = 346082432810284958084726260561 * 1557042133329275408168212868258129061648358517436501061

Out[2]:= 538864929490711709797512456311393620958529115592409693915023137785609088666438955221
Out[3]:= False
Out[4]:= 84

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

Segmentation Fault
 

Jason,

SIQS completed the run and generated a segmentation fault.
Restarting also generates segmentation faults.
[code]
Factorizations of Cyclotomic Numbers
[url]http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm[/url]

(95 102 (191 255361 233208807810643451 154471008061557210898451) (C 97))


Using Alex Kruppa's cyclotomic.c

root@p4-2682:/home/k5gj# ./cyclotomic 95 102
4120344881551650102177241238433008645791897745242013634779918233868952106754945330497167695530932824148537616991645654807101341802143677974305211
root@p4-2682:/home/k5gj#


Using Mathematica

n = 4120344881551650102177241238433008645791897745242013634779918233868952106754945330497167695530932824148537616991645654807101341802143677974305211;
w = n ÷ 191;
x = w ÷ 255361;
y = x ÷ 233208807810643451;
z = y ÷ 154471008061557210898451

Out[2]:= 2345058611503884540925422185958077060316993945836417897272899799983211849510845345120981987125861
Out[3]:= False
Out[4]:= 97

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

ASUS K8V-SE motherboard, AMD64-3400+
K8-2200, 64K L1, 1M L2, BUS 200 MHz, 512M DDR400 PC3200
64-bit Fedora Core 3

[root@k8-2200 QS08]#
[root@k8-2200 QS08]# uname -a
Linux k8-2200.localdomain 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]#
[root@k8-2200 QS08]# gcc40 -v
Reading specs from /usr/local/lib/gcc/x86_64-unknown-linux-gnu/4.0.0/specs
Configured with: /usr/gcc-4.0-20041128/./configure --program-suffix=40 --enable-languages=c,c++ --disable-nls
Thread model: posix
gcc version 4.0.0 20041128 (experimental)
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# gcc40 -O3 -march=k8 -m64 *.c -o qs086 -lm
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# ./qs086 < c97.txt

Msieve v. 0.86
random seeds: 00000d1c 41b3264d
input to factor: factoring 2345058611503884540925422185958077060316993945836417897272899799983211849510845345120981987125861
Sun Dec 5 09:16:29 2004
using multiplier of 1
Sun Dec 5 09:16:30 2004
using sieve block of 65536
using a sieve bound of 1774813 (66765 primes)
using large prime bound of 360287039
using double large prime bound of 2523291894858840

sieving in progress (press Ctrl-C to pause)
found 5 relations (5 full + 0 partial), need 66893
found 10 relations (10 full + 0 partial), need 66893
|
|
found 66921 relations (13848 full + 53073 partial), need 66893
found 66921 relations (13848 full + 53073 partial), need 66893
begin with 1244309 relations
reduce to 182087 relations in 11 passes
attempting to read 13848 full and 182087 partial relations
recovered 13848 full and 182087 partial relations
recovered 165281 polynomials
attempting to build 55506 cycles
Segmentation fault
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# ./qs086 < c97.txt

Msieve v. 0.86
random seeds: 00000dff 41b3d3ef
input to factor: factoring 2345058611503884540925422185958077060316993945836417897272899799983211849510845345120981987125861
Sun Dec 5 21:37:19 2004
using multiplier of 1
Sun Dec 5 21:37:21 2004
using sieve block of 65536
using a sieve bound of 1774813 (66765 primes)
using large prime bound of 360287039
using double large prime bound of 2523291894858840
restarting with 13848 full and 1244309 partial relations

found 66921 relations (13848 full + 53073 partial), need 66893
begin with 1244309 relations
reduce to 182087 relations in 11 passes
attempting to read 13848 full and 182087 partial relations
recovered 13848 full and 182087 partial relations
recovered 165281 polynomials
attempting to build 55506 cycles
Segmentation fault
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# ./qs086 < c97.txt

Msieve v. 0.86
random seeds: 00000e02 41b3d40b
input to factor: factoring 2345058611503884540925422185958077060316993945836417897272899799983211849510845345120981987125861
Sun Dec 5 21:37:47 2004
using multiplier of 1
Sun Dec 5 21:37:49 2004
using sieve block of 65536
using a sieve bound of 1774813 (66765 primes)
using large prime bound of 360287039
using double large prime bound of 2523291894858840
restarting with 13848 full and 1244309 partial relations

found 66921 relations (13848 full + 53073 partial), need 66893
begin with 1244309 relations
reduce to 182087 relations in 11 passes
attempting to read 13848 full and 182087 partial relations
recovered 13848 full and 182087 partial relations
recovered 165281 polynomials
attempting to build 55506 cycles
Segmentation fault
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#

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

[QUOTE=Mystwalker]In general (and given equal bounds), an ECM curve is a lot less likely to find a factor [/QUOTE]

Are you sure? I thought P-1 would find a factor if (P-1) was within the B1 & B2 bounds, while ECM would find a factor if a random number near P was within the bounds. The randomly selected sigma determines what the random number is. I thought this meant that P-1 has the same probability as an equivalent ECM curve but is faster.

William

What if we put a short list of numbers and coordinate the effort of both trying msieve and help factorization? :w00t:

Luigi

[QUOTE=wblipp]Are you sure? I thought P-1 would find a factor if (P-1) was within the B1 & B2 bounds, while ECM would find a factor if a random number near P was within the bounds. The randomly selected sigma determines what the random number is. I thought this meant that P-1 has the same probability as an equivalent ECM curve but is faster.[/QUOTE]

That's pretty much correct. Both p-1 and the order of the elliptic curve are more or less random integers close to p, so the probability that they are B1,B2-smooth is in the same ballpark.

However, the divisibility properties of a prime minus 1, and of the order of an elliptic curve using Montgomery's parameter choice, is subtly different.

A prime minus 1 is more likely to be smooth than a number of the same size chosen uniformly at random from the integers. For example, a (not too small) prime minus 1 is always divisible by 2, divisible by 3 with probability 1/2, divisible by 5 with probablilty 1/4 etc. This makes the number "look" as if it were smaller by a factor of ~3.41 in value.

Montgomery's parameter selection for elliptic curves ensures that the curve over Q has a torsion subgroup of order 12, thus a group order divisible by 12 over Z/Zp. (Alternatively a subgroup or order 8 or 16, but both Prime95 and gmp-ecm use the order 12 parameter choice.) It turns out in practice that the order is even smoother than that, the order seems to "look" smaller by a factor of about 24 on average. This is empirical data, afaik nothing has been proven about the extra smoothness beyond the torsion subgroup.

Thus, given a random p, ECM actually has a somewhat higher probability of success per curve than P-1, as the order of the elliptic curve tends to be smoother than p-1. If a reasonably large factor of p-1 is known, for example because p is a divisor of a cyclotomic or Lucas or Fibonacci etc. number, the advantage shifts in favour of P-1. P-1 is also almost an order of magnitude faster in stage 1.

Alex

[QUOTE=Mystwalker]ECM is probabilistic, so there is a certain chance finding a suitable factor. P-1 finds every factor within bounds. In general (and given equal bounds), an ECM curve is a lot less likely to find a factor (given that the factor size and shape is unknown) than a P-1 run, but is a lot faster.
But using a certain pair of bounds with P-1 and don't finding a factor doesn't mean that ECM with the same bounds won't find any.
Maybe this thread gives a little more info on that occurence: [url]http://www.mersenneforum.org/showthread.php?t=3135[/url][/QUOTE]
Are you sure of those statements?

In my experience, performing elliptic curve arithmetic is rather slower than performing essentially the same manipulations on integers.

I'm also rather doubtful about your claim that for a particular pair of bounds B1,B2, a single (presumed randomly chosen) elliptic curve is "a lot less likely to find a factor" than a P-1 computation with the same bounds B1.B2.

Paul

[QUOTE=error404]
SIQS completed the run and generated a segmentation fault.
Restarting also generates segmentation faults.
[/QUOTE]
Damn, I thought we were finished with these segfaults. I'm
about half done with this number, the sieving should be finished
by the time I get back from work.

Luigi, it would be a good idea to collect all the numbers that have
given the code problems, and make a QA suite out of that. I do
performance and correctness testing using a fixed set of ~6 numbers.

Several people have remarked that the numbers people typically
want factored have > 100 digits, so those would be pretty stressful
as tests go (both on the code and the tester :smile:).

jasonp

[QUOTE=jasonp]
Luigi, it would be a good idea to collect all the numbers that have
given the code problems, and make a QA suite out of that. I do
performance and correctness testing using a fixed set of ~6 numbers.

Several people have remarked that the numbers people typically
want factored have > 100 digits, so those would be pretty stressful
as tests go (both on the code and the tester :smile:).

jasonp[/QUOTE]

Fine, then. If you want to share work, just tell me which numbers should I retest. I'm working with version 0.86, celeron and athlon.

Luigi

[QUOTE=ET_]Fine, then. If you want to share work, just tell me which numbers should I retest. I'm working with version 0.86, celeron and athlon.
[/QUOTE]
Actually, I'd prefer that you wait for a short while. There's a bug I have to
track down, and the next version will include some major enhancements to
the sieving and the savefile format (I'm sure it will be faster, but I don't know
by how much because the sieve parameters will need retuning).

Of course, if someone *else* has numbers they want factored, they now
know who to call :smile:

I appreciate the offer.
jasonp

Cyclotomic number 186 152 has a factor
 

Jason,

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

(186 152 (1117 1489 1459294340824735433260848534309805453) (C 89))

g4-867:~/Desktop/QS08 k5gj$ ./cyclotomic 186 152
81933780844053993353957429209791886135030149087598190352329344598505064358815648189723097806889620438848140264087777135732388092569
g4-867:~/Desktop/QS08 k5gj$

n =
x = n ÷ 1117;
y = x ÷ 1489;
z = y ÷ 1459294340824735433260848534309805453

Out[2]:= 33757651605880619712827861853678607692515530473114371727532171803237077415975577801560721
Out[3]:= False
Out[4]:= 89

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

Script started on Mon Dec 6 07:29:37 2004
gigabyte#
gigabyte# uname -a
FreeBSD gigabyte.dl.cox.net 5.3-RELEASE-p2 FreeBSD 5.3-RELEASE-p2 #0: Sun Dec
5 13:02:41 CST 2004 [email]root@gigabyte.dl.cox.net[/email]:/usr/src/sys/amd64/compile/MYKERNEL amd64
gigabyte#
gigabyte#
gigabyte# gcc40 -v
Reading specs from /usr/local/lib/gcc/x86_64-portbld-freebsd5.3/4.0.0/specs
Configured with: ./..//gcc-4.0-20041128/configure --disable-nls --with-system-zlib --with-libiconv-prefix=/usr/local --program-suffix=40 --with-gxx-include-dir=/usr/local/lib/gcc/x86_64-portbld-freebsd5.3/4.0.0/include/c++/ --disable-shared --disable-libgcj --prefix=/usr/local x86_64-portbld-freebsd5.3
Thread model: posix
gcc version 4.0.0 20041128 (experimental) [FreeBSD]
gigabyte#
gigabyte#
gigabyte# gcc40 -O3 -march=k8 -m64 *.c -o qs086 -lm
gigabyte#
gigabyte#
gigabyte#
gigabyte# time ./qs086 < c89.txt

Msieve v. 0.86
random seeds: 0000022e 41b45f00
input to factor: factoring 33757651605880619712827861853678607692515530473114371727532171803237077415975577801560721
Mon Dec 6 07:30:40 2004
using multiplier of 1
Mon Dec 6 07:30:41 2004
using sieve block of 65536
using a sieve bound of 1556173 (58844 primes)
using large prime bound of 124493840
using double large prime bound of 372619898133360

sieving in progress (press Ctrl-C to pause)
found 25 relations (25 full + 0 partial), need 58972
found 51 relations (51 full + 0 partial), need 58972
|
|
found 59208 relations (17159 full + 42049 partial), need 58972
found 59208 relations (17159 full + 42049 partial), need 58972
begin with 606976 relations
reduce to 123887 relations in 10 passes
attempting to read 17159 full and 123887 partial relations
recovered 17159 full and 123887 partial relations
recovered 53167 polynomials
attempting to build 43367 cycles
found 43377 cycles in 3 passes
distribution of cycle lengths:
length 2 : 12907
length 3 : 10901
length 4 : 7817
length 5 : 5207
length 6 : 3042
length 7 : 1734
length 8 : 915
length 9+: 854
largest cycle: 16 relations
Mon Dec 6 09:01:14 2004
58844 x 58908 system, weight 3162541 (avg 53.69/col)
reduce to 56870 x 56934 in 3 passes
lanczos halted after 900 iterations
recovered 60 nontrivial dependencies
Mon Dec 6 09:01:51 2004
probable prime factor: 30469512918934386498005156108617821805275709
probable prime factor: 1107915695787277115335350635921117303077655269
Mon Dec 6 09:02:09 2004
5460.907u 17.329s 1:31:29.70 99.7% 71+57464k 3+352io 0pf+0w
gigabyte#
gigabyte#
gigabyte# exit
Script done on Mon Dec 6 09:03:48 2004

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

n = 30469512918934386498005156108617821805275709 * 1107915695787277115335350635921117303077655269
Out[2]:= 33757651605880619712827861853678607692515530473114371727532171803237077415975577801560721
Out[3]:= False
Out[4]:= 89

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

Core Dumped ...
 

Jason,

SIQS found P43 and P43 then dumped the core.
[code]
Factorizations of Cyclotomic Numbers
[url]http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm[/url]

(186 220 (1667050111 5464443482664751829353 1353062669101203728079589) (C 86))

g4-867:~/Desktop/QS08 k5gj$ ./cyclotomic 186 220
352639048821862708791836786192806678856568531278456924512641600312636253712201652394536384104356875559864818329522425852514476660924430792221
g4-867:~/Desktop/QS08 k5gj$

n = 352639048821862708791836786192806678856568531278456924512641600312636253712201652394536384104356875559864818329522425852514476660924430792221
x = n ÷ 1667050111;
y = x ÷ 5464443482664751829353;
z = y ÷ 1353062669101203728079589

Out[2]:= 28610002519413524908105375253180292962016621610769366636479537044824333203549496464783
Out[3]:= False
Out[4]:= 86

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

Script started on Mon Dec 6 09:22:16 2004
gigabyte#
gigabyte#
gigabyte# time ./qs086 < c86.txt
Msieve v. 0.86
random seeds: 00000329 41b47934
input to factor: factoring 28610002519413524908105375253180292962016621610769366636479537044824333203549496464783
Mon Dec 6 09:22:28 2004
using multiplier of 7
Mon Dec 6 09:22:29 2004
using sieve block of 65536
using a sieve bound of 1451911 (55324 primes)
using large prime bound of 116152880
using double large prime bound of 328892455058240

sieving in progress (press Ctrl-C to pause)
found 27 relations (26 full + 1 partial), need 55452
found 52 relations (51 full + 1 partial), need 55452
|
|
found 55626 relations (16309 full + 39317 partial), need 55452
found 55626 relations (16309 full + 39317 partial), need 55452
begin with 568416 relations
reduce to 115269 relations in 10 passes
attempting to read 16309 full and 115269 partial relations
recovered 16309 full and 115269 partial relations
recovered 36618 polynomials
attempting to build 40447 cycles
found 40451 cycles in 3 passes
distribution of cycle lengths:
length 2 : 12274
length 3 : 10340
length 4 : 7093
length 5 : 4735
length 6 : 2801
length 7 : 1604
length 8 : 862
length 9+: 742
largest cycle: 17 relations
Mon Dec 6 10:20:14 2004
55324 x 55388 system, weight 2842803 (avg 51.33/col)
reduce to 53239 x 53303 in 3 passes
lanczos halted after 843 iterations
recovered 59 nontrivial dependencies
Mon Dec 6 10:20:45 2004
probable prime factor: 3735834380356383356363286218775269337018319
probable prime factor: 7658263083034277179777057314568471549947457
Mon Dec 6 10:21:00 2004
qs086 in free(): error: chunk is already free
Abort (core dumped)
3493.074u 11.655s 58:32.53 99.7% 71+55264k 1+420io 1pf+0w
gigabyte#
gigabyte#
gigabyte# exit
Script done on Mon Dec 6 11:36:53 2004

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

n = 3735834380356383356363286218775269337018319 * 7658263083034277179777057314568471549947457
Out[2]:= 28610002519413524908105375253180292962016621610769366636479537044824333203549496464783
Out[3]:= False
Out[4]:= 86

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