- Notifications
You must be signed in to change notification settings - Fork 0
Files
/
searchLLR.cc
103 lines (98 loc) · 3.83 KB
/
searchLLR.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// searchLLR b n1@n2 <source
// b is the base, source provides a series of linear families s1{d}s2,
// n1 is the first repetition number of d, n2 the last one
// the program creates a sieve of exponents to analyse,
// then calls llr64; results are sent to lresu<b>00.txt
#include <list>
#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <time.h>
#include <sstream>
#include <stdlib.h>
#define factl 100000
using namespace std;
using sint=long int; // std::vector<std::__cxx11::basic_string<char> >::size_type;
string p,p1,p2,pp,s,ss,sss,lru,pref;
sint b,j,lgmin,lgmax,x1,x2,b1,b2,k,k1,k2,lg,lg1;
vector <sint> fact,listn;
char tr[128]; int w[128];
ofstream result,lresult;
void buildfact()
{sint kk,n,nn,n1; bool ok;
fact.push_back(2);fact.push_back(3);fact.push_back(5);
nn=1;n1=factl;
for(lg1=0;nn<n1;lg1++){nn=nn*b;}
lg1=2*lg1;
for(n=7;true;n++)
{ok=true;for(kk=0;fact[kk]*fact[kk]<=n;kk++)if(n%fact[kk]==0){ok=false;break;}
if(ok){fact.push_back(n);if(n>nn)break;}
}
}
bool ok(unsigned long long int n) // is prime?
{sint kk;
if (n<2) return false;
for (kk=0;fact[kk]*fact[kk]<=n;kk++)
{if(n % fact[kk]==0)return false;}
return true;
}
sint gcd(sint a,sint b)
{if(b==0)return a;
return gcd(b,a%b);
}
int main(int argc, char *argv[])
{int i,c,x,n; string bs,com; bs=argv[1]; b=atoi(argv[1]);
for(char c='0';c<='9';c++){w[c]=0+c-'0';tr[0+c-'0']=c;}
for(char c='A';c<='Z';c++){w[c]=10+c-'A';tr[10+c-'A']=c;}
for(char c='a';c<='z';c++){w[c]=36+c-'a';tr[36+c-'a']=c;}
buildfact();
s=argv[2]; for(i=0;i<s.length();i++)if(s[i]=='@')break;
ss=s.substr(0,i);lgmin=stoi(ss);
if(i!=s.length()){sss=s.substr(i+1,s.length());lgmax=stoi(sss);} else {lgmax=lgmin;lgmin=2;}
pref="llr-data"+bs; lru="lresu"+bs+"00.txt";
lresult.open(lru.c_str(),ios::app);
lresult<<"search for possible exponents in base "<<b<<"; lgmin="<<lgmin<<", lgmax="<<lgmax<<"; greater tested prime factor="<<fact.back()<<"\n";
lresult.close();
while(cin>>p)
{lresult.open(lru.c_str(),ios::app); lresult<<p<<":";
result.open(pref.c_str(),ios::trunc);
lg=0;x1=0;for(j=0;j<p.length();j++) if(p[j]=='{')break;else{lg++;x1=x1*b+w[p[j]];}j++;
c=w[p[j]];j++; if(p[j]!='}')abort();x2=0;b2=1;
for(j=j+1;j<p.length();j++){x2=x2*b+w[p[j]];b2=b2*b;}
b1=b-1;k1=(b1*x1+c)*b2;k2=b1*x2-c*b2;
k=gcd(abs(k2),gcd(k1,b1));k1=k1/k;k2=k2/k;b1=b1/k;
if(k2>=0){if(b1!=1)
{result<<"ABC ("<<k1<<"*"<<b<<"^n+"<<k2<<")/"<<b1<<"\n";
lresult<<"ABC ("<<k1<<"*"<<b<<"^n+"<<k2<<")/"<<b1<<"\n";
}
else
{result<<"ABC "<<k1<<"*"<<b<<"^n+"<<k2<<"\n";
lresult<<"ABC "<<k1<<"*"<<b<<"^n+"<<k2<<"\n";
}
}
else{if(b1!=1)
{result<<"ABC ("<<k1<<"*"<<b<<"^n"<<k2<<")/"<<b1<<"\n";
lresult<<"ABC ("<<k1<<"*"<<b<<"^n"<<k2<<")/"<<b1<<"\n";
}
else
{result<<"ABC "<<k1<<"*"<<b<<"^n"<<k2<<"\n";
lresult<<"ABC "<<k1<<"*"<<b<<"^n"<<k2<<"\n";
}
}
listn.clear();for(j=lgmin;j<=lgmax;j++)listn.push_back(j);
for(i=0;i<fact.size();i++)
{x=x1;n=0;
for(j=0;j<listn.size();j++)
{for(k=n;k<listn[j];k++)x=(x*b+c)%fact[i];n=listn[j];
if((x*b2+x2)%fact[i]==0){listn.erase(listn.begin()+j);j--;}
}
}
for(j=0;j<listn.size();j++)result<<listn[j]<<"\n";result.close();
lresult.close();
com="rm llr"+bs+"00.ini";
system(com.c_str());
com="llr64 -d "+pref+" -oStopOnSuccess=1 -oBPSW=1 -a"+bs+"00 >brol";
system(com.c_str());
}
} // fin main