mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-11-23, 16:14   #1
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default 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
akruppa is offline   Reply With Quote
Old 2012-11-23, 16:29   #2
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

4,637 Posts
Default

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);
      }
    }
  }
}
Attached Files
File Type: zip snfspoly.zip (1.8 KB, 57 views)

Last fiddled with by pinhodecarlos on 2012-11-23 at 16:33
pinhodecarlos is online now   Reply With Quote
Old 2012-11-23, 17:41   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000110100012 Posts
Default

[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
fivemack is offline   Reply With Quote
Old 2012-12-04, 02:48   #4
swellman
 
swellman's Avatar
 
Jun 2012

23·353 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
swellman is online now   Reply With Quote
Old 2012-12-04, 09:20   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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.
akruppa is offline   Reply With Quote
Old 2012-12-04, 09:24   #6
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

10,193 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
Hmm, interesting. I'm going to have to think more about this one.

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

Paul
xilman is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Auto-XYYXF tool fivemack NFS@Home 3 2016-07-06 04:01

All times are UTC. The time now is 18:48.

Wed Aug 12 18:48:00 UTC 2020 up 26 days, 14:34, 0 users, load averages: 2.80, 2.33, 2.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.