|
2012-11-23, 16:14
|
#1 |
"Nancy"
Aug 2002
Alexandria
246710 Posts |
XYYXF C200_111_110
Which polynomial would you use for the XYYXF number:
Code:
// C200_111_110 77215796253421280876381456380974445136193725510512173385737053215721798782046132110832277873978131147310324106427071437690162828839546260296387584341866441349207786683755945408920981833481128637483351 Last fiddled with by akruppa on 2012-11-23 at 16:14 Reason: grammared badly |
|
|
|
2012-11-23, 16:29
|
#2 |
"Carlos Pinho"
Oct 2011
Milton Keynes, UK
3×17×97 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);
mpz_add(n, tmpxy, tmpyx);
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);
}
}
}
}
Last fiddled with by pinhodecarlos on 2012-11-23 at 16:33 |
|
|
|
|
2012-11-23, 17:41
|
#3 |
|
(loop (#_fork))
Feb 2006
Cambridge, England
23·11·73 Posts |
[QUOTE=akruppa;319420]Which polynomial would you use for the XYYXF number:
Code:
// C200_111_110 77215796253421280876381456380974445136193725510512173385737053215721798782046132110832277873978131147310324106427071437690162828839546260296387584341866441349207786683755945408920981833481128637483351 (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 | |
Jun 2012
22·773 Posts |
Quote:
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 |
|
"Nancy"
Aug 2002
Alexandria
1001101000112 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 | |
|
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2·5,393 Posts |
Quote:
Perhaps the GCW numbers might also provide candidates --- which is why I want to think more about the method. Paul |
|
|
|
|
 |
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Auto-XYYXF tool | fivemack | NFS@Home | 3 | 2016-07-06 04:01 |
