View Single Post
Old 2020-08-02, 23:47   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

225328 Posts
Default

Code:
  period 60 for M11
  period 32340 for M23
  period 252 for M29
  period 516924 for M37
  period 822960 for M41
  period 420 for M43
  period 20338900 for M47
  period 1309620 for M53
  period 345603421440 for M59

(period is always a multiple of (p-1) )
_____________

main(int argc,char **argv) {
  uint64_t f,b,c,j,k,l,l2;
//...

  if(argc<=1) { printf(" Use: %s p\n\t (copyleft) 2020 S.Batalov\n",argv[0]); exit(0); }
  if(argc>1) l = atoll(argv[1]);
  printf("# %lld ... testing\n",l);
  l = 1ULL << l;
  l--;
  c = 4;
  for(f=1; f<=120000;f++) { # or some other number, -- to get into "real" cycle
    c = mulmod(c,c,l)-2;
  }
  b = c;
  c = mulmod(b,b,l)-2;
  for(f=1; c!=b && f<=l;f++) {
    c = mulmod(c,c,l)-2;
  }
  printf("  period %lld for M%lld\n",f,atoll(argv[1]));
  exit(0);
}
The cycle does not include 4 (of course*), and not 14 or even 194 for larger p values, but we can greedily simply scroll forward "far enough".

*we all already know that we will never see 4 again, because 6 is a nonresidue. 16 and 196 are residues
Batalov is offline   Reply With Quote