mersenneforum.org XYYXF C200_111_110
 Register FAQ Search Today's Posts Mark Forums Read

 2012-11-23, 16:14 #1 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts XYYXF C200_111_110 Which polynomial would you use for the XYYXF number: Code: // C200_111_110 77215796253421280876381456380974445136193725510512173385737053215721798782046132110832277873978131147310324106427071437690162828839546260296387584341866441349207786683755945408920981833481128637483351 I haven't kept up with that project so I'm not aware of what polynomial selection tricks they usually use - I'm toying with an idea of my own tho. Last fiddled with by akruppa on 2012-11-23 at 16:14 Reason: grammared badly
2012-11-23, 16:29   #2
pinhodecarlos

"Carlos Pinho"
Oct 2011
Milton Keynes, UK

4,637 Posts

Did you try going here http://tech.groups.yahoo.com/group/xyyxf/files/ ?
There you will find C-program for SNFS polynominal calculation. See attachment or code.

Code:
#include <stdio.h>
#include "gmp.h"

#define MAX_FACTOR 300

void factor(int n, int factor[MAX_FACTOR])
{
int i;

for(i=0; i<MAX_FACTOR; i++) {
factor[i] = 0;
}
for(i=2; i<MAX_FACTOR; i++) {
if (n % i == 0) {
factor[i]++;
n /= i;
i--;
}
}
}

main(int argc, char** argv)
{
int i, j;
int x, y, len;
char buf[1024];
int x_factor[MAX_FACTOR];
int y_factor[MAX_FACTOR];
int count;
mpz_t n, tmpxy, tmpyx, tmp, common;
int digits;
int common_f;
int degree = 5;
char is_cubic, is_seventh, is_fifth;

mpz_t c0, c5, c2, y1, y0;
mpz_init(c0);
mpz_init(c5);
mpz_init(c2);
mpz_init(y1);
mpz_init(y0);
mpz_init(n);
mpz_init(tmp);
mpz_init(tmpxy);
mpz_init(tmpyx);
mpz_init(common);
if (argc>1) {
degree=atoi(argv[1]);
}
while (gets(buf) != 0) {
char reverse = 0;
char first = 0;
if ((buf[0] == 'C') || (buf[0] == '/')) {

if (buf[0] == 'C') sscanf(buf, "C%d_%d_%d", &len, &x, &y);
if (buf[0] == '/') sscanf(buf, "// C%d_%d_%d", &len, &x, &y);
factor(x, x_factor);
factor(y, y_factor);
mpz_set_ui(tmpxy, x);
mpz_pow_ui(tmpxy, tmpxy, y);
mpz_set_ui(tmpyx, y);
mpz_pow_ui(tmpyx, tmpyx, x);
digits = mpz_sizeinbase (n, 10);
printf("Original C%d_%d_%d contains %d digits\n", len, x, y, digits);

for(i=0; i<MAX_FACTOR; i++) {
y_factor[i] *= x;
x_factor[i] *= y;
}
printf("Y^X=");
first = 1;
for(i=0; i<MAX_FACTOR; i++) {
if (y_factor[i]>0) {
if (first == 1) {
first = 0;
} else {
printf("*");
}
printf("%d^%d", i, y_factor[i]);
}
}
printf("\n");
printf("X^Y=");
first = 1;
for(i=0; i<MAX_FACTOR; i++) {
if (x_factor[i]>0) {
if (first == 1) {
first = 0;
} else {
printf("*");
}
printf("%d^%d", i, x_factor[i]);
}
}
printf("\n");

count = 0;
mpz_set_ui(common, 1);
for(i=0; i<MAX_FACTOR; i++) {
if ((x_factor[i]>0) && (y_factor[i]>0)) {
count++;
#if 0
if (count == 1) {
printf("buf=%s\n", buf);
printf("x=%d, y=%d\n", x, y);
}
#endif
printf("x^y and y^x share factor of %d^%d\n", i,
(x_factor[i]<y_factor[i]) ? x_factor[i] : y_factor[i]);
if (x_factor[i] < y_factor[i])
common_f = x_factor[i];
else
common_f = y_factor[i];
x_factor[i] -= common_f;
y_factor[i] -= common_f;
mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, common_f);
mpz_mul(common, common, tmp);
}
}
if (mpz_cmp_ui(common, 1) >0) {
printf("common factor is ");
mpz_out_str(stdout, 10, common);
printf("\n");
mpz_div(n, n, common);
digits = mpz_sizeinbase (n, 10);
printf("Reduced C%d_%d_%d now contains %d digits\n", len, x, y, digits);
}

printf("Y^X=");
first = 1;
for(i=0; i<MAX_FACTOR; i++) {
if (y_factor[i]>0) {
if (first == 1) {
first = 0;
} else {
printf("*");
}
printf("%d^%d", i, y_factor[i]);
}
}
printf("\n");

mpz_set_ui(c0, 1);
mpz_set_ui(c5, 1);
mpz_set_ui(y0, 1);
mpz_set_ui(y1, 1);

printf("\nPoly file:\n********\nn: <copy from file>\n");
printf("name: C%d_%d_%d\n", len, x, y);
printf("#X^Y=(");
first = 1;
for(i=0; i<MAX_FACTOR; i++) {
if (x_factor[i]>0) {
if (first == 1) {
first = 0;
} else {
printf("*");
}
printf("%d^%d", i, (x_factor[i]) % degree);
mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, (x_factor[i])%degree);
mpz_mul(c0, c0, tmp);
}
}
if (first) printf("1");
printf(")*(");
first = 1;
for(i=0; i<MAX_FACTOR; i++) {
if (x_factor[i]>0) {
if (first == 1) {
first = 0;
} else {
printf("*");
}
printf("%d^%d", i, x_factor[i]/degree);
mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, x_factor[i]/degree);
mpz_mul(y1, y1, tmp);
}
}
printf(")^%d\n", degree);

printf("#Y^X=(");
first = 1;
for(i=0; i<MAX_FACTOR; i++) {
if (y_factor[i]>0) {
if (first == 1) {
first = 0;
} else {
printf("*");
}
printf("%d^%d", i, y_factor[i]%degree);
mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, y_factor[i]%degree);
mpz_mul(c5, c5, tmp);
}
}
if (first) printf("1");
printf(")*(");
first = 1;
for(i=0; i<MAX_FACTOR; i++) {
if (y_factor[i]>0) {
if (first == 1) {
first = 0;
} else {
printf("*");
}
printf("%d^%d", i, y_factor[i]/degree);
mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, y_factor[i]/degree);
mpz_mul(y0, y0, tmp);
}
}
printf(")^%d\n", degree);
/* We want the high-order coefficient to be the smaller number
so reverse it if necessary */
if (mpz_cmp(c5, c0) > 0) reverse = 1;
printf("deg: %d\nc%d: ", degree, degree);
mpz_out_str(stdout, 10, reverse ? c0 : c5);
printf("\n");
printf("c0: ");
mpz_out_str(stdout, 10, reverse ? c5: c0);
printf("\n");
printf("Y1: ");
mpz_out_str(stdout, 10, reverse ? y0: y1);
printf("\n");
printf("Y0: -");
mpz_out_str(stdout, 10, reverse ? y1: y0);
printf("\ntype: snfs\nskew: <vary from 1 to 10 and check secs/rel number>\n********\n");
is_cubic = 1;
for(i=0; is_cubic && (i<MAX_FACTOR); i++) {
if (x_factor[i] % 3 != 0) is_cubic=0;
if (y_factor[i] % 3 != 0) is_cubic=0;
}
is_fifth = 1;
for(i=0; is_fifth && (i<MAX_FACTOR); i++) {
if (x_factor[i] % 5 != 0) is_fifth=0;
if (y_factor[i] % 5 != 0) is_fifth=0;
}
is_seventh = 1;
for(i=0; is_seventh && (i<MAX_FACTOR); i++) {
if (x_factor[i] % 7 != 0) is_seventh=0;
if (y_factor[i] % 7 != 0) is_seventh=0;
}
if (is_fifth) {
printf("%f ratio POLY IS REDUCIBLE X^5+Y^5: C%d_%d_%d with %d digits\n", ((float)digits)/((7/(float)6)*(float)len), len, x, y, (4*digits)/5);
}
if (is_seventh) {
printf("%f ratio POLY IS REDUCIBLE X^7+Y^7: C%d_%d_%d with %d digits\n", ((float)digits)/((7/(float)6)*(float)len), len, x, y, (6*digits)/7);
}
if (is_cubic) {
printf("%f ratio POLY IS REDUCIBLE X^3+Y^3: C%d_%d_%d with %d digits\n", ((float)digits)/(1.5*(float)len), len, x, y, (2*digits)/3);
/* Convert x and y to a and b where a^3+b^3 = x^y + y^x */
for(i=0; i<MAX_FACTOR; i++) {
x_factor[i] /= 3;
y_factor[i] /= 3;
}
mpz_set_si(y0, -1);
mpz_set_ui(y1, 1);
mpz_set_ui(c5, 1);
mpz_set_si(c2, -1);
mpz_set_ui(c0, 1);
for(i=0; i<MAX_FACTOR; i++) {
if (x_factor[i]>0) {
mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, x_factor[i]/2);
mpz_mul(y1, y1, tmp);

mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, 2*(x_factor[i] % 2));
mpz_mul(c0, c0, tmp);

mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, x_factor[i] % 2);
mpz_mul(c2, c2, tmp);
}
if (y_factor[i]>0) {
mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, y_factor[i]/2);
mpz_mul(y0, y0, tmp);

mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, 2*(y_factor[i] % 2));
mpz_mul(c5, c5, tmp);

mpz_set_ui(tmp, i);
mpz_pow_ui(tmp, tmp, y_factor[i] % 2);
mpz_mul(c2, c2, tmp);
}

}
printf("deg: 4\nc4: ");
mpz_out_str(stdout, 10, c5);
printf("\n");
printf("c2: ");
mpz_out_str(stdout, 10, c2);
printf("\n");
printf("c0: ");
mpz_out_str(stdout, 10, c0);
printf("\n");
printf("Y1: ");
mpz_out_str(stdout, 10, y1);
printf("\n");
printf("Y0: ");
mpz_out_str(stdout, 10, y0);
printf("\n");
} else if ((mpz_cmp_ui(c5, 1)==0) && (mpz_cmp_ui(c0, 1)==0)) {
printf("%f ratio POLY IS REDUCIBLE: C%d_%d_%d with %d digits\n", ((float)digits)/(float)len, len, x, y, digits);
} else {
printf("%f ratio : C%d_%d_%d with %d digits\n", ((float)digits)/(float)len, len, x, y, digits);
}
}
}
}
Attached Files
 snfspoly.zip (1.8 KB, 57 views)

Last fiddled with by pinhodecarlos on 2012-11-23 at 16:33

 2012-11-23, 17:41 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 11000110100012 Posts [QUOTE=akruppa;319420]Which polynomial would you use for the XYYXF number: Code: // C200_111_110 77215796253421280876381456380974445136193725510512173385737053215721798782046132110832277873978131147310324106427071437690162828839546260296387584341866441349207786683755945408920981833481128637483351 I would say 111*T = 111^111+111*110^111, write 111=6*18+3 and say (111^4)*a^6 + (111*110^3)*b^6 a=111^18 b=110^18 but that's much too obvious and the 12-digit coefficients are pretty ugly ... obviously T=(111^22)^5 + 110*(110^22)^5 but degree 5 at 227 digits is not good
2012-12-04, 02:48   #4
swellman

Jun 2012

23·353 Posts

Quote:
 Originally Posted by akruppa Which polynomial would you use for the XYYXF number: Code: // C200_111_110 77215796253421280876381456380974445136193725510512173385737053215721798782046132110832277873978131147310324106427071437690162828839546260296387584341866441349207786683755945408920981833481128637483351 I haven't kept up with that project so I'm not aware of what polynomial selection tricks they usually use - I'm toying with an idea of my own tho.
XYYXF is where I do all my factoring - just wandered in one day and never left. This hardly makes me an expert but I've factored a good number of such composites.

Tried a few sample runs of that C200 composite with both degree 5 and 6 polys. Best result for me is the c5=1 and c0=110 with (111^22)^5 and (110^22)^5 as fivemack suggests, sieved on the rational side. The relations/sec is not great but it's the best poly I could find. It is what I would use. YMMV.

Curious if you ran the c program from the xyyxf yahoo group. Or found a better poly with your own methods - please share if so.

I would also encourage you and any other interested factorers to come over (or return) to the xyyxf group and throw some cycles at the project. Yoyo@home is methodically ECMing the remaining composites to the t50 level but there are lots of reasonably sized SNFS and GNFS numbers available for individual contributors. Or ECM some big composites yourself - lots of those available too.

 2012-12-04, 09:20 #5 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts I tried the program pinhodecarlos pointed out. I asked because we (the Nancy guys and I) noticed that it isn't actually particularly hard to make SNFS polynomial pairs with both degrees > 1. Just take a look at the polynomial resultant, e.g., polresultant(a1*x^4+a2, b1*x^3+b2) b2^4*a1^3 + b1^4*a2^3 and it should be clear why XYYX numbers sprang to my mind. Cunningham-like numbers could be expressed like that just as easily, for example x^4+2^148, 2^145*x^3+1 for F10. The common root can be found with a polynomial gcd. Unfortunately, I have not been able to find a two-nonlinear polynomial pair that acutally performs better than the usual degree [4,5,6],1 for any number. Maybe this idea is worthwhile for factoring numbers where currently no SNFS polynomial is known, by allowing more non-zero coefficient in the polynomial pair. The resultant gets a bit messy then, however, and odds are we are not actually interested in factoring numbers that admit to such a form.
2012-12-04, 09:24   #6
xilman
Bamboozled!

May 2003
Down not across

10,193 Posts

Quote:
 Originally Posted by akruppa I tried the program pinhodecarlos pointed out. I asked because we (the Nancy guys and I) noticed that it isn't actually particularly hard to make SNFS polynomial pairs with both degrees > 1. Just take a look at the polynomial resultant, e.g., polresultant(a1*x^4+a2, b1*x^3+b2) b2^4*a1^3 + b1^4*a2^3 and it should be clear why XYYX numbers sprang to my mind. Cunningham-like numbers could be expressed like that just as easily, for example x^4+2^148, 2^145*x^3+1 for F10. The common root can be found with a polynomial gcd. Unfortunately, I have not been able to find a two-nonlinear polynomial pair that acutally performs better than the usual degree [4,5,6],1 for any number. Maybe this idea is worthwhile for factoring numbers where currently no SNFS polynomial is known, by allowing more non-zero coefficient in the polynomial pair. The resultant gets a bit messy then, however, and odds are we are not actually interested in factoring numbers that admit to such a form.

Perhaps the GCW numbers might also provide candidates --- which is why I want to think more about the method.

Paul