Pascal's OPN roadblock files

[Happy5214]

Originally Posted by lavalamp

I have found that factor db will sometimes show different factorisations depending if one looks up b^n-1 or (b^n-1)/(b-1). I assume that sometimes in the backend (b^n-1)/(b-1) is not always linked as a factor of b^n-1, or perhaps that changes to one page may take a while to propogate to another.

Since I noticed that I've always made sure to report factors to both pages to ensure that they aren't missed.

I reported my factors directly to the cofactor pages, which should take care of both. I did have to create a ton of b^n-1 IDs though.

[henryzz]

Thank you, Pascal, for posting this. I will use this to help my work on taking most of the proof tree to 2500(and identifying the bits that this is difficult for). I also hope to post lists of composites that occur many times but don't necessarily occur first(like the txxx files). These should shorten the proof but may become irrelevant if numbers in the txxx files are factored. A large proportion of these will be useful for a long time due to txxx composites that are beyond our ability to factor currently. These files with have a format similar to the roadblocks file rather than the txxx files as they will have line counts.
Unfortunately, I have limited time to spend on this currently so getting this ready might take a while.

[SuikaPredator]

What will be done on one update of the files? I found that some of the partially factored composites disappeared on bound_on_m.txt and their remaining composites does not appear. Also, some composites that were not on the previous version appeared.

Btw, for bound_on_m.txt, I ran pm1 with B1=1e7 on all composites and pp1*3 with B1=1e7 on composites <10^700 and 900@1e6 ecm curves on 9% of the composites. For the newly appeared composites >10^830, 432@25e4 ecm curves have been done. All factors are uploaded to factordb. The factors found by ecm are attached.

[Happy5214]

Originally Posted by Pascal Ochem

I have asked skilled people to write suitable scripts, back in the days. If the file comp contains composites in tXXX format, the command
toto.sh comp
produces the files comp_f containing the factors in checkfacts format and comp_n containing the remaining composites.

Thanks for those scripts. However, it doesn't appear that match is a standard Unix utility (it's not on my box, and a search for its man page shows it as part of Mail Avenger). Is there an alternative?

[Pascal Ochem]

Originally Posted by Happy5214

Thanks for those scripts. However, it doesn't appear that match is a standard Unix utility (it's not on my box, and a search for its man page shows it as part of Mail Avenger). Is there an alternative?

Oups, I forgot about this one. Michael Rao wrote it. It can also be used by itself to match factors to their respective \(\sigma(p^e)\).
match c_file f_file
where c_file contains composites in tXXX format and f_file contains primes dividing composites in c_file (one prime per line),
produces the factors in checkfacts format.

match.cpp

#include <math.h>
#includet <stdio.h>
#include <stdlib.h>
#include <map>
#include <list>
#include <set>
#include <fstream>
#include <iostream>
using namespace std;
#include <gmpxx.h>
#include <assert.h>

typedef mpz_class int_t;

bool isdiv(const int_t &p,const int_t &q)
{
  return mpz_divisible_p(p.get_mpz_t(),q.get_mpz_t());
}

struct toto_t {
  toto_t(const int_t &p_,int q_,const int_t &n_):p(p_),q(q_),n(n_) {}
  int_t p;
  int q;
  int_t n;
};

list<int_t> nums;
list<toto_t> totos;

bool isprime(const int_t &a)
{
  return mpz_probab_prime_p(a.get_mpz_t(),15);
}

int main(int ac, char **av)
{
  int comp=0;
  int verb=0;
  int qp1=0;
  while(ac>1) {
    if(0==strcmp(av[1],"-co")) { comp=1; av++;ac--;continue;}
    if(0==strcmp(av[1],"-eq")) { comp=2; av++;ac--;continue;}
    if(0==strcmp(av[1],"-pr")) { verb=1; av++;ac--;continue;}
    if(0==strcmp(av[1],"-qp1")) { qp1=1; av++;ac--;continue;}
    break;
  }

  FILE *in;
  in=fopen(av[1],"r");
  assert(in);

  while(!feof(in)) {
    char bf[100000],bp[100000],ba[100000];
    int q;
    if(NULL==fgets(bf,100000,in)) break;
    if(bf[0]=='#' || bf[0]=='\n' || bf[0]==0 ) continue;
    if(3!=sscanf(bf,"%s %d %s",bp,&q,ba)) break;
    int_t p=int_t(bp);
    int_t f=int_t(ba);
    totos.push_back(toto_t(p,q-qp1,f));
  }

  fclose(in);

  in=fopen(av[2],"r");

  assert(in);
  while(!feof(in)) {
    char bf[100000],bp[100000];
    if(NULL==fgets(bf,100000,in)) break;
    if(1!=sscanf(bf,"%s",bp)) continue;
    int_t p=int_t(bp);
    if(p>1)
      nums.push_back(p);
  }
  fprintf(stderr,"nums: %d readed\n",int(nums.size()));
  
  fclose(in);
  
  int k=0,ss=totos.size();
  for(list<toto_t>::iterator it=totos.begin();it!=totos.end();it++) {
    if(k%1000==0 && verb)fprintf(stderr,"%d/%d\r",k,ss);
    k++;    
    for(list<int_t>::iterator iti=nums.begin();iti!=nums.end();++iti) {
      if((
	  (comp==0 && *iti<it->n) 
	  ||(comp==1 && *iti<=it->n) 
	  ||(comp==2 && *iti==it->n) 
	  )&& isdiv(it->n,*iti)) {
	char bf[100000];
	char bp[100000];
	char ba[100000];
	mpz_get_str(bp,10,it->p.get_mpz_t());
	mpz_get_str(ba,10,iti->get_mpz_t());
	sprintf(bf,"%s %d %s",bp,it->q+1,ba);
	if(comp==0 && !isprime(*iti)) {
	  fprintf(stderr,"div but not prime: %s\n",bf);
	} else {
	  printf("%s\n",bf);
	}
      }
    }
  }
  return 0;
}

[Happy5214]

Originally Posted by Pascal Ochem

Oups, I forgot about this one. Michael Rao wrote it. It can also be used by itself to match factors to their respective \(\sigma(p^e)\).
match c_file f_file
where c_file contains composites in tXXX format and f_file contains primes dividing composites in c_file (one prime per line),
produces the factors in checkfacts format.

[...]

Thanks. I also had to adjust toto.sh to use the current directory for the two other commands, since they're not on the PATH (e.g. ./match).