📄 lllgcd.c
字号:
FREEMPI(SHORTER);
SHORTER = COPYI(T);
FREEMATI(MATI);
MATI = COPYMATI(MATI2);
COUNT = K;
}
}
FREEMPI(T);
FREEMATI(MATI1);
FREEMATI(MATI2);
}
fprintf(outfile, "X[0]=");
printf("X[0]=");
for (i = 0; i < m; i++)
{
PRINTI(B->V[m - 1][i]);
printf(" ");
FPRINTI(outfile, B->V[m - 1][i]);
fprintf(outfile, " ");
}
fprintf(outfile, "=b[%u]: ", m);
printf("=b[%u]: ", m);
T = LENGTHSQRI(B, m - 1);
FPRINTI(outfile, T);
PRINTI(T);
fprintf(outfile, "\n");
printf("\n");
c = RSV(T, SHORTER);
if (c < 0)
{
FREEMPI(SHORTER);
SHORTER = COPYI(T);
for (i = 0; i < m; i++)
{
FREEMPI(MATI->V[0][i]);
MATI->V[0][i] = COPYI(B->V[m-1][i]);
}
COUNT = K;
}
FREEMPI(T);
count = COUNT + 1;
fprintf(outfile, "shortest of the vectors is number %d:", count);
printf("shortest of the vectors is number %d:", count);
for (i = 0; i < m; i++)
{
PRINTI(MATI->V[0][i]); printf(" ");
FPRINTI(outfile, MATI->V[0][i]); fprintf(outfile, " ");
}
FREEMATI(MATI);
fprintf(outfile, ": ");
printf(": ");
FPRINTI(outfile, SHORTER);
fprintf(outfile, "\n");
PRINTI(SHORTER);
printf("\n");
FREEMPI(SHORTER);
fclose(outfile);
FREEMATI(L);
for (i = 0; i <= m; i++)
FREEMPI(D[i]);
ffree((char *)D, (1 + m) * sizeof(MPI *));
for (i = 0; i < m; i++)
FREEMPI(A[i]);
ffree((char *)A, m * sizeof(MPI *));
for (i = 0; i < m; i++)
FREEMPI(XX[i]);
ffree((char *)XX, m * sizeof(MPI *));
return (B);
}
MPR *MPI_TO_MPR(MPI *N)
/* Converts an MPI to an MPR */
{
MPR *T;
T = BUILDMPR();
T->N = COPYI(N);
T->D = ONEI();
return (T);
}
void GCD10()
/* We compute an optimal multipliers for a[1],...,a[10]
* in the range p1<=a[1]<=q1 etc. and rel prime.
*/
{
USI l, m, p1, q1, p2, q2, p3, q3, p4, q4, p5, q5, p6, q6, m1, n1;
USI p7, q7, p8, q8, p9, q9, p10, q10;
USI i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, p, t;
int e;
USL x, y, z, u, v, v1, v2, v3, v4;
MPI *GCD, *T1, *T2, **XX, **X, *Temp, *DIFF;
MPMATI *MATI1, *BB, *MATI3, *Q, *M;
char buff[20];
FILE *outfile;
printf("Enter alpha=m/n, 1/4 < m/n <= 1: (ie enter m and n)");
scanf("%u%u", &m1, &n1);
strcpy(buff, "gcd10.out");
if(access(buff, R_OK) == 0)
unlink(buff);
printf("Enter the ranges pi,qi; 2 <= pi < qi < 2^32, i = 1,...,6: ");
scanf("%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u", &p1, &q1, &p2, &q2, &p3, &q3, &p4, &q4, &p5, &q5, &p6, &q6, &p7, &q7, &p8, &q8, &p9, &q9, &p10, &q10);
Flush();
m = 10;
p = m - 1;
for (i1 = p1; i1 <= q1; i1++)
{
for (i2 = p2; i2 <= q2; i2++)
{
for (i3 = p3; i3 <= q3; i3++)
{
for (i4 = p4; i4 <= q4; i4++)
{
for (i5 = p5; i5 <= q5; i5++)
{
for (i6 = p6; i6 <= q6; i6++)
{
for (i7 = p7; i7 <= q7; i7++)
{
for (i8 = p8; i8 <= q8; i8++)
{
for (i9 = p9; i9 <= q9; i9++)
{
for (i10 = p10; i10 <= q10; i10++)
{
x = GCDm((USL)i1, (USL)i2);
y = GCDm(x, (USL)i3);
z = GCDm(y, (USL)i4);
u = GCDm(z, (USL)i5);
v = GCDm(u, (USL)i6);
v1 = GCDm(v, (USL)i7);
v2 = GCDm(v1, (USL)i8);
v3 = GCDm(v2, (USL)i9);
v4 = GCDm(v3, (USL)i10);
if (v4 == 1)
{
printf("(i1,i2,i3,i4,i5,i6,i7,i8,i9,i10)=(%u,%u,%u,%u,%u,%u,%u,%u,%u,%u)\n", i1,i2,i3,i4,i5,i6,i7,i8,i9,i10);
MATI1 = BUILDMATI(m, 1);
MATI1->V[0][0] = CHANGE((USL) i1);
MATI1->V[1][0] = CHANGE((USL) i2);
MATI1->V[2][0] = CHANGE((USL) i3);
MATI1->V[3][0] = CHANGE((USL) i4);
MATI1->V[4][0] = CHANGE((USL) i5);
MATI1->V[5][0] = CHANGE((USL) i6);
MATI1->V[6][0] = CHANGE((USL) i7);
MATI1->V[7][0] = CHANGE((USL) i8);
MATI1->V[8][0] = CHANGE((USL) i9);
MATI1->V[9][0] = CHANGE((USL) i10);
BB = LLLGCD0M(MATI1, &GCD, m, m1, n1);
FREEMATI(MATI1);
FREEMPI(GCD);
MATI3 = BUILDMATI(1, m);
for (l = 0; l < m; l++)
MATI3->V[0][l] = COPYI(BB->V[m - 1][l]);
T1 = LENGTHSQRI(MATI3, 0);
Q = BB;
XX = (MPI **)mmalloc((USL)(p * sizeof(MPI *)));
for (t = 0; t < p; t++)
XX[t] = ZEROI();
while (1)
{
M = SHORTESTT0(Q, &X);
for (t = 0; t < p; t++)
{
Temp = XX[t];
XX[t] = ADDI(XX[t], X[t]);
FREEMPI(Temp);
FREEMPI(X[t]);
}
ffree((char *)X, p * sizeof(MPI *));
if (M == NULL)
break;
else
{
for (l = 0; l < Q->C; l++)
{
FREEMPI(Q->V[m - 1][l]);
Q->V[m - 1][l] = COPYI(M->V[0][l]);
}
FREEMATI(MATI3);
MATI3 = M;
}
}
T2 = LENGTHSQRI(MATI3, 0);
if (RSV(T2, T1) == -1)
{
outfile = fopen(buff, "a");
fprintf(outfile, "(%u,%u,%u,%u,%u,%u,%u,%u,%u,%u): ", i1,i2,i3,i4,i5,i6,i7,i8,i9,i10);
fprintf(outfile, "b[%u]", m);
for (t = 0; t < p; t++)
{
e = XX[t]->S;
if (e == -1)
{
fprintf(outfile, "+");
Temp = MINUSI(XX[t]);
if (!EQONEI(Temp))
FPRINTI(outfile, Temp);
fprintf(outfile, "b[%u]", t + 1);
FREEMPI(Temp);
}
if (e == 1)
{
fprintf(outfile, "-");
if (!EQONEI(XX[t]))
FPRINTI(outfile, XX[t]);
fprintf(outfile, "b[%u]", t + 1);
}
}
fprintf(outfile, ": ");
DIFF = SUB0I(T1, T2);
FPRINTI(outfile, DIFF);
FREEMPI(DIFF);
fprintf(outfile, "\n");
fclose(outfile);
}
for (t = 0; t < p; t++)
FREEMPI(XX[t]);
ffree((char *)XX, p * sizeof(MPI *));
FREEMATI(BB);
FREEMATI(MATI3);
FREEMPI(T1);
FREEMPI(T2);
}
}
}
}
}
}
}
}
}
}
}
return;
}
void GCD11()
/* We compute an optimal multipliers for a[1],...,a[11]
* in the range p1<=a[1]<=q1 etc. and rel prime.
*/
{
USI l, m, p1, q1, p2, q2, p3, q3, p4, q4, p5, q5, p6, q6, m1, n1;
USI p7, q7, p8, q8, p9, q9, p10, q10, p11, q11;
USI i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, p, t, i11;
int e;
USL x, y, z, u, v, v1, v2, v3, v4, v5;
MPI *GCD, *T1, *T2, **XX, **X, *Temp;
MPMATI *MATI1, *BB, *MATI3, *Q, *M;
char buff[20];
FILE *outfile;
printf("Enter alpha=m/n, 1/4 < m/n <= 1: (ie enter m and n)");
scanf("%u%u", &m1, &n1);
strcpy(buff, "gcd11.out");
if(access(buff, R_OK) == 0)
unlink(buff);
printf("Enter the ranges pi,qi; 2 <= pi < qi < 2^32, i = 1,...,11: ");
scanf("%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u", &p1, &q1, &p2, &q2, &p3, &q3, &p4, &q4, &p5, &q5, &p6, &q6, &p7, &q7, &p8, &q8, &p9, &q9, &p10, &q10, &p11, &q11);
Flush();
m = 11;
p = m - 1;
for (i1 = p1; i1 <= q1; i1++)
{
for (i2 = p2; i2 <= q2; i2++)
{
for (i3 = p3; i3 <= q3; i3++)
{
for (i4 = p4; i4 <= q4; i4++)
{
for (i5 = p5; i5 <= q5; i5++)
{
for (i6 = p6; i6 <= q6; i6++)
{
for (i7 = p7; i7 <= q7; i7++)
{
for (i8 = p8; i8 <= q8; i8++)
{
for (i9 = p9; i9 <= q9; i9++)
{
for (i10 = p10; i10 <= q10; i10++)
{
for (i11 = p11; i11 <= q11; i11++)
{
x = GCDm((USL)i1, (USL)i2);
y = GCDm(x, (USL)i3);
z = GCDm(y, (USL)i4);
u = GCDm(z, (USL)i5);
v = GCDm(u, (USL)i6);
v1 = GCDm(v, (USL)i7);
v2 = GCDm(v1, (USL)i8);
v3 = GCDm(v2, (USL)i9);
v4 = GCDm(v3, (USL)i10);
v5 = GCDm(v4, (USL)i11);
if (v5 == 1)
{
printf("(i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11)=(%u,%u,%u,%u,%u,%u,%u,%u,%u,%u,%u)\n", i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11);
MATI1 = BUILDMATI(m, 1);
MATI1->V[0][0] = CHANGE((USL) i1);
MATI1->V[1][0] = CHANGE((USL) i2);
MATI1->V[2][0] = CHANGE((USL) i3);
MATI1->V[3][0] = CHANGE((USL) i4);
MATI1->V[4][0] = CHANGE((USL) i5);
MATI1->V[5][0] = CHANGE((USL) i6);
MATI1->V[6][0] = CHANGE((USL) i7);
MATI1->V[7][0] = CHANGE((USL) i8);
MATI1->V[8][0] = CHANGE((USL) i9);
MATI1->V[9][0] = CHANGE((USL) i10);
MATI1->V[10][0] = CHANGE((USL) i11);
BB = LLLGCD(MATI1, &GCD, m, m1, n1);
FREEMATI(MATI1);
FREEMPI(GCD);
MATI3 = BUILDMATI(1, m);
for (l = 0; l < m; l++)
MATI3->V[0][l] = COPYI(BB->V[m - 1][l]);
T1 = LENGTHSQRI(MATI3, 0);
Q = BB;
XX = (MPI **)mmalloc((USL)(p * sizeof(MPI *)));
for (t = 0; t < p; t++)
XX[t] = ZEROI();
while (1)
{
M = SHORTESTT0(Q, &X);
for (t = 0; t < p; t++)
{
Temp = XX[t];
XX[t] = ADDI(XX[t], X[t]);
FREEMPI(Temp);
FREEMPI(X[t]);
}
ffree((char *)X, p * sizeof(MPI *));
if (M == NULL)
break;
else
{
for (l = 0; l < Q->C; l++)
{
FREEMPI(Q->V[m - 1][l]);
Q->V[m - 1][l] = COPYI(M->V[0][l]);
}
FREEMATI(MATI3);
MATI3 = M;
}
}
T2 = LENGTHSQRI(MATI3, 0);
if (RSV(T2, T1) == -1)
{
outfile = fopen(buff, "a");
fprintf(outfile, "(%u,%u,%u,%u,%u,%u,%u,%u,%u,%u,%u): ", i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11);
fprintf(outfile, "b[%u]", m);
for (t = 0; t < p; t++)
{
e = XX[t]->S;
if (e == -1)
{
fprintf(outfile, "+");
Temp = MINUSI(XX[t]);
if (!EQONEI(Temp))
FPRINTI(outfile, Temp);
fprintf(outfile, "b[%u]", t + 1);
FREEMPI(Temp);
}
if (e == 1)
{
fprintf(outfile, "-");
if (!EQONEI(XX[t]))
FPRINTI(outfile, XX[t]);
fprintf(outfile, "b[%u]", t + 1);
}
}
fprintf(outfile, "\n");
fclose(outfile);
}
for (t = 0; t < p; t++)
FREEMPI(XX[t]);
ffree((char *)XX, p * sizeof(MPI *));
FREEMATI(BB);
FREEMATI(MATI3);
FREEMPI(T1);
FREEMPI(T2);
}
}
}
}
}
}
}
}
}
}
}
}
return;
}
void GCD33()
/* We compute an optimal multipliers for a[1],a[2],a[3]
* in the range p1<=a[1]<=q1 etc. and rel prime.
*/
{
USI l, m, p1, q1, p2, q2, p3, q3, m1, n1, t;
USI i1, i2, i3, p;
int e;
USL x, y;
MPI *GCD, *T1, *T2, **XX, **X, *Temp, *DIFF;
MPMATI *MATI1, *BB, *MATI3, *Q, *M;
char buff[20];
FILE *outfile;
printf("Enter alpha=m/n, 1/4 < m/n <= 1: (ie enter m and n)");
scanf("%u%u", &m1, &n1);
strcpy(buff, "gcd33.out");
if(access(buff, R_OK) == 0)
unlink(buff);
printf("Enter the ranges pi,qi; 2 <= pi < qi < 2^32, i = 1,..3: ");
scanf("%u%u%u%u%u%u", &p1, &q1, &p2, &q2, &p3, &q3);
Flush();
m = 3;
p = m - 1;
for (i1 = p1; i1 <= q1; i1++)
{
for (i2 = p2; i2 <= q2; i2++)
{
printf("(i1,i2)=(%u,%u)\n", i1,i2);
for (i3 = p3; i3 <= q3; i3++)
{
x = GCDm((USL)i1, (USL)i2);
y = GCDm(x, (USL)i3);
if (y == 1)
{
MATI1 = BUILDMATI(m, 1);
MATI1->V[0][0] = CHANGE((USL) i1);
MATI1->V[1][0] = CHANGE((USL) i2);
MATI1->V[2][0] = CHANGE((USL) i3);
BB = LLLGCD0M(MATI1, &GCD, m, m1, n1);
FREEMATI(MATI1);
FREEMPI(GCD);
MATI3 = BUILDMATI(1, m);
for (l = 0; l < m; l++)
MATI3->V[0][l] = COPYI(BB->V[m - 1][l]);
T1 = LENGTHSQRI(MATI3, 0);
Q = BB;
XX = (MPI **)mmalloc((USL)(p * sizeof(MPI *)));
for (t = 0; t < p; t++)
XX[t] = ZEROI();
while (1)
{
M = SHORTESTT0(Q, &X);
for (t = 0; t < p; t++)
{
Temp = XX[t];
XX[t] = ADDI(XX[t], X[t]);
FREEMPI(Temp);
FREEMPI(X[t]);
}
ffree((char *)X, p * sizeof(MPI *));
if (M == NULL)
break;
else
{
for (l = 0; l < Q->C; l++)
{
FREEMPI(Q->V[m - 1][l]);
Q->V[m - 1][l] = COPYI(M->V[0][l]);
}
FREEMATI(MATI3);
MATI3 = M;
}
}
T2 = LENGTHSQRI(MATI3, 0);
if (RSV(T2, T1) == -1)
{
outfile = fopen(buff, "a");
fprintf(outfile, "(%u,%u,%u): ", i1,i2,i3);
fprintf(outfile, "b[%u]", m);
for (t = 0; t < p; t++)
{
e = XX[t]->S;
if (e == -1)
{
fprintf(outfile, "+");
Temp = MINUSI(XX[t]);
if (!EQONEI(Temp))
FPRINTI(outfile, Temp);
fprintf(outfile, "b[%u]", t + 1);
FREEMPI(Temp);
}
if (e == 1)
{
fprintf(outfile, "-");
if (!EQONEI(XX[t]))
FPRINTI(outfile, XX[t]);
fprintf(outfile, "b[%u]", t + 1);
}
}
fprintf(outfile, ": ");
DIFF = SUB0I(T1, T2);
FPRINTI(outfile, DIFF);
FREEMPI(DIFF);
fprintf(outfile, "\n");
fclose(outfile);
}
for (t = 0; t < p; t++)
FREEMPI(XX[t]);
ffree((char *)XX, p * sizeof(MPI *));
FREEMATI(BB);
FREEMATI(MATI3);
FREEMPI(T1);
FREEMPI(T2);
}
}
}
}
return;
}
MPMATI *LLLGCD0M(MPMATI *DD, MPI **Aptr, USI m, USI m1, USI n1)
/*
* Input: an m x 1 vector of positive MPI's.
* Output: *Aptr = gcd of the vector of MPI's. Also we return a small set of
* multipliers using the LLL method of Havas and Matthews.
* Normally m1=1,n1=1.
* Also returns matrix B of the LLL extended gcd algorithm of
* Havas-Majewski-Matthews is returned.
* 30/1/97.
* SHORTER is the shortest length squared all the m short vectors
* returned.
* The matrix returned is the one LLLGCD0 returns, but with the shortest
* of the X[K] as the last row. This is then used in GCD4() etc.
*/
{
unsigned int i, j, k, l, flag, p, t;
MPI **A, **D, *X, *Y, *Z, *Tmp, *R, *M1, *N1;
MPI **XX, *temp, *mu, *SUM, *SHORTER;
MPI *temp1, *T, *tempI1, *tempI2;
MPMATI *L, *B, *MATI1, *MATI2, *MATI;
MPR *tempR1;
int r, kk, K, c, COUNT, count;
B = IDENTITYI(m);
A = (MPI **)mmalloc(m * sizeof(MPI *));
for (i = 0; i < m; i++)
A[i] = COPYI(DD->V[i][0]);
D = (MPI **)mmalloc((1 + m) * sizeof(MPI *));
for (i = 0; i <= m; i++)
D[i] = ONEI();
L = ZEROMNI(m, m);
M1 = CHANGE(m1);
N1 = CHANGE(n1);
k = 2;
while (k <= m)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -